> > 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 Haskell<http://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.sittampa...@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 > > > =============================================================================== > >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
