Common subexpression elemination (CSE)

[Lennart Augustsson]

The relation to strictness is that you have much tighter control over  
when things are evaluated (typically) for something strict, so it is  
less likely to leak.
Take the expression 'e + e' at some base type.  It's harmless to CSE  
this to 'let x = e in x+x' because + is strict in x.  Whereas '(e,e)'  
can't be CSE:ed to 'let x = e in (x,x)' without risking a space leak.

It's not exactly strictness, it's more about knowing when a value is  
going to be consumed.
Also, things that are "small" can be CSE:ed, since the evaulated form  
doesn't take more space than the unevaluated.

	-- Lennart

On Nov 28, 2006, at 09:50 , Bertram Felgenhauer wrote:

> Dinko Tenev wrote:
>> On 11/27/06, Lennart Augustsson <lennart at augustsson.net> 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
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users