Recently I was surprised by the behaviour of a Haskell program I wrote. This simple example demonstrates the problem:
This computes the length of the list formed by every n-sized
combination of the letters “a”, “b” and “c”. For example, if
4, the first few elements of the list are “aaaa”, “aaab”, “aaac”,
“aaba”. (In other words, it’s a slow way to compute 3 to the power of
n.) I expected this program to take near-constant space, even
though the list might be very long, because it can be consumed by
length as it is produced by
n increases the space required grows exponentially.
The “in use” value is the interesting one: 4MB for
n=10, and 11MB
Even more surprising is what happens when you give your own definition
Now the same examples as before:
This time we get constant space. Then take the same program, and turn on optimization:
And memory use is high again — optimization has made it worse. What is going on?
The explanation is that GHC has tried to make our definition of
mySequence faster, but at the expense of using more memory. It has
observed that the value of
mySequence ys does not depend on what
value is chosen for
x, and moved it out of the loop. In effect, it
has transformed our definition into:
The result for our combination-counting program is that to compute the
big list of
n-sized combinations, it first computes the list of
(n-1)-sized combinations and keeps this sub-list in memory so that
it can put an “a”, “b” or “c” on the front of each element. That is,
while exploring all the combinations that start with “a”, the sub-list
stays in memory so it doesn’t have to be computed again later to make
all the combinations that start with “b” and “c”. The sub-list is
pretty big, and that’s the cause of the high memory use.
This optimization is called “full laziness”, and you can turn it off:
With the optimization turned off, memory use is constant again.
When I first encountered this problem I had no idea what the cause was. After some searching I found this discussion on Stack Overflow, which explains what is going on and a couple of ways to work around it (apart from just turning off the full laziness optimization).
A second problem
A variation of the problem comes courtesy of Albert Lai. In this program, we also get exponential memory use, but changing the optimization level doesn’t fix it. Here is the program in question:
On the surface it looks similar to the previous programs. In
particular, the definition of
k is very close to
and so you might expect that the full laziness optimization is again
the culprit. But turning off optimization here doesn’t help.
In this case the
foldr is the problem. Recall the behaviour of
In the misbehaving problem, we have:
ms = [m0, m1, ... mn]. If we examine the outermost call to
k more closely, we get:
This is equivalent in behaviour to:
k has done the same thing that full laziness did: it’s
given a name (here
m') to the big sub-list, causing it to be shared
across the loop over the choice of the first element (the
x <- m).