Revisiting Memoization

After revisiting the Haskell Wiki recently, I wanted to look at memoization again for a brief second after talking about it a while ago.  In particular, there were two competing ideas, one around using a generic dictionary/map for storing the memoized values, the other using a lazy list approach.  I wanted to briefly look into those as possible solutions.

The Baseline Approach

Let’s take a baseline approach, and instead of using the trite Fibonacci sequence, let’s use the Lucas Sequence instead.  It’s a slight variation on the theme, and enough to avoid that dreaded function.  The baseline should produce the following sequence: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123

It might be implemented something like this:

let rec lucas = function
  | n when n = 0I -> 2I
  | n when n = 1I -> 1I
  | n -> lucas (n - 1I) + lucas (n - 2I)

You’ll notice that F# cannot handle BigInt values as literals like you can for integers and other primitives, but can be easily worked around by using a when clause in the pattern.  When we run the aforementioned function in F# interactive, we see that we get the expected results.

> lucas 2I;;
Real: 00:00:00.003, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : bigint = 3I

The problem with the above function is that when dealing with larger numbers, and calling this function repeatedly, you have to take a rather large performance hit each time.  And worse yet, when dealing with those larger numbers say greater than 30, the function just may hang.  We can solve this through a process called memoization, which I’ve talked about before.  The main idea is to cache all values that we’ve seen before for quicker retrieval instead of calculating the value each and every time.

The LazyList Approach

There are two ways I’ll cover memoization here, one using a lazy list and the other using the dictionary approach.  First, let’s look at how we might be able to use a list to store those values we’ve already calculated.  Let’s first look at the Haskell implementation which is similar to the Haskell Wiki example. 

memoized_lucas :: Int -> Integer
memoized_lucas =
  (map lucas [0 ..] !!)
  where lucas 0 = 0
        lucas 1 = 1
        lucas n = memoized_lucas (n-2) + memoized_lucas (n-1)

The approach here is to perform a map of the lucas from 0 to infinity and taking the nth value.  Since this is partially applied, we need to wait on the last value to say which value we need.  When we run this through GHCi, we can calculate the 1000th Lucas number rather easily with me omitting the result and only checking the time:

*Main> memoized_lucas 1000
(0.03 secs, 0 bytes)

Not only that, but the performance is rather good.  Any subsequent calls to this function should now be memoized such as the following call:

*Main> memoized_lucas 1000
(0.00 secs, 0 bytes)

Now, how would we apply this to F#?  Can we get the same results as a lazy language?  If we switch over from using a list to a LazyList, the answer is yes, and the performance will be close.  First, we need to define the nth function which returns the value at the index specified.  Using pattern matching, we can then return the appropriate value, or recurse again.  We could use Seq.nth, but this may be more efficient.

module LazyList =
  open Microsoft.FSharp.Collections.LazyList

  let rec nth list index = 
    match list with 
    | Cons(h, t) when index >= 0 -> 
        if index = 0 then h else nth t (index - 1)
    | _ -> invalidArg "index" "the index was outside the range of elements in the list"

Now that we’ve defined our nth function, it’s time to define our memoized Lucas function.  The logic is the same as above, and I’ve introduced a new operator to get the nth value which could be used as an infix operator.  The problem is that F# currently does not allow for the infix operator to be in the middle during partially applied functions, so instead I have to define it in the beginning.

open System
open Microsoft.FSharp.Math
let (<!>) s (n:bigint) = LazyList.nth s (int n)

let rec memoized_lucas : bigint -> bigint =
  let lucas = function
    | n when n = 0I -> 2I
    | n when n = 1I -> 1I
    | n -> memoized_lucas (n - 1I) + memoized_lucas (n - 2I)
  (<!>) (LazyList.map lucas (seq {0I..new BigInt(Int32.MaxValue)} |> LazyList.of_seq))

This is a rather clumsy approach in some ways as we’re downcasting our bigint value to an integer, so in reality, we’re only able to get values up to Int32.MaxValue, which in most cases, should be ok. Let’s look at the performance of this in the same way we did above:

> memoized_lucas 1000I;;
Real: 00:00:00.092, CPU: 00:00:00.093, GC gen0: 15, gen1: 0, gen2: 0

You’ll notice that we are taking a slight performance penalty in terms of our Generation 0 memory in the GC.  Any subsequent calls are memoized given the following results:

> memoized_lucas 1000I;;
Real: 00:00:00.001, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0

Let’s kick it up a notch to see what kind of penalty we may pay should we calculate the 10,000th Lucas sequence number:

> memoized_lucas 10000I;;
Real: 00:00:07.922, CPU: 00:00:07.815, GC gen0: 1511, gen1: 356, gen2: 1

Ouch!  But, there is another approach that we can use and that I’ve shown before using the generic dictionary to store our values.

The Dictionary Approach

The generic dictionary approach is another approach rather than using the lazy list approach.  We simply create a dictionary outside of our inner function which stores these values from our inner Lucas sequence function. 

open System.Collections.Generic
let rec memoized_lucas' : bigint -> bigint =
  let t = new Dictionary<_,_>()
  let rec lucas n =
    match t.TryGetValue(n) with
    | (true , res) -> res
    | (false, _  ) ->
      match n with
       | n when n = 0I -> 2I
       | n when n = 1I -> 1I
       | n ->
           let res = lucas (n - 1I) + lucas (n - 2I)
           t.Add(n, res)
           res
  fun n -> lucas n

The code itself is rather self explanatory.  We have the outer dictionary to store our values, then we have the inner function to calculate the value at the nth index.  We then determine whether it is in the dictionary and, if so return it, else calculate, add to the list and then return.  You’ll notice that we return not the literal value of the calculation, but instead a function which allows us to specify the nth at a later time.  This is important!

Looking at the performance, we’ll notice the following:

> memoized_lucas' 1000I;;
Real: 00:00:00.006, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
> memoized_lucas' 1000I;;
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

You’ll notice that the first calls is less expensive than the lazy list approach and has less impact on Generation 0 of the GC.  Any subsequent calls, as above will be nil.  But once again, let’s ratchet up the number to 10,000 much as we did above: 

> memoized_lucas' 10000I;;
Real: 00:00:00.047, CPU: 00:00:00.062, GC gen0: 1, gen1: 1, gen2: 1

You’ll notice a drastically less performance hit than the above solution. 

Conclusion

If nothing else, it was an interesting exercise in seeing different ways of memoization in action and what kind of performance penalties you may pay along the way.  Now back to your regular programming…