[Haskell-cafe] I love purity, but it's killing me.
tomahawkins at gmail.com
Tue May 26 20:24:14 EDT 2009
On Tue, May 26, 2009 at 6:49 PM, Conal Elliott <conal at conal.net> 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?
I wasn't able to find a solution that offered both performance and
elegance, so I changed the fundamental operation of the DSL (in this
case, atom). When atom was still a hardware description language, the
compiler would combine several user defined expressions together
resulting in very wide and deep expression trees, resulting in the
same problem you are observing. But when I switch the target of atom
from HDL to C, the compiler no longer needed to perform the same
expression expansion. And since the user defined expressions are
generally shallow -- at least in the case of my applications -- atom
is able to get away with exhaustive equality comparison (deriving Eq).
Sorry I can't be of more help.
More information about the Haskell-Cafe