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:
- bytes allocated in the heap: the total work, which tells you whether the program did more than it needed to.
- bytes copied during GC: how much the collector moved, which follows from the residency.
- bytes maximum residency: the peak live heap, the number a space leak inflates.
- total memory in use: what the process held at the peak.
- GC time and Total time: whether the collector or the program dominated.
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
- Run the three programs with +RTS -s on your machine and compare the residency lines with the ones here.
- Change the fold to -O2 and compare it with -O1.
- Replace the list with a list of Integer and say what changes in allocation.
- Explain why length does not leak on a million-element list while this fold does.
- 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.
-
Which line of
+RTS -sshows a space leak?Answer
The maximum residency line
A leak keeps memory live, so the peak live heap, the maximum residency, grows.
-
Why does
foldl (+) 0build 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.
-
What does
foldl'do differently?Answer
It forces the accumulator at every step
The strict fold evaluates each new accumulator, so no chain exists.
-
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.
-
Which flag prints the heap report?
Answer
+RTS -sThe -s RTS option prints the allocation, GC and residency summary at exit.
-
What did the measurement at
-O1show 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.
-
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.
-
Why is relying on
-O1to 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'.
-
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.
-
What is the maximum residency of the
-O0strict 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