[ this reply was slightly delayed because I accidentally sent it to just
Fergus instead of the whole list... ]
Fergus Henderson <[EMAIL PROTECTED]> writes:
> The query quoted below, about heap usage in a 5-line Haskell program,
> has remained unanswered for two weeks.
Ok, I'll give it a shot. This particular 5-line example needed about
3 cups of coffee's worth of investigation.
> On 14-Sep-1998, Martin Stein <[EMAIL PROTECTED]> wrote:
> > Hi,
> >
> > though I think there was written enough about this theme, I can't still
> > understand the following problem (foldl' from the Prelude.hs):
> >
> > > seq1 x = (3-x):seq1 x
> > > seq2 x = (3-x):seq2 1
> > >
> > > countOne xs = foldl' (\c x -> if x==1 then c+1 else c) 0 xs
> > >
> > > num1 n = countOne (take n (seq1 1))
> > > num2 n = countOne (take n (seq2 1))
> >
> > num1 needs lots of heap space, num2 needs very few. Why?
> > (I checked it using ghc and '+RTS -s')
If we define foldl' as:
foldl' f c [] = c
foldl' f c (x:xs) = let z = f c x in seq z (foldl' f z xs)
(the version using 'strict' is similar) then the call to seq compiles
to
let w = foldl' f z xs
in seq z w
where w is an updatable thunk. When the thunk for w is finally
entered, it will push an update frame and tail-call foldl'. This
means that not only does a naive implementation of foldl' require
linear stack, it also requires linear heap for all the w thunks.
That's not good.
If the definition of seq is inlined, then we get the (much better):
case z of z' -> foldl' f z' xs
This runs in constant stack/heap. In GHC, seq is inlined if the -O
flag is given.
I checked this with both ghc-3.02 and ghc-4.00 with and without -O,
and except for ghc-4.00 without -O they all require a constant 200
bytes or so of heap. The anomaly with ghc-4.00 is because the new
garbage collector doesn't implement stack squeezing (yet). Stack
squeezing is an optimisation whereby sequences of update frames on the
stack can be squeezed into a single frame, saving the extra updates
and allowing the extra thunks in the heap to be collected. You can
see the effect in ghc-3.02 by turning off squeezing with the -Z flag:
ghc-3.02 test.hs
a.out +RTS -Z -Sstderr -F2s -K4m
You might also have been tripped up by the generational collector -
with this example it seems to hang on to a lot of stuff until a major
collection, probably because something in the old generation gets
updated with a pointer into the new generation, which is retained
until a major collection is triggered. The -F2s flag forces a 2-space
collector to be used.
Cheers,
Simon
--
Simon Marlow [EMAIL PROTECTED]
University of Glasgow http://www.dcs.gla.ac.uk/~simonm/
finger for PGP public key
