Space leaks and +RTS -s

What a space leak is

A space leak is memory that a program cannot free because a thunk still refers to it, even though the final answer does not need it. The classic case is a lazy accumulator: foldl (+) 0 is ((0 + x1) + x2) + x3 and so on, a left-nested chain of thunks that is only collapsed when the result is demanded. On a million elements the chain is a million thunks, and the residency of the program is that chain.

foldl (+) 0 [1, 2, 3] = ((0 + 1) + 2) + 3 -- a chain foldl' (+) 0 [1, 2, 3] = (((0 + 1) + 2) + 3) -- forced at each step

The two give the same answer and differ in memory. The RTS can tell you which one your program ran, and that is what the rest of the lesson does, with the numbers of a real run on this machine.

+RTS -s and the lines that matter

Every GHC binary accepts +RTS -s -RTS and prints a report of the heap when it finishes. Five lines carry the diagnosis:

The sizes of the default generation are in +RTS --info and can be changed with -A and -H; all three programs below use the defaults of GHC 9.10.3, with no -rtsopts and no other RTS flag, so the only difference is the flag given to ghc and the fold in the source.

foldl on a million elements

module Main (main) where main :: IO () main = print (foldl (+) 0 [1 .. 1000000 :: Int])

ghc -Wall -O0 -o foldl foldl.hs
./foldl +RTS -s

500000500000
     161,310,144 bytes allocated in the heap
     199,826,496 bytes copied during GC
      49,563,296 bytes maximum residency (5 sample(s))
         801,120 bytes maximum slop
             101 MiB total memory in use (0 MiB lost due to fragmentation)
  GC      time    0.371s  (  0.375s elapsed)
  Total   time    0.440s  (  0.445s elapsed)

The answer is right and the residency is the leak: about 47 MiB live at the peak and the larger part of the run in the collector, for a sum that needs no memory at all. The bytes allocated line shows the work of building and then collapsing the chain, and the GC time line shows what the collector cost.

The same fold with foldl'

module Main (main) where import Data.List (foldl') main :: IO () main = print (foldl' (+) 0 [1 .. 1000000 :: Int])

ghc -Wall -O0 -o foldlprime foldlprime.hs
./foldlprime +RTS -s

500000500000
      88,050,624 bytes allocated in the heap
          14,008 bytes copied during GC
          44,328 bytes maximum residency (2 sample(s))
          29,400 bytes maximum slop
               6 MiB total memory in use (0 MiB lost due to fragmentation)
  GC      time    0.001s  (  0.001s elapsed)
  Total   time    0.025s  (  0.025s elapsed)

Same answer, same build flags, and the peak residency is 44,328 bytes instead of 49,563,296: the accumulator is evaluated at every step, so the chain never exists. The allocation is halved as well, because the program builds integers and not thunks, and the collector runs for a millisecond instead of most of the run.

The optimizer and what it hides

The first program is compiled with -O0 on purpose. The course builds with -O1, and at -O1 the strictness analysis of GHC sees that the numeric accumulator of this particular fold is always demanded and turns it into a strict loop. The same lazy source then measures like the strict one:

module Main (main) where main :: IO () main = print (foldl (+) 0 [1 .. 1000000 :: Int])

ghc -Wall -O1 -o foldopt foldopt.hs
./foldopt +RTS -s

500000500000
          50,440 bytes allocated in the heap
           3,272 bytes copied during GC
          44,328 bytes maximum residency (1 sample(s))
          25,304 bytes maximum slop
               6 MiB total memory in use (0 MiB lost due to fragmentation)
  GC      time    0.000s  (  0.000s elapsed)
  Total   time    0.002s  (  0.001s elapsed)

That is a real and useful result, and it is also a trap: the optimizer saved this fold and will not save every one. A fold into a data structure, a foldl whose combining function is not strict in the accumulator, or a build at -O0 keeps the chain, so write the strict fold when strictness is what you mean and do not rely on the flag. The measurements here are one run each on an Alpine 3.24.3 container with GHC 9.10.3 on four CPUs; the residency numbers are stable between runs, while the times move with the load of the machine.

Exercises

  1. Run the three programs with +RTS -s on your machine and compare the residency lines with the ones here.
  2. Change the fold to -O2 and compare it with -O1.
  3. Replace the list with a list of Integer and say what changes in allocation.
  4. Explain why length does not leak on a million-element list while this fold does.
  5. Add -s to a program of the previous lesson and find its maximum residency.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. Which line of +RTS -s shows a space leak?

    Answer

    The maximum residency line

    A leak keeps memory live, so the peak live heap, the maximum residency, grows.

  2. Why does foldl (+) 0 build a chain?

    Answer

    The accumulator is a thunk until the final result is demanded

    foldl nests the applications on the left without forcing them, so the chain grows with the input.

  3. What does foldl' do differently?

    Answer

    It forces the accumulator at every step

    The strict fold evaluates each new accumulator, so no chain exists.

  4. What does this program print? module Main (main) where import Data.List (foldl') main :: IO () main = print (foldl' (+) 0 [1 .. 4 :: Int])

    Answer

    10

    The strict fold adds 1, 2, 3 and 4 to the starting zero.

  5. Which flag prints the heap report?

    Answer

    +RTS -s

    The -s RTS option prints the allocation, GC and residency summary at exit.

  6. What did the measurement at -O1 show for the lazy fold?

    Answer

    The optimizer turned it into a strict loop, with a residency like the strict one

    GHC saw that the numeric accumulator was always demanded and removed the chain at -O1.

  7. What does the bytes allocated line tell you?

    Answer

    How much work the program did, including the thunks it built

    Allocation counts every heap object the program created, so a chain of thunks shows up there too.

  8. Why is relying on -O1 to remove the chain a bad idea?

    Answer

    The optimizer helps some folds and not others, so the leak can come back in another program

    Strictness analysis is a heuristic; the source should say what it means with foldl'.

  9. What happens to the residency if the fold builds a list instead of an Int?

    Answer

    It grows with the list, because the list is live data

    A list that the program keeps is live data, and the peak live heap is its size.

  10. What is the maximum residency of the -O0 strict fold in this lesson?

    Answer

    44,328 bytes

    The strict fold held 44,328 bytes at its peak, against 49,563,296 for the lazy one.

The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev