Make lines stricter to fix a space leak
marlowsd at gmail.com
Sat Sep 25 14:38:35 EDT 2010
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
There were two depth limits in the GC. The first affected chains of the
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).
> If that was fixed then we could have constant space usage.
> Libraries mailing list
> Libraries at haskell.org
More information about the Libraries