In my experience [1], observable sharing using GHC's stable names is a pretty effective solution to this problem.
Plus unsafePerformIO and weak references as in *Stretching the storage manager: weak pointers and stable names in Haskellhttp://citeseer.ist.psu.edu/peytonjones99stretching.html *? Lacking a more elegant alternative, that's what I'll probably do again, as in Pan, Vertigo, and Pajama. - Conal On Wed, May 27, 2009 at 3:51 AM, Sittampalam, Ganesh < ganesh.sittampalam@credit-suisse.com> wrote:
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 expression tree to blow up exponentially in relation to the code the user actually wrote! You can indeed construct an intermediate language that collapses this blowup, but the pass to create it must take exponential time if written completely purely, since it has to visit everything at least once.
In my experience [1], observable sharing using GHC's stable names is a pretty effective solution to this problem.
Ganesh
[1] http://www.earth.li/~ganesh/research/paradise-icfp08/http://www.earth.li/%7Eganesh/research/paradise-icfp08/
=============================================================================== Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html
===============================================================================