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@haskell.org http://www.haskell.org/mailman/listinfo/libraries