Compile-time optimization

[JS]

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.