CODEWITHSUNDEEP
haskellrecursionoptimizationtail-recursionmicrobenchmark
lloydmeta
lloydmeta

Reputation: 1339

Haskell Fibonacci: Tail-Recursive slower than the classic lazy list approach?

Disclaimer: some possibly dubious Haskell ahead.

I've implemented 2 versions of Fibonacci, one that is linear and tail-recursive (incl. a banged variant), and another using the classic lazy-list approach:

{-# LANGUAGE BangPatterns #-}

-- Linear
fibLinear :: Int -> Integer
fibLinear 0 = 0
fibLinear 1 = 1
fibLinear x = fibLin' 2 1 2
  where
      fibLin' i y z | i == x = y
      fibLin' i y z          = fibLin' (i+1) z (z+y)

-- Linear banged
fibLinearBang :: Int -> Integer
fibLinearBang 0 = 0
fibLinearBang 1 = 1
fibLinearBang x = fibLin' 2 1 2
  where
      fibLin' (!i) (!y) (!z) | i == x = y
      fibLin' (!i) (!y) (!z)          = fibLin' (i+1) z (z+y)

-- Haskeller classic lazy
fibClassic :: Int -> Integer
fibClassic n = fib' !! n
    where fib' = 0:1:zipWith (+) fib' (tail fib')

When using criterion to benchmark it (code), I get somewhat unintuitive results: Fib 30 takes 443.0 ns for fibLinear and 279.5 ns for fibLinearBang, vs 73.51 ns for fibClassic. This is strange because I would think fibLinear & fibLinearBang could be optimised into something like a loop or a jump.

My only guess is maybe fib' in fibClassic is memoised as a constant list despite being inside a function definition so that subsequent invocations of the function reuse the same list for lookup.

Can someone give me a definitive explanation for my benchmark results?

For those interested, I've put the project on Github.

Upvotes: 2

Views: 703

Answers (1)

lloydmeta
lloydmeta

Reputation: 1339

tl;dr: fib' was indeed reused across invocations

Thanks to the commenters, I've learnt that full-laziness is not (just) a term used to describe how Haskell evaluates, but an actual compiler optimisation term, one that is on by default, but can be disabled (by using the -fno-full-laziness GHC-option flag.

Re-running the benchmarks with that flag, we see the tables have turned:

  • fibLinearBang 259.8 ns
  • fibClassic 738.4 ns

This performance, along with this guide on GHC compiler options is pretty compelling evidence that fib' does get transformed into something like a top-level reference that is reused (and being a list, memoised) across different invocations of the method.

Both that guide and the paper it links to describing let-lifting admit that let-lifting could result in increased memory residency, which to me is somewhat scary (do not write a fib-as-a-service using fibClassic and expose it to the internet...), but I might come around to it..

Upvotes: 0

Related Questions