Different implementation for lines to fix a space leak (was: Make lines stricter ...)

Daniel Fischer daniel.is.fischer at web.de
Mon Oct 4 15:44:31 EDT 2010


On Monday 04 October 2010 20:15:07, Duncan Coutts wrote:
> On 24 September 2010 15:21, Daniel Fischer <daniel.is.fischer at web.de> 
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.
> >
> > Discussion period: Three weeks, until 15th October (because of ICFP).
> >
> > Ticket: http://hackage.haskell.org/trac/ghc/ticket/4334
>
> My gut instinct is that we should not make lines stricter.

I didn't see a way without changing the strictness properties at first.
Now there *seems* to be one, although I have doubts concerning its 
reliability to fix the leak. It's certainly more delicate than the stricter 
version.

> Generally the list library is as lazy as possible, except when there are
> compelling reasons otherwise. I am not yet convinced that this
> proposal meets that standard.
>
> Have we thought about the opposite issue, that there may be programs
> that rely on the current non-strict version for correctness or memory
> behaviour?

The possibility that some programmes rely on the current behaviour 
certainly exists.
Though, the only change in behaviour is when the first Char on a line is 
bottom, so I don't expect it would affect many programmes.

The memory behaviour can only be worse (by more than a few bytes) when the 
first Char on a line is the result of a space-demanding computation for the 
stricter version and not at all (as far as I can see) for the new 
suggestion.
I'd be surprised if that affected any programme negatively.

> We currently have an open proposal on making intersperse
> less strict because it caused practical problems (unexpected memory
> behaviour).
>
> There's also an issue of consistency with other functions in the list
> library. The lines function is similar in many ways to group /
> groupBy, and with the proposed change the strictness properties of
> these functions would be inconsistent. Such inconsistency has a cost
> in terms of programmers being able to predict and reason about
> strictness and space use (simply because if its inconsistent then it
> is harder to remember).

Agreed. That's why I favour the new suggestion (until someone comes forth 
with a reliable way to fix the leak or someone finds that it doesn't fix 
the leak in real use cases - it worked in my tests, but those were fairly 
simple).

>
> The strictness of lines is pretty subtle. I think it would help our
> discussion if people reading this thread look at the strictness
> properties given in the ticket.
>
> Duncan



More information about the Libraries mailing list