Make lines stricter to fix a space leak

Daniel Fischer daniel.is.fischer at web.de
Mon Sep 27 14:36:36 EDT 2010


On Monday 27 September 2010 19:40:52, Yitzchak Gale wrote:
> Daniel Fischer wrote:
> > Proposal: A stricter implementation of lines.
> > Reason: The current implementation causes a space leak
> > Ticket: http://hackage.haskell.org/trac/ghc/ticket/4334
>
> I propose the following combinator approach as
> an alternative:
>
> lines :: String -> [String]
> lines = map (takeWhile (/= '\n')) . takeWhile (not . null) .
>             iterate (drop 1 . dropWhile (/= '\n'))
>
> GHC fuses that into a tight loop.

Not here.
Neither 6.12.3 nor 6.13.20100917 did that.
Here, that uses even more memory than the current lines.
The core is ewww, you get functions for (/= '\n') [two] and (not . null), 
apart from that it's almost verbatim the Haskell code (split in chunks at 
the compositions).

Pity. Would've been nice to fix the leak without changing the semantics 
(and getting faster to boot).

> So in addition to solving
> the space leak, it is faster and uses less heap than both
> the existing implementation and Daniel's proposal.

I assume you tested on a 64-bit platform with lots of registers?
For us poor souls stuck on 32-bits, things look apparently *very* 
different. Even using Data.List.Stream instead of the Prelude functions 
didn't help much.

> It is also cleaner and easier to read, in my opinion.
>
> Thanks,
> Yitz

Cheers,
Daniel



More information about the Libraries mailing list