Strictness and space leaks

The classic space leak

A left fold with a lazy accumulator builds a tower of unevaluated additions. The number stays small, the chain does not:

-- the accumulator becomes (((0+1)+2)+3)+... foldl (+) 0 [1..1000000]

At a million elements the chain is a million frames deep. The result is correct and the process needs hundreds of megabytes to produce it. On a ten times larger input it may simply die.

seq and the strict fold

seq forces its first argument to weak head normal form before returning the second. The strict fold is written with it (here called foldlStrict to avoid a clash with the standard one):

-- seq :: a -> b -> b foldlStrict f z [] = z foldlStrict f z (x:xs) = let z2 = f z x in z2 `seq` foldlStrict f z2 xs

The seq call evaluates the new accumulator at every step, so only one number is alive at a time. Use foldl' from Data.List and the problem disappears.

Bang patterns

The BangPatterns extension writes the same thing at the pattern. A bang before a variable forces it as soon as it is bound:

{-# LANGUAGE BangPatterns #-} sumTo :: Int -> Int sumTo n = go 0 1 where go !acc i | i > n = acc | otherwise = go (acc + i) (i + 1)

The bang on acc keeps the accumulator evaluated, which is the difference between constant and linear memory for this loop.

Finding a leak

Guessing is slower than measuring. Compile with profiling and the runtime tells you where the memory went:

cabal build --enable-profiling

./todo +RTS -p -s

The runtime prints an allocation summary and a maximum residency figure; the numbers depend on the machine and the build. A large maximum residency with a small total allocation is the signature of a leak. -hT produces a heap profile that shows which type grows, and the strict fold usually fixes it.

The code on this page was run with GHC 9.10.3 on Alpine Linux 3.24.3 (x86_64) in a Docker container. The profiling commands were not run: the profiling libraries are not installed here.

Article author: Arthur Isaev