GHC optimization

Question

The two Haskell functions below seems to differ only by whether the index variable is implicit or explicit but the difference in performance is by two orders of magnitude.

This function takes about 0.03 seconds to calculate mfib 30:

let mfib = (map fib [0..] !!)
  where
    fib 0 = 0
    fib 1 = 1
    fib x = mfib (x-1) + mfib (x-2)

This function takes about 3 seconds for mfib 30:

let mfib i = map fib [0..] !! i
  where
    fib 0 = 0
    fib 1 = 1
    fib x = mfib (x-1) + mfib (x-2)

I'm guessing it has to do with GHC inline rules and have been trying to add inline/noinline pragmas to get matching performance.

EDIT: I understand how doing a lookup into the lazy list can be used to memoize the fib function and why the traditional definition of fib is very slow. I was expecting the memoization to work in the second function as well as the first and don't understand why it is not.

Answer 1

It's easier to understand these differences when looking at the desugared code, so here are partially desugared versions of the two functions.

let mfib = let fib 0 = 0
               fib 1 = 1
               fib x = mfib (x-1) + mfib (x-2)
           in (!!) (map fib [0..])

versus

let mfib = \i ->
               let fib 0 = 0
                   fib 1 = 1
                   fib x = mfib (x-1) + mfib (x-2)
               in map fib [0..] !! i

Note that in the second program, the expression map fib [0..] appears inside \i -> ..., so it will (normally, without optimizations) evaluated for each value of i. See When is memoization automatic in GHC Haskell?

Answer 2

No, this has nothing to do with inlining. The difference is that mfib = (map fib [0..] !!) has no arguments. It's still a function of course, but evaluating that function does upfront not require to pass any argument. In particular, evaluating this mfib will generate the fib list in a way that it can be reused for all indices.

OTOH, mfib i = map fib [0..] !! i means the entire where block will only get considered when you actually pass an argument i.

The two are only different if you evaluate a function many multiple times again and again. Unfortunately for the second version, the functions own recursion already calls it again and again! So mfib (x-1) + mfib (x-2) then needs to do the entire work of mfib (x-1), and then again the entire work of mfib (x-2). So mfib n takes more than twice the computational cost of mfib (n-1), therefore mfib ∈ O (2ⁿ).

That's incredibly wasteful, because most of the terms in mfib (x-2) are also already in mfib (x-1) and could simply be re-used. Well, that's exactly what your first version does, because it computes the fib list once and for all indices, so evaluating mfib (x-1) will already do most of the work that can then simply be re-read by mfib (x-2), reducing the complexity to polynomial.