Memoize Techniques in Ruby and Rails


The headline isn’t a typo. If you haven’t heard of “memoizing”, it’s the act of caching the result of a method so that when you call the method in the future, it doesn’t have to do all the processing again. I’ll show you a few different ways to do this, along with the pros and cons of each.

Setup

Let’s setup a sample rails app to play with. I’m using Rails 3, and we’ll generate a simple model to work with:

memoize$ rails g model user first_name:string last_name:string
      invoke  active_record
      create    db/migrate/20101204003605_create_users.rb
      create    app/models/user.rb
      invoke    test_unit
      create      test/unit/user_test.rb
      create      test/fixtures/users.yml
memoize$ rake db:migrate
(in /Users/bellmyer/Desktop/bellmyer/blog/memoize)
==  CreateUsers: migrating ====================================================
-- create_table(:users)
   -> 0.0013s
==  CreateUsers: migrated (0.0014s) ===========================================

The Standard Idiom

You’ve probably seen the simplest form of memoization, whether you called it that or not. Our user model has a first_name and last_name. Let’s say we want to create a full_name method to combine the two:

class User < ActiveRecord::Base
  def full_name
    "#{first_name} #{last_name}"
  end
end

Let’s verify that it works as we expect:

memoize$ rails c
Loading development environment (Rails 3.0.1)
ruby-1.9.2-p0 > user = User.new :first_name => 'Bob', :last_name => 'Smith'
 => #<User id: nil, first_name: "Bob", last_name: "Smith", created_at: nil, updated_at: nil> 
ruby-1.9.2-p0 > user.full_name
 => "Bob Smith" 

Great! Now let’s try the simplest form of memoization:

class User < ActiveRecord::Base
  def full_name
    @full_name ||= "#{first_name} #{last_name}"
  end
end

The first time this method is called, @full_name doesn’t exist yet, so the code to the right of ||= is executed. The next time this method is called, the result of the method has already been stored in @full_name, so the method doesn’t need to recalculate it.

A Better Way

This quick-and-dirty method works well for a lot of stuff, but it doesn’t work in all cases. Let’s add another memoized method, and see if you can find the logical flaw:

  def has_full_name?
    @has_full_name ||= (!first_name.blank? && !last_name.blank?)
  end

This method checks to see if the user has both a first and last name. At first, it looks like it will work as well as our first method. But what if the result is false? @has_full_name will be set to false, which means the right side of the equation will be run from scratch each time.

Instead of checking if @has_full_name equates to true or false, we need to check if @has_full_name has been defined, like so:

  def has_full_name?
    return @has_full_name if defined?(@has_full_name)
    @has_full_name = (!first_name.blank? && !last_name.blank?)
  end

Now we’re returning @has_full_name if it exists, and evaluating it otherwise. No more true/false gotchas. This method is more reliable, but it’s not as short and sweet, I’ll admit.

Memoization with Method Arguments

What if we have a method with arguments? We usually want the same input to produce the same output. If we enter the same arguments to a method over and over, we’d expect the same return value. So why not take our memoization a step further, and add caching for methods with arguments?

  def formal_name(salutation='Mr.', suffix=nil)
    @formal_name ||= {}
    return @formal_name[[salutation, suffix]] if @formal_name.has_key?([salutation, suffix])

    @formal_name[[salutation, suffix]] = "#{salutation} #{full_name} #{suffix}"
  end

This is a bit more complicated. Since this methd can be called with different arguments, we initialize a hash to store our cached results. We use Hash’s has_key? method to check if we already have a value for the given arguments. Let’s try it out:

memoize$ rails c
user Loading development environment (Rails 3.0.1)
ruby-1.9.2-p0 > user = User.new :first_name => 'Bob', :last_name => 'Smith'
 => #<User id: nil, first_name: "Bob", last_name: "Smith", created_at: nil, updated_at: nil> 
ruby-1.9.2-p0 > user.formal_name('Mr.', 'Jr.')
 => "Mr. Bob Smith Jr." 
ruby-1.9.2-p0 > user.first_name = 'John'
 => "John" 
ruby-1.9.2-p0 > user.formal_name('Mr.', 'Jr.')
 => "Mr. Bob Smith Jr." 

You know the memoization is working, because I changed the first name, and formal_name still gave us the same answer.

Using Rails’ Memoize Module

Our “better way” is bulletproof, and we’ve even added the ability to handle method arguments. But it’s a lot of work to do this for every method, and it gunks up the readability of the method. We have to wade through the caching code to figure out what the method really does.

If you’re using Rails, 2.2 or later, you can take advantage if its Memoize module to clean this up.
Let’s add a method that uses it:

class User < ActiveRecord::Base
  extend ActiveSupport::Memoizable

  # other methods...
  
  def initials(middle_initial)
    first_name[0] + middle_initial + last_name[0]
  end
  memoize :initials
end

It’s that easy! The memoize method takes care of things for you, but you have to extend your class with the module for it to work. And unlike the other memoization strategies discussed, this uses ActiveSupport, so it’s Rails-specific.

The good news is that if you’re using Rails for your project, you can use Memoizable anywhere. Let’s add a non-activerecord class in our lib folder:

# lib/my_number.rb
class MyNumber
  extend ActiveSupport::Memoizable
  
  attr_accessor :x
  
  def initialize(x)
    @x = x
  end
  
  def plus(y)
    @x + y
  end
  memoize :plus
end

And here’s the proof that it works:

memoize$ rails c
require 'myLoading development environment (Rails 3.0.1)
ruby-1.9.2-p0 > require 'my_number'
 => ["MyNumber"] 
ruby-1.9.2-p0 > num = MyNumber.new(5)
 => #<MyNumber:0x00000104434bf8 @x=5> 
ruby-1.9.2-p0 > num.plus 2
 => 7 
ruby-1.9.2-p0 > num.x = 0
 => 0 
ruby-1.9.2-p0 > num.plus 2
 => 7 

This is a much better solution if you’re using Rails, and I highly recommend it. The less code you type by hand, the less chance of adding a bug somewhere.

Things You Should Know

First, as mentioned above, the Memoizable module is only available in ActiveSupport, part of Rails. But the previous examples are pure Ruby, and can be used in any Ruby project.

You don’t want to use memoization everywhere. Here are some situations where it’s not appropriate:

  • The method is simple, and memoizing it won’t save you much (there is some overhead involved).
  • The method’s output needs to change over the life of its object
  • The method is unlikely to be called again with the same parameters.
  • There are so many combinations of parameters that will be called, it will eat up too much memory to store all the results.
About these ads

Tags: , , , , ,

One Response to “Memoize Techniques in Ruby and Rails”

  1. Memoize техники в Ruby on Rails | Разработка на Ruby и Rails c нуля Says:

    [...] Оригинал статьи на английском: Memoize Techniques in Ruby and Rails [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: