Make lines stricter to fix a space leak

[Simon Marlow]

On 25/09/10 01:55, Ian Lynagh wrote:
> 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
> them).

There were two depth limits in the GC.  The first affected chains of the 
form

    snd (x, snd (x, snd (x, ...)))

this was fixed a while ago.  The other one is:

    snd $ snd $ snd $ ...

which still has a depth limit (16) to avoid unbounded recursion in the 
GC.  This second form is less common I think than the other one, which 
cropped up quite a lot.

> I thought we had a ticket about that, but I can't find it now.

Feel free to make a ticket if you like.  I'd be inclined to wait and see 
if anyone actually runs into it in practice.

The other problem in this area is that the simplifier tends to transform 
code such that selector thunks aren't recognisable any more, so the GC 
optimisation doesn't apply.  I think we have a ticket for this one (but 
as I'm on a plane right now I can't find it).

Cheers,
	Simon


> If that was fixed then we could have constant space usage.
>
>
> Thanks
> Ian
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries