On Tuesday, 23 July 2013 at 22:38:35 UTC, Yota wrote:
>   typeof(Xs[0]) sum(Xs...)()
>   {
>       pragma(msg, Xs); // tuple(1, 2, 3)
>       typeof(Xs[0]) y;
>       foreach(x; Xs) y ~= x;
>       return y;
>   }

*facepalm*
That ~= in there is what I get for copying code after I experiment on it.  Ment for it to be a +=. Phooey

~Yota

On Tue, Jul 23, 2013 at 10:11:17PM +0200, JS wrote:
[...]
> Note though that something like
> 
> string x = "asd"
> join(x,...); // x is compile time known and should be joined at
> compile time. Not sure if D is smart enough to get this one?

Well, if you want *that*, then you'll just have to submit a DMD pull request for the optimizer. ;-)

The problem is that even though in this particular case it should be easy for the compiler to figure out, in the general case it's far from trivial. For example, you might write:

	string x = "asd";
	x ~= "def";
	join(x, ...);

Arguably, the compiler should detect that the value of x is computable at compile-time, so it should apply the optimization. But the problem is, the code between the first line and the call to join() can be arbitrarily complex... for example:

	enum VeryLargeNumber = 2_391_382_391_483;
	string x = "asd";
	if (canFactorize(VeryLargeNumber))
		x ~= "x";
	join(x, ...);

Assuming canFactorize is CTFE-able, in theory the compiler should be able to figure out the value of x at compile-time. But integer factorization currently has no simple solution, which means your code will take 5 months to compile while DMD tries to solve integer factorization. Worse yet, you might write something like:

	string x = "asd";
	void function(int x) fn = createArbitraryFunction();
	if (canHalt(fn))
		x ~= "x";
	join(x, ...);

Then your program will *never* finish compiling, because the halting problem is unsolvable, but nothing stops you from writing a CTFE-able solution that requires infinite time to find an answer.


> When I get some time later I'll check your code out, what I want to do is get something like
> 
> string x = join(a, b, "a", "b"); to produce the same code as
> string x = a~b~"ab";
> 
> (no looping using for each except for string arrays)
[...]

That's pretty much what my code already does.  Just use GDC and it will unroll the loop for you. ;-)

Alternatively, since tupleReduce returns a tuple, you *could* just foreach over it (loops involving tuples are automatically unrolled at compile-time) and generate the code. That is, instead of using optimizedJoin() as a wrapper for a function, you could do something like this instead:

	string optimizedJoin(args...)() {
		string result;
		foreach (arg; tupleReduce!(
				(string x, string y) => x~y, args))
		{
			result ~= arg;
		}
		return result;
	}

I haven't tested this code, though, so I'm not 100% sure if it will work. But if not, a little massaging should make it work.

On another note, though, it makes me wonder why you want this level of control over the generated code. Are you sure you're not doing premature optimization? You should be aware that the more you use such arcane tricks to generate this "optimized" code, the less the compiler's built-in optimizer will be able to understand your intent, and the more likely that it may be generating more inferior code than if you had just written the code the "normal" way.

Generally, this level of manual optimization should only be done after you've profiled your code and identified the hotspots. I know from experience that more often than not, what you *think* is a hotspot actually isn't. It's only after running a profiler that you find out where the *real* hotspots are. :)  I used to be a hardcore optimization freak -- used to read assembly output from the compiler to identify inefficiencies -- until one day I actually ran a profiler on my code. Turns out that the real hotspot is completely NOT where I expected it. All those late nights spent "optimizing" my code, only to get negligible performance gain, when a 1-line change in the *real* hotspot improved performance by 30% instantly (and only took me 5 minutes instead of hours and hours).


T

-- 
My program has no bugs! Only undocumented features...

On Tuesday, 23 July 2013 at 22:38:35 UTC, Yota wrote:
> On Tuesday, 23 July 2013 at 20:11:21 UTC, JS wrote:
>> Your code doesn't exactly do what I wanted but probably because I wasn't clear... I think it is modifiable and solves the problem I was having(again, assuming your code is correct).
>>
>> Note though that something like
>>
>> string x = "asd"
>> join(x,...); // x is compile time known and should be joined at compile time. Not sure if D is smart enough to get this one?
>>
>> When I get some time later I'll check your code out, what I want to do is get something like
>>
>> string x = join(a, b, "a", "b"); to produce the same code as
>> string x = a~b~"ab";
>>
>> (no looping using for each except for string arrays)
>>
>> Thanks!
>
>
> Don't forget that tuples can store more than just types!  See this for instance.
>
>   import std.stdio;
>
>   typeof(Xs[0]) sum(Xs...)()
>   {
>       pragma(msg, Xs); // tuple(1, 2, 3)
>       typeof(Xs[0]) y;
>       foreach(x; Xs) y ~= x;
>       return y;
>   }
>
>   int main() {
>       auto n = sum!(1, 2, 3);
>       enum m = sum!(1, 2, 3);
>
>       pragma(msg, typeof(n)); // int
>       writeln(n); // 6
>       writeln(m); // 6
>
>       return 0;
>   }
>
> Works great.  When I comment out the 'sum!("1", "2", "3")' and replace it with a literal '6', the compiled EXE is byte for byte exactly the same.  You can exchange the '+=' for '~=' and it will concatenate strings instead.  Of course, now all arguments MUST be known at compile time, but that's no surprise.
>
> PS: OK, just noticed that you were hoping to mix run time and compile time arguments.  Oops....
> Oh well, posting anyway because I think it's neat. lol
>
> As for a~"B"~"C" compiling into a~"BC", I think we just need to work on constant folding in the compiler. (If it doesn't already do this anyway.)

Well, it's not that simple. Constant folding is easy when it is obvious to the compiler... but something buried in foreach loop that uses runtime and compile time objects is not obvious.

My three points out of the post is:

1. D needs some way to make doing this stuff easier.
2. It needs to be done! ;)
3. Goto 1.

I didn't realize D could even potentially do it, and still not sure if it can(have to check out T's post again and work with the code).

I think there is a lot of potential power behind such techniques with regard to optimization.

Suppose you are writing a matrix library. Wouldn't it be nice to have certain matrix computations that can be done at compile time actually done? (I suppose what I'm trying to do is extend the compiler's "constant folding" to be able to deal with much more complex cases).


Another way to potentially do it, I think, is for the compiler to automatically expand ctfe functions and replace runtime entities with "placeholder" code which is then expanded at runtime.

e.g., for a simple join

join(T...)(T t)
{
    string s;
    foreach(tt; t)
        s ~= tt;
    return s;
}

the compiler can unroll the loop to get

s ~= t[0]~t[1]~t[2]~...;

replace the compile time entities, e.g., suppose t[1] and t[3] are known at compile time at the invocation, then

s ~= t[0]~"abcd"~t[2]~"asdf";

then this code could be used inline for the join call instead of the actual code. The key here is there is no dependence on the for loop. If all arguments are compile-time evaluable, then s could be just a reference lookup to a static string. If it can't be done, then no big deal, it is optimized as far as it can go. Only if all arguments passed are runtime entities will the exact code be used.

This seems like it would take a pretty smart compiler and possibly it would have issues in some many cases. I personally don't mind writing the code itself but it seems pretty complex, and having no way to debug the code generation easily(AFAIK) makes it difficult to do.

Possibly using version(ctfe) can help... I'll work on it when I get a chance...

On Wed, Jul 24, 2013 at 01:35:23AM +0200, JS wrote:
[...]
> My three points out of the post is:
> 
> 1. D needs some way to make doing this stuff easier.
> 2. It needs to be done! ;)
> 3. Goto 1.
> 
> I didn't realize D could even potentially do it, and still not sure if it can(have to check out T's post again and work with the code).
> 
> I think there is a lot of potential power behind such techniques with regard to optimization.
> 
> Suppose you are writing a matrix library. Wouldn't it be nice to have certain matrix computations that can be done at compile time actually done? (I suppose what I'm trying to do is extend the compiler's "constant folding" to be able to deal with much more complex cases).
[...]

You're looking for expression templates. So far, nobody seems to have written expression templates in D yet (that I know of, anyway, I could be wrong). D should be more than well-equipped to handle expression templates, you just have to write them. (But having said that, they aren't exactly easy to write. :-P)

I think the last time this topic came up, somebody mentioned the dreaded mythical AST macros, and the discussion got derailed. I've been meaning to write a D matrix library using expression templates, but I haven't gotten around to it yet.

The basic idea behind expression templates is that overloaded operators (or function calls, if operator overloading isn't good enough for you) don't return concrete types, but a proxy wrapper type that gets unboxed into a real type when assigned to a concrete variable. The operators are overloaded to take these wrapper types as arguments, and basically construct a template tree paralleling the structure of the expression so that when you're finally assigning the result to a concrete variable, the assignment operator can traverse the expression tree, fold constants and do whatever other optimizations you wish, then generate optimized code for performing the operation represented by the tree.

That's the theory anyway. In practice, expression templates are rather hard to write (and read!) if you're the unlucky library writer (it *is* really nice from the user's POV though!). They are also one of the sources of C++ error messages that span 15 pages per line, if you're ever unlucky enough to run into a problem.

Last I was told, however, that the preferred approach in D is to use string mixins instead. You basically write a string containing an arbitrary expression (of arbtrary syntax, even!) that gets parsed by a CTFE lexer/parser that can perform arbitrary transformations on it, which generates D code as a string that you can use in a mixin. This is significantly more powerful than expression templates, because you're no longer constrained by the syntax of the host language, but your input string can be literally *anything*, like a DSL, or a math expression containing real, bona fide Unicode mathematical symbols for operators, sets, and what-have-you. You could even write your own language that way. All of it eventually gets compiled down into D code as a string mixin.

Syntax-wise, there's the slight ugliness of having to write "mixin(MyDSL("A ± B / C → D"))", but that's more than outweighed by the total freedom of syntax within the input string itself. I saw an expression-template-based regex implementation in C++ once, and almost went blind. It overloaded C++ operators in rather ugly ways in order to work around the fact that C++ doesn't have native regex operators. By contrast, our own std.regex has a ctRegex function that essentially does the same thing while allowing you to use native regex syntax within a string literal. I think that's a far better approach for many cases. :)


T

-- 
It always amuses me that Windows has a Safe Mode during bootup. Does that mean that Windows is normally unsafe?

On Wednesday, 24 July 2013 at 01:07:15 UTC, H. S. Teoh wrote:
> On Wed, Jul 24, 2013 at 01:35:23AM +0200, JS wrote:
> [...]
>> My three points out of the post is:
>> 
>> 1. D needs some way to make doing this stuff easier.
>> 2. It needs to be done! ;)
>> 3. Goto 1.
>> 
>> I didn't realize D could even potentially do it, and still not sure
>> if it can(have to check out T's post again and work with the code).
>> 
>> I think there is a lot of potential power behind such techniques
>> with regard to optimization.
>> 
>> Suppose you are writing a matrix library. Wouldn't it be nice to
>> have certain matrix computations that can be done at compile time
>> actually done? (I suppose what I'm trying to do is extend the
>> compiler's "constant folding" to be able to deal with much more
>> complex cases).
> [...]
>

Your tuple reduce seems to work! Debugging the code shows no loops and memory debugging looks like the adjacent constants are folded! magnificent!

As far as over optimizing, I am trying to write some library code and want to "get it right" the first time... having it not only optimize the best it can but also make the functions easier to use... e.g., variargs instead of nested calls.

As far as ctfe running time issues, I believe they exist already?

In any case, the compiler at some point has to mark a variable that is compile time evaluable as not evaluable at some point(probably at a function call)

What we do know is arguments to ctfe's return compile time evaluable results... So it is easy to know that a variable is compile time evaluable but not necessarily actually be able to compute it at compile time.... a simple time out count with error/warning could be used... if failed it could be marked as a run-time entity at that point and beyond(so no optimization beyond the point where it can't be computed at compile time. Not perfect but covers 99.99% of cases.





> You're looking for expression templates. So far, nobody seems to have
> written expression templates in D yet (that I know of, anyway, I could
> be wrong). D should be more than well-equipped to handle expression
> templates, you just have to write them. (But having said that, they
> aren't exactly easy to write. :-P)
>

I think I'll pass, I'm still struggling just to learn D. You, OTH, seem like someone that can pull it off rather easily!
> I think the last time this topic came up, somebody mentioned the dreaded
> mythical AST macros, and the discussion got derailed. I've been meaning
> to write a D matrix library using expression templates, but I haven't
> gotten around to it yet.
>
> The basic idea behind expression templates is that overloaded operators
> (or function calls, if operator overloading isn't good enough for you)
> don't return concrete types, but a proxy wrapper type that gets unboxed
> into a real type when assigned to a concrete variable. The operators are
> overloaded to take these wrapper types as arguments, and basically
> construct a template tree paralleling the structure of the expression so
> that when you're finally assigning the result to a concrete variable,
> the assignment operator can traverse the expression tree, fold constants
> and do whatever other optimizations you wish, then generate optimized
> code for performing the operation represented by the tree.
>
> That's the theory anyway. In practice, expression templates are rather
> hard to write (and read!) if you're the unlucky library writer (it *is*
> really nice from the user's POV though!). They are also one of the
> sources of C++ error messages that span 15 pages per line, if you're
> ever unlucky enough to run into a problem.
>
> Last I was told, however, that the preferred approach in D is to use
> string mixins instead. You basically write a string containing an
> arbitrary expression (of arbtrary syntax, even!) that gets parsed by a
> CTFE lexer/parser that can perform arbitrary transformations on it,
> which generates D code as a string that you can use in a mixin. This is
> significantly more powerful than expression templates, because you're no
> longer constrained by the syntax of the host language, but your input
> string can be literally *anything*, like a DSL, or a math expression
> containing real, bona fide Unicode mathematical symbols for operators,
> sets, and what-have-you. You could even write your own language that
> way. All of it eventually gets compiled down into D code as a string
> mixin.
>
> Syntax-wise, there's the slight ugliness of having to write
> "mixin(MyDSL("A ± B / C → D"))", but that's more than outweighed by the
> total freedom of syntax within the input string itself. I saw an
> expression-template-based regex implementation in C++ once, and almost
> went blind. It overloaded C++ operators in rather ugly ways in order to
> work around the fact that C++ doesn't have native regex operators. By
> contrast, our own std.regex has a ctRegex function that essentially does
> the same thing while allowing you to use native regex syntax within a
> string literal. I think that's a far better approach for many cases. :)
>
>

I was wondering if that was possible. I was using string mixins to essentially accomplish the constant folding was thinking that one could implement java script or some other language in the strings and have them transformed. It could be pretty useful to have. I've still got a lot to learn about D but it seems nearly unbounded for what it can do compared to other languages.

Thanks for making this work! I'll spend some time studying your code to learn how it works then try to apply it to my library code.

Trying to do stripLeft/Right, split, join, etc... for strings. Each function taking an arbitrary number of run-time or compile-time char or string arguments with optimal code generation.

On Tuesday, 23 July 2013 at 17:41:01 UTC, Ali Çehreli wrote:
> On 07/23/2013 09:21 AM, JS wrote:
>
> > string join(T...)(T t)    // Note join has a variadic
> parameter
> > {
> >      ctfe {
>
> Are you aware of version(ctfe)?

Hum... really? I don't think that exists. Either that, or I'm using it wrong. Could you provide an example?

What you do have is "if (__ctfe)" though...

//----
import std.stdio;

int foo()
{
    version (poop)
        return 1;
    else
        return 0;
}

void main(string[] args)
{
    enum a = foo();
    auto b = foo();
    writeln(a, " ", b);
}
//----
Prints: 0 0

//----
import std.stdio;

int foo()
{
    if (__ctfe)
        return 1;
    else
        return 0;
}

void main(string[] args)
{
    enum a = foo();
    auto b = foo();
    writeln(a, " ", b);
}
//----
Prints: 1 0

On Wednesday, 24 July 2013 at 09:56:41 UTC, monarch_dodra wrote:
>     version (poop)

Goddamnit. There goes my credibility -_-'

I was testing to see if I got a compile error with an inexistant version tag. Please replace that with "ctfe"

On Wednesday, 24 July 2013 at 09:58:02 UTC, monarch_dodra wrote:
> On Wednesday, 24 July 2013 at 09:56:41 UTC, monarch_dodra wrote:
>>    version (poop)
>
> Goddamnit. There goes my credibility -_-'
>
> I was testing to see if I got a compile error with an inexistant version tag. Please replace that with "ctfe"

lol... I was wondering were the hell that came from. I thought maybe it meant you wrote that part of the code on the toilet ;)

On 07/24/2013 02:56 AM, monarch_dodra wrote:

> On Tuesday, 23 July 2013 at 17:41:01 UTC, Ali Çehreli wrote:

>> Are you aware of version(ctfe)?
>
> Hum... really? I don't think that exists.

You are right. I must be remembering old proposals about it.

Ali

On Wed, Jul 24, 2013 at 09:22:14AM -0700, Ali Çehreli wrote:
> On 07/24/2013 02:56 AM, monarch_dodra wrote:
> 
> > On Tuesday, 23 July 2013 at 17:41:01 UTC, Ali Çehreli wrote:
> 
> >> Are you aware of version(ctfe)?
> >
> > Hum... really? I don't think that exists.
> 
> You are right. I must be remembering old proposals about it.
[...]

There's if(__ctfe), but unfortunately (IIRC) it doesn't work with static if, because CTFE runs after static ifs have been processed. So it might not be enough if you have code that has parts that can't run under CTFE. Those parts will taint all parent functions up the call tree as non-CTFEable, so once you have them you're out of luck.


T

-- 
We are in class, we are supposed to be learning, we have a teacher... Is it too much that I expect him to teach me??? -- RL