Re: Common subexpression elemination (CSE)

On 11/28/06, Bertram Felgenhauer wrote:

Dinko Tenev wrote:

...

On 11/27/06, Lennart Augustsson wrote:

...

GHC doesn't normally do CSE. CSE can cause space leaks, so you can't do it willy-nilly. I'm sure there are some strict contexts where it could be done safely, but I don't think ghc uses that information (yet).

-- Lennart

My apologies in advance for asking possibly stupid questions, but I don't understand this.

How exactly can CSE cause space leaks, and what does this have to do with strictness?

Combining two expressions means that they're represented by the same memory location. In particular when you start evaluating the first, the second reference to the value will keep all of it alive even if parts of it could otherwise be freed. This is especially problematic for infinite lists.

http://hackage.haskell.org/trac/ghc/ticket/947

demonstrates this problem, caused by the little CSE that ghc does. (Note: This is not of the form "let x = term in ... term ...", but it will be once it's desugared and the simplifier has floated out the constant expressions from the "primes0" and "primes" functions)

I'm not sure how it relates to strictness. I'd be more worried about about the size of the data that's being kept alive. Numbers are more likely to be ok than lists.

Bertram

I see the point, though it still feels a bit weird to call this a leak (it also explains the relation to strictness for me, as the issue seems to be irrelevant in a strict context.) Thanks for the explanation. -- Cheers, Dinko