Make lines stricter to fix a space leak
igloo at earth.li
Fri Sep 24 20:55:24 EDT 2010
On Fri, Sep 24, 2010 at 09:21:19PM +0200, Daniel Fischer wrote:
> Proposal: A stricter implementation of lines.
> Reason: The current implementation causes a space leak (cf.
> http://homepages.inf.ed.ac.uk/wadler/papers/leak/leak.ps), at least in GHC.
> The proposed implementation fixes the leak at the small cost of being
> stricter if the first _|_ in the String is the first character of a line.
I think this changes the definition from one that currently has a space
leak with GHC, to one which necessarily must have a space leak (as all
of l must be held in memory while we look for a newline).
IIRC GHC's GC does have an optimisation which I believe would apply
here, where it reduces essentially (snd (x, y)) in the heap to y, but
that that optimisation isn't always good enough (it has a threshold for
how deep it is willing to reduce, and a small loop like this will
generates pairs and selectors faster than the GC is willing to reduce
I thought we had a ticket about that, but I can't find it now.
If that was fixed then we could have constant space usage.
More information about the Libraries