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.rbclass 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.rbclass 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::texture
thentop_texture
object, andbot_texture
object. And if no cached value yet, then performdo
…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 intendedBlock.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, {})
)
endObject.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