Sebastiaan Visser wrote:
> On May 27, 2009, at 1:49 AM,
Conal Elliott wrote:
>> Hi Tom,
>>
>> I've been
working on another code-generating graphics compiler,
>> generating
GPU code. As always, I run into the problem of efficient
>>
common subexpression elimination. In Pan, Vertigo & Pajama, I
used
>> lazy memoization, using stable pointers and weak references,
to avoid
>> the worst-case-exponential behavior you mention below.
I'm now using
>> a bottom-up CSE method that's slower and more
complicated than I'm
>> going for.
>
> What do you mean
with `exponential behavior'? Exponential related to
>
what?
>
> For my FRP EDSL to JavaScript (toy) compiler[1] I've
been
> implementing CSE as well. I traverses the expression tree
recursively
> and creates an small intermediate language containing id's
(pointers)
> to expressions instead of real
sub-expressions.
>
> Maybe (probably) I am very naive, but I think
this trick takes time
> linear to the amount of sub-expressions in my
script. When using a
> trie instead of a binary tree for the comparisons
there should be no
> more character (or atomic expression) comparisons
that the amount of
> characters in the script.
>
> So the
problem seems not to be CSE algorithm, but the fact that EDSL
> itself
tends to blow up because it is hosted in Haskell. Like Tom's
>
example:
>
> > let d = Add c c
> >
e = Add d d -- "e" now as 16 leaf nodes.
>
>
But again, I might be missing some important point
here.
That's exactly right. But it's pretty inconvenient to
have your