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.