Memoization in Ruby

Memoization is the term for caching operations in order to reuse them; by storing operations in memory it allows us to speed up programs. Lets take a look at how to use memoization in Ruby.

Basic example

The first way to use memoization is to use Ruby’s or-equals operator.

def intensive_process
  @result ||= 10_000.times {|n| n ** n}
end

The first time this method is called, it will perform the expensive operation. However, the result will be cached so that all future method calls will get the result from memory rather than performing the calculation again.

Functional Programming

Memoization is very useful in functional programming, here is an example of how memoization can be used to speed up calculating a Fibonacci sequence. The example that I’m bench-marking here has been taken from blackbytes blog.

def fibonacci(n)
  return n if (0..1).include? n

  (fibonacci(n - 1) + fibonacci(n - 2))
end

time = Time.now
puts "fib: #{fibonacci(35)}" # => fib: 9227465
puts "seconds: #{Time.now - time}" # => seconds: 6.768906

Calculating Fibonacci’s number, for 35, takes ~6.7 seconds.Calculating Fibonacci in this way becomes slow as the input number increases because operations are being re-calculated many times. For example: fibonacci(3) may have to be re-calculated lots of times, therefore, we can use memoization to speed this up.

@cache = [0, 1]
def fibonacci(n)
  return n if (0..1).include? n
  return @cache[n] if @cache[n]

  @cache[n] = (fibonacci(n - 1) + fibonacci(n - 2))
end

time = Time.now
puts "fib: #{fibonacci(35)}"
puts "seconds: #{Time.now - time}" # => seconds: 7.1e-05

As you can see, the results are pretty amazing. It is not just faster but an order of magnitude faster.

Rails

Rails used to have ActiveRecord::Memoizable which mixes in the memoize method. This has now been deprecated but you can use the memoist gem instead.

require 'memoist'
class Pet < ActiveRecord::Base
  extend Memoist

  def breed_number
    "#{breed}#{rand(100)}"
  end
  memoize :breed_number
end

pet = Pet.first
pet.breed_number # => "lab19"
pet.breed_number # => "lab19"
pet.breed_number # => "lab19"

As you can see breed_number is calculated once and the result is cached. The return value “lab19” does not change because the rand method is not being re-evaluated.

Alternatively, if you don’t want to use the memoist gem, you could simply cache the result in a variable (using the or-equals operator).

When to use Memoization

Memoization is best suited to complex operation, pure functions and simple methods that are called many times.

Complex operations that are expensive to calculate should always be cached, if they are referenced multiple times. On the other hand, you may want to cache smaller, less expensive operations, if they are referenced a large number of times.

In order for any method to be cached it needs to be pure. That means that, given a set of inputs, the function produces the same output. Pure functions do not have any side effects that change the state of the system.

When not to use Memoization

Memoization is not suitable for values that need to change often, for example, times and dates. Memoizing a method that calculates a date means that it will return the same date every time it is called. This could lead to unexpected bugs if you are not careful.

Conclusion

Memoization is a useful tool for optimizing performance. It is best suited to complex operations that can be cached, pure functions and simple methods that are called numerous times. When using Memoization you should be wary of values that need to change (e.g. Time). Memoization is not a good fit for these types of values and could cause bugs.

Further reading