Common subexpression elemination (CSE)

[Dinko Tenev]

On 11/28/06, Bertram Felgenhauer <bertram.felgenhauer at googlemail.com> 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



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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20061128/266c6f25/attachment.htm