Compile-time optimization

[H. S. Teoh]

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?