Simple Ruby Memoization

Primer; from Wiki:

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

TL;DR: 41 times faster on my ruby game using below code

Object.class_eval do
  def memoized!(*identifier)
    memoized = (
      instance_variable_get(:@memoized) ||
        instance_variable_set(:@memoized, {})
    )
    memoized[identifier] = yield unless memoized.has_key? identifier
    memoized[identifier]
  end
end

…to wrap any of your “cache-able” code. In particular, my 41x speed gain, was resulted from wrapping below:

# block.rb
class Block
  attr_accessor :top_texture, :bot_texture
  
  def render
    Rubuild::Texture.new_from_render(
      width: SIZE,
      height: SIZE
    ) do
      top_texture.draw(x: 0, y: 0, width: SIZE, height: SIZE / 2)
      bot_texture.draw(x: 0, y: SIZE / 2, width: SIZE, height: SIZE / 2)
    end
  end
  # ...
end

…into…

# block.rb
class Block
  attr_accessor :top_texture, :bot_texture
    
  def render
    Block.memoized!(:render, top_texture, bot_texture) do
      Rubuild::Texture.new_from_render(
        width: SIZE,
        height: SIZE
      ) do
        top_texture.draw(x: 0, y: 0, width: SIZE, height: SIZE / 2)
        bot_texture.draw(x: 0, y: SIZE / 2, width: SIZE, height: SIZE / 2)
      end
    end
  end
  # ...
end

To explain what’s happening above, see animation below first for context:

… I have 8165 “grass” blocks being rendered on the screen (only once and gets cached), and each block will be called therender method on it which you could see in my code above. Without memoization, each block would always have to render a texture for both the “top half part” (grass) and “bottom half part” (dirt) of the block, thereby slowing down the application unnecessarily. Before memoization, the “Drawing World…” portion (black screen in the animation above) took ~12 seconds using benchmark . Now it just took 0.28 seconds. That’s a huuuuuge gain! :)

Now, there’s an easier popular way to do memoization in ruby as you probably already know; using the ||= operator like below:

def total_doge_count
  @total_doge_count ||= (
    # perform some heavy calculation
    # ...
  )
end

…which I use all the time, but have to be always wary of “boolean” values, as ||= wouldn’t work with false values because ||= is just a shorthand for

def total_doge_count
  @total_doge_count = @total_doge_count || (
    # perform some heavy calculation
    # ...
  )
end

…Now, to also be able to memoize false and true values, you’ll need to do something like below instead:

def foo
  @foo = true if @foo.nil?
end

… which (aside from just repeating the code @foo above) is still very simple right? So, then why use my memoized! extension? 2 reasons:

Flexibility

In my example, notice I am passing multiple arguments to memoized! :

def render
  Block.memoized!(:render, top_texture, bot_texture) do
    some_value_to_be_cached
  end
end

Above can be translated into:

Get the cached value stored in Block that uniquely matches the following pattern: :texturethen top_texture object, and bot_texture object. And if no cached value yet, then perform do … end , and memoize / cache the return value of this block for this particular pattern.

This makes this a lot more flexible as top_texture and bot_texture can dynamically change, but will be cached independently for each different objects. Without this memoized! helper, you’d probably do something like below which gets lengthy and a bit unsightly!

def render
  identifier = :"@memoized_#{top_texture.object_id}_#{bot_texture.object_id}
  if Block.instance_variable_defined? identifier
    Block.instance_variable_get identifier
  else
    Block.instance_variable_set identifier, some_value_to_be_cached
  end
end

Context Switching

Allows you to control which “objects” you want to store the cache. Because the memoized! method is defined or extended to the root Object class, then you can basically call .memoize! to any object you use in Ruby! Case in point, you can call .memoize to both instance and class-instance objects, and they are treated independently:

Block.memoized!(:foo) { 'bar' }
block = Block.new
block.memoized!(:foo) { 'baz' }
puts Block.memoized!(:foo)
# => 'bar'
puts block.memoized!(:foo)
# => 'baz'

You can also use .memoized! in arrays, hashes, integers, everything! :)

my_anime_list = ['Code Geass', 'Clannad', 'Silent Voice']
my_anime_list.memoized(:list_of) { 'Jules' }
puts my_anime_list.memoized(:list_of)
# => 'Jules'

Extra Features:

Object.class_eval do
  def memoized!(*identifier)
    memoized = (
      instance_variable_get(:@memoized) ||
        instance_variable_set(:@memoized, {})
    )
    memoized[identifier] = yield unless memoized.has_key? identifier
    memoized[identifier]
  end
  def memoized_with_object!(*identifier, &block)
    memoized = (
      instance_variable_get(:@memoized) ||
        instance_variable_set(:@memoized, {})
    )
    memoized[identifier] = instance_exec(&block) unless memoized.has_key? identifier
    memoized[identifier]
  end
  
  def memoized_thread_safe!(*identifier)
    Thread.current(:memoized) ||= {}
    Thread.current(:memoized)[identifier] = yield unless Thread.current(:memoized).has_key? identifier
    Thread.current(:memoized)[identifier]
  end
end

• You can also use memoized_with_object! if you want a simple chain of methods to be called:

# say you want to memoize the following:
SuperGame::Block.name.split('::').map(&:underscore)
# then you can do
SuperGame::Block.memoized_with_object!(:directory_path) { name.split('::').map(&:underscore) }
puts SuperGame::Block.memoized!(:directory_path)
# => ['super_game', 'block']

• Also you can use memoized_thread_safe! if you want the values to not be shared across different threads. You may or may not want to do this intentionally. For example in my case above, I intended Block.memoized!(:render, top_texture, bot_texture)to be shared across all threads.

Unobtrusive Alternative Way

The original code above would store an instance variable @memoized to the called object, which works perfectly, but for certain classes you implement where the list of instance variables affect application behaviour, you do not want to pollute the instance variables of an object. You’d want to use something like below instead, which stores the cache into a global Memoized.cache

module Memoized
  singleton_class.attr_accessor :cache
  @cache = (
    instance_variable_get(:@cache) ||
      instance_variable_set(:@cache, {})
  )
end
Object.class_eval do
  def memoized!(*identifier)
    object_cache = Memoized.cache[self] ||= {}
    object_cache[identifier] = yield unless object_cache.has_key? identifier
    object_cache[identifier]
  end
end