The intricacies of implementing memoization in Ruby

In the never-ending quest to write code that is performant, we have many techniques at our disposal. One of those techniques is memoization,^{11 That’s memoization, not memorization — there’s no “r”!  which boils down to storing the results of expensive function calls, so that these expensive functions do not need to be called more than absolutely necessary.}

Many years ago, I wrote a Ruby gem for memoization, ddmemoize. It has since been superseded by better solutions, but for a long time, it was one of the best memoization libraries for Ruby out there.

Creating this library taught me a great deal. Memoization is surprisingly complex, and a proper implementation, it turns out, goes far beyond Ruby’s ||= memoization operator. Memory management and thread safety, for example, are important considerations, though often overlooked.

In this article, I’ll walk you through all the learnings I gained in the process of implementing this memoization gem.

1. Local variables
2. The memoization operator
   1. Be careful with false and nil
3. Argument-aware memoization
4. Memoization DSL
   1. Memoization requirements
5. Memoizing on frozen objects
6. Memory-efficient memoization
   1. Weak references
   2. Soft references
   3. Freezing, revisited
7. Supporting keyword arguments
8. Supporting blocks
9. Thread-safe memoization
10. Metrics
11. Conclusion

Local variables

The simplest tool at our disposal for remembering values is the concept of local variables. Trivial, perhaps — but still worth mentioning.

In the following example, the #calc_base_price function is called twice:

def total_price
  vat = calc_base_price * VAT_RATE
  calc_base_price + vat
end

If the #calc_base_price function were expensive, for example because of a database query, it would make sense to store the result in a local variable. In the following snippet, the base price is stored in a local variable called base_price:

def total_price
  base_price = calc_base_price
  vat = base_price * VAT_RATE
  base_price + vat
end

But there is certainly more to memoization than just this trivial example!

The memoization operator

Ruby comes with an operator, ||=, which is sometimes called the memoization operator. Here is an example of it in use:

def base_price
  @base_price ||= calc_base_price
end

When executing this method, Ruby will check whether the @base_price instance variable is already defined and has a value that is truthy, meaning not nil and not false. If so, it will return the value of @base_price.

If, on the other hand, @base_price is either undefined or set to nil or false, it will call the #calc_base_price method, store its return value in the @base_price instance variable, and use that value as the value for the entire expression (and thus as the return value of #base_price).

The #base_price method could be rewritten without the use of the ||= operator like this:

def base_price
  if defined?(@base_price) && @base_price
    @base_price
  else
    @base_price = calc_base_price
  end
end

However, one of the cases in which Ruby’s ||= operator does not work well is when the memo­ized method has parameters. That’s next on the list to fix.

def open?
  @is_open ||= calc_is_open
end

def open?
  if defined?(@is_open)
    @is_open
  else
    @is_open = calc_is_open
  end
end

Argument-aware memoization

Any piece of literature on the topic of memoization will inevitably bring up the Fibonacci sequence as an example where memoization is particularly useful. Here is a Ruby implementation of a function that returns a given entry in the Fibonacci sequence:

def fib(n)
  case n
  when 0
    0
  when 1
    1
  else
    fib(n - 1) + fib(n - 2)
  end
end

This works as intended: fib(6) evaluates to 8 and fib(7) evaluates to 13.

However, for larger numbers, the execution time quickly increases. I wrote some code to calculate the first 50 Fibonacci numbers, and print out the duration^{22 This code snippet uses a monotonic clock to calculate elapsed time. This is a more accurate way than using Time.now, because the monotonic clock is not affected by small shifts that occur e.g. when synchronising with a network time server.  to calculate them:}

def now
  Process.clock_gettime(
    Process::CLOCK_MONOTONIC
  )
end

50.times do |i|
  print "#{i}: "

  before = now
  val = fib(i)
  after = now
  duration = after - before

  puts "#{val} (#{format '%.1f', duration}s)"
end

Here is what it printed out:

0: 0 (0.0s)
1: 1 (0.0s)
2: 1 (0.0s)
3: 2 (0.0s)
4: 3 (0.0s)
5: 5 (0.0s)
6: 8 (0.0s)
7: 13 (0.0s)
8: 21 (0.0s)
9: 34 (0.0s)
10: 55 (0.0s)
11: 89 (0.0s)
12: 144 (0.0s)
13: 233 (0.0s)
14: 377 (0.0s)
15: 610 (0.0s)
16: 987 (0.0s)
17: 1597 (0.0s)
18: 2584 (0.0s)
19: 4181 (0.0s)
20: 6765 (0.0s)
21: 10946 (0.0s)
22: 17711 (0.0s)
23: 28657 (0.0s)
24: 46368 (0.0s)
25: 75025 (0.0s)
26: 121393 (0.0s)
27: 196418 (0.0s)
28: 317811 (0.0s)
29: 514229 (0.0s)
30: 832040 (0.1s)
31: 1346269 (0.1s)
32: 2178309 (0.2s)
33: 3524578 (0.3s)
34: 5702887 (0.5s)
35: 9227465 (0.8s)
36: 14930352 (1.2s)
37: 24157817 (2.0s)
38: 39088169 (3.2s)
39: 63245986 (5.2s)
40: 102334155 (8.3s)
41: 165580141 (13.5s)
42: 267914296 (21.8s)

Calculating number 42 in the Fibonacci sequence took 21 seconds,^{33 Did you spot how the durations form something quite close to the Fibonacci sequence, too? How neat is that?!  after which I gave up and aborted the script. Extrapolating from the durations above, I estimate that calculating number 50 in the Fibonacci sequence would take 17 minutes.44 This is assuming that the thermal throttling on my M2 MacBook Air does not engage. If it does, I imagine it would take much longer than that.} 

The reason why calculating Fibonacci numbers gets so slow is because there is a lot of redundant work happening. For example, calculating fib(40) calculates fib(39) and fib(38). Calculating fib(39) also calculates fib(38). This redundant work gets progressively worse for lower numbers. For example, fib(40) calculates the third number (n=2) in the Fibonacci sequence 63 245 986 times.

It only really needs to do that once. No wonder this implementation is slow.

One way to avoid this problem with execution speed would be to rewrite the method to avoid recursion and use looping instead:

def fib(n)
  arr = [0, 1]
  while arr.size <= n
    arr << arr.last(2).sum
  end
  arr[n]
end

The reason why this solution is so much faster is because it avoids recalculating anything. For example, fib(40) calculates the third number in the Fibonacci sequence only once — not 63 million times.

The version that uses a loop instead of recursion is much faster, but it has the problem of not being nearly as easy to read as the initial version. In this faster, recursive version, the mathematical definition of the Fibonacci sequence is not readily visible.

The #fib function cannot be memo­ized by applying the ||= operator as before. Something a little more sophisticated is needed, creating a cache for each value of the argument n:

def fib(n)
  @fib ||= {}
  @fib[n] ||=
    case n
    when 0
      0
    when 1
      1
    else
      fib(n - 1) + fib(n - 2)
    end
end

With this change, calculating fib(40) is instantaneous. In fact, so is fib(4000).^{55 Any number much larger than 8000 or so will yield a different problem: stack level too deep (SystemStackError). This is difficult, but not impossible, to avoid with a recursive solution. The version that uses a loop won’t have this issue.} 

Memoization DSL

One of Ruby’s great strengths is its capacity for metaprogramming. A good use case for this is automating memoization by tacking a call to memo­ize after a method definition, like this:

def fib(n)
  # [snip]
end
memo­ize :fib

The technique that I’ll introduce here only works for methods, not for functions. So, let’s stick #fib in a class:

class Fib
  def fib(n)
    case n
    when 0
      0
    when 1
      1
    else
      fib(n - 1) + fib(n - 2)
    end
  end
end

The invocation is a little different, but it works as before (with the same slowness):

p Fib.new.fib(10)

We’ll create a module named Memoization and stick the memo­ize method in there:

module Memoization
  def memo­ize(method_name)

Its goal will be to replace the method with the given name (:fib in our example) with a new one that performs automatic memoization. This new method needs to be able to call the original method, so it first creates a copy of the original method, using #alias_method:

    orig_method_name="__orig_" + method_name.to_s
    alias_method(orig_method_name, method_name)

In our example with #fib example, this will create a method named #__orig_fib.

The original method (#fib in our example) has not been touched yet. The next step is to redefine that original method, for which #define_method is useful. For now, it’ll use #send to call the original method; an implementation with memoization will follow later:

    define_method(method_name) do |*args|
      send(orig_method_name, *args)
    end
  end
end

To use this new functionality in our existing Fib class, first add extend Memoization near the top, and then add memo­ize :fib after the #fib method definition:

class Fib
  extend Memoization

  def fib(n)
    case n
    when 0
      0
    when 1
      1
    else
      fib(n - 1) + fib(n - 2)
    end
  end
  memo­ize :fib
end

This will still work, still without memoization (yet):

p Fib.new.fib(10)

It is now time to implement memoization in the newly defined method. The first thing it needs is a cache:

define_method(method_name) do |*args|
  @__cache ||= {}

This @__cache instance variable will contain the results of all invocations for all methods on this particular instance. The keys of the @__cache hash will be the method name.

Next, the implementation needs to get the cache for this particular method, given by the method_name variable:

  method_cache = (@__cache[method_name] ||= {})

With the cache for this particular method now available, it can check whether there is already a value for the given arguments. If there is, that is the value that can be returned — the entire point of memoization:

  if method_cache.key?(args)
    method_cache[args]

If there is no value available yet, call the original method and store the return value in the cache for this method:

  else
    method_cache[args] =
      send(orig_method_name, *args)
  end
end

In Ruby, an assignment evaluates to the value that was assigned, so there is no need for an explicit method_cache[args] after the assignment.

With this change, running fib(40) is now very fast indeed — practically instantaneous:

p Fib.new.fib(40)

There is one more neat change that is possible. In Ruby, method definitions return the mehod name as a symbol, so memo­ize can be stuck in front of the def keyword and the memo­ize :fib line removed:

memo­ize def fib(n)
  # [snip]
end

Now it looks like a keyword, which I find rather neat.

Memoization requirements

Before continuing, I want address the following question: under which circumstances can memoization be safely applied? Memoization is not a technique that can be spray-painted onto code to make it faster. There are restrictions to consider for memo­ized code to work correctly.

A memo­ized method must only use variables that never change value. This includes instance variables, arguments, global variables, constants, and more.

To illustrate this, take a look at the following example LineItem class, with a memo­ized #total_price method:^{66 The use of memoization here is not particularly useful: multiplying two numbers, count and unit_price, is very fast  — but it is appropriate as an example.} 

class LineItem
  extend Memoization

  attr_accessor :unit_price
  attr_accessor :count

  def initialize(unit_price:, count:)
    @unit_price = unit_price
    @count = count
  end

  memo­ize def total_price
    count * unit_price
  end
end

The total price is calculated correctly:

line_item = LineItem.new(unit_price: 49, count: 2)
p line_item.total_price
# => 98

However, after changing the count, the total price is not updated, because it is memo­ized:

line_item.count = 3
p line_item.total_price
# => 98

A solution to this problem is to make LineItem immutable, either by freezing it or replacing attr_accessor with attr_reader. This would prevent the count of a LineItem from being changed; instead, a new instance of LineItem can be created with the correct count:

line_item = LineItem.new(
  unit_price: 49,
  count: 2)
p line_item.total_price
# => 98

line_item = LineItem.new(
  unit_price: line_item.unit_price,
  count: 3)
p line_item.total_price
# => 147

A good general guideline is to use memoization only on objects that are immutable, and likewise pass in only arguments that are immutable as well.

Memoizing on frozen objects

There is one particular issue with this implementation. Attempting to use memoization on a frozen object fails. Take the following code as an example:

f = Fib.new
f.freeze
p f.fib(40)

This fails with a FrozenError:

example3.rb:20:in `block in memo­ize': can't modify frozen Fib: #<0x000000011ffeb008/>

­

­

­

­

­

&blk

&blk­

&&

&&&&