What is memoization?

Memoization is a performance optimization technique.

The idea with memoization is: “When a method invokes an expensive operation, don’t perform that operation each time the method is called. Instead, just invoke the expensive operation once, remember the answer, and use that answer from now on each time the method is called.”

Below is an example that shows the benefit of memoization. The example is a class with two methods which both return the same result, but one is memoized and one is not.

The expensive operation in the example takes one second to run. As you can see from the benchmark I performed, the memoized method is dramatically more performant than the un-memoized one.

Running the un-memoized version 10 times takes 10 seconds (one second per run). Running the memoized version 10 times takes only just over one second. That’s because the first call takes one second but the calls after that take a negligibly small amount of time.

class Product
  # This method is NOT memoized. This method will invoke the
  # expensive operation every single time it's called.
  def price
    expensive_calculation
  end

  # This method IS memoized. It will invoke the expensive
  # operation the first time it's called but never again
  # after that.
  def memoized_price
    @memoized_price ||= expensive_calculation
  end
  
  def expensive_calculation
    sleep(1)
    500
  end
end

require "benchmark"

product = Product.new
puts Benchmark.measure { 10.times { product.price } }
puts Benchmark.measure { 10.times { product.memoized_price } }

$ ruby memoized.rb
  0.000318   0.000362   0.000680 ( 10.038078)
  0.000040   0.000049   0.000089 (  1.003962)

Why is memoization called memoization?

I’ve always thought memoization was an awkward term due to its similarity to “memorization”. The obscurity of the name bugged me a little so I decided to look up its etymology.

According to Wikipedia, “memoization” is derived from the Latin word “memorandum”, which means “to be remembered”. “Memo” is short for memorandum, hence “memoization”.

When to use memoization

The art of performance optimization is a bag of many tricks: query optimization, background processing, caching, lazy UI loading, and other techniques.

Memoization is one trick in this bag of tricks. You can recognize its use case when an expensive method is called repeatedly without a change in return value.

This is not to say that every time a case is encountered where an expensive method is called repeatedly without a change in return value that it’s automatically a good use case for memoization. Memoization (just like all performance techniques) is not without a cost, as we’ll see shortly. Memoization should only be used when the benefit exceeds the cost.

As with all performance techniques, memoization should only be used a) when you’re sure it’s needed and b) when you have a plan to measure the before/after performance effect. Otherwise what you’re doing is not performance optimization, you’re just randomly adding code (i.e. incurring costs) without knowing whether the costs you’re incurring are actually providing a benefit.

The costs of memoization

The main cost of memoization is that you risk introducing subtle bugs. Here are a couple examples of the kinds of bugs to which memoization is susceptible.

Instance confusion

Memoization works if and only if the return value will always be the same. Let’s say, for example, that you have a loop that makes use of an object which has a memoized method. Maybe this loop uses the same object instance in every single iteration, but you’re under the mistaken belief that a fresh instance is used for each iteration.

In this case the value from the object in the first iteration will be correct, but all the subsequent iterations risk being incorrect because they’ll use the value from the first iteration rather than getting their own fresh values.

If this type of bug sounds contrived, it’s not. It comes from a real example of a bug I once caused myself!

Nil return values

In the example above, if expensive_calculation had been nil, then the value wouldn’t get memoized because @memoized_price would be nil and nil is falsy.

The risk of such a bug is probably low, and the consequences of the bug are probably small in most cases, but it’s a good category of bug to be aware of. An alternative solution is to use defined? rather than lazy initialization, which is not susceptible to the nil-is-falsy bug.

Understandability

Last but certainly not least, code that involves memoization is harder to follow than code that doesn’t. This is probably the biggest cost of memoization. Code that’s hard to understand is hard to change. Code that’s hard to understand provides a place for bugs to hide.

Prudence pays off

Because memoization isn’t free, it’s not a good idea to habitually add memoization to methods as a default policy. Instead, add memoization on a case-by-case basis when it’s clearly justified.

Takeaways

• Memoization is a performance optimization technique that prevents wasteful repeated calls to an expensive operation when the return value is the same each time.
• Memoization should only be added when you’re sure it’s needed and you have a plan to verify the performance difference.
• A good use case for memoization is when an expensive method is called repeatedly without a change in return value.
• Memoization isn’t free. It carries with it the risk of subtle bugs. Therefore, don’t apply memoization indiscriminately. Only use it in cases where there’s a clear benefit.