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.

The key is *memoization*. See [here](http://stackoverflow.com/questions/11466284/how-is-this-fibonacci-function-memoized). — Alexey Radkov, Jan 09 '17 at 12:45

score 12 · Accepted Answer · edited May 23 '17 at 11:53

12

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?

edited May 23 '17 at 11:53

Community

1
1

answered Jan 09 '17 at 13:41

Reid Barton

14,951
3
39
49

I did some tests on the repl to try to confirm this and seems correct. I also looked at the link provided by @alexey-radkov about memoization and the suggestion there was that it had to do with the first function being monomorphic and therefore shared between calls, whereas the second is polymorphic, but I couldn't confirm this e.g. by redefining `map` to be monomorphic. – Mikkel Jan 09 '17 at 14:30
TL;DR Because `map fib [0..]` is in a lambda it isn't shared, but garbage collected between (recursive) calls. Correct? – Mikkel Jan 09 '17 at 14:31
@Mikkel Right, and the reason is because (though it doesn't in this case) it could depend on `i`, and then couldn't be shared. (And this is usually a good way to see what will be shared without doing the desugaring first.) – Reid Barton Jan 09 '17 at 16:37

score 7 · Answer 2 · answered Jan 09 '17 at 11:23

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.

A little additional explanation for _why_ the `where` block is re-evaluated: it's because `i` is in the `where` block's closure. If you were to write it as `let mfib = \i -> map fib [0..] !! i where ...` it'd be just as fast as the eta-contracted version. That said, I'm surprised GHC didn't spot an opportunity to apply the full-laziness transformation and float `fib` outside the binder. — Benjamin Hodgson, Jan 09 '17 at 12:22
@BenjaminHodgson I did indeed try putting the `i` in a lambda, but it makes no difference -- memoization still not "working". — Mikkel, Jan 09 '17 at 13:32

GHC optimization

2 Answers2