why does this programm consume so much memory?

Question

I needed to use an algorithm to solve a KP problem some time ago, in haskell

Here is what my code look like:

stepKP :: [Int] -> (Int, Int) -> [Int]
stepKP l (p, v) = take p l ++ zipWith bestOption l (drop p l)
  where bestOption a = max (a+v)


kp :: [(Int, Int)] -> Int -> Int
kp l pMax = last $ foldl stepKP [0 | i <- [0..pMax]] l



main = print $ kp (zip weights values) 20000
       where weights = [0..2000]
             values = reverse  [8000..10000]

But when I try to execute it (after compilation with ghc, no flags), it seems pretty bad: here is the result of the command ./kp -RTS -s

1980100
   9,461,474,416 bytes allocated in the heap
   6,103,730,184 bytes copied during GC
   1,190,494,880 bytes maximum residency (18 sample(s))
       5,098,848 bytes maximum slop
            2624 MiB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      6473 colls,     0 par    2.173s   2.176s     0.0003s    0.0010s
  Gen  1        18 colls,     0 par    4.185s   4.188s     0.2327s    1.4993s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    3.320s  (  3.322s elapsed)
  GC      time    6.358s  (  6.365s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    9.679s  (  9.687s elapsed)

  %GC     time       0.0%  (0.0% elapsed)

  Alloc rate    2,849,443,762 bytes per MUT second

  Productivity  34.3% of total user, 34.3% of total elapsed

I thinks that my programm takes O(n*w) memory, while it could do it in O(w). (w is the total capacity)

Is that a problem of lazy evaluation taking too much space, or something else ? How could this code be more memory and time efficient ?

Answer 1

We can think of a left fold as performing iterations while keeping an accumulator that is returned at the end.

When there are lots of iterations, one concern is that the accumulator might grow too large in memory. And because Haskell is lazy, this can happen even when the accumulator is of a primitive type like Int: behind some seemingly innocent Int value a large number of pending operations might lurk, in the form of thunks.

Here the strict left fold function foldl' is useful because it ensures that, as the left fold is being evaluated, the accumulator will always be kept in weak head normal form (WHNF).

Alas, sometimes this isn't enough. WHNF only says that evaluation has progressed up to the "outermost constructor" of the value. This is enough for Int, but for recursive types like lists or trees, that isn't saying much: the thunks might simply lurk further down the list, or in branches below.

This is the case here, where the accumulator is a list that is recreated at each iteration. Each iteration, the foldl' only evaluates the list up to _ : _. Unevaluated max and zipWith operations start to pile up.

What we need is a way to trigger a full evaluation of the accumulator list at each iteration, one which cleans any max and zipWith thunks from memory. And this is what force accomplishes. When force $ something is evaluated to WHNF, something is fully evaluated to normal form, that is, not only up to the outermost constructor but "deeply".

Notice that we still need the foldl' in order to "trigger" the force at each iteration.