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's your latest wisdom about CSE in DSELs?
Thanks, - Conal
One common trick that Tom didn't seem to mention in the 2008-02-07T23:33
post is hash cons'ing.
Given a perfect hash function, traverse the term bottom-up storing each
(hash,subterm) pair in a memo table and replacing the subterm by its
hash. Once that's done, equality checks are trivial, and the memotable
can be converted to SSA rather easily.
This works best if you amortize the memoization by doing it with smart
constructors, so that you don't need to worry about the exponential
duplication of work for expressions with DAGy structure sharing in the
Haskell. Since it's stateful, that means the smart constructors may need
to be in an appropriate monad/applicative for passing the memo table
around (some hash functions may not need to store the table explicitly).
Maybe this is the too-slow too-complex solution you're using already?
--
Live well,
~wren
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
