From: James Edward Gray II <james@...>
Date: 2006-01-25T01:27:25+09:00
Subject: Rethinking Memoization

Daniel Berger and I have been having an off-list discussion about his  
memoize.rb library.  You can find that library at:

http://raa.ruby-lang.org/project/memoize/

In the course of the discussion, I ended up building a library of my  
own, to show Daniel what I was talking about.  Daniel thought it  
might be worth moving the discussion of my new library here, to get  
community feedback.

The primary difference between our two approaches is that Daniel's  
library is built to memoize individual objects, while mine is  
intended to link all instance method calls for a class of objects to  
a single cache.

I wanted this behavior because I felt it would increase cache hits  
and make memoizing methods that much more worthwhile.  Daniel pointed  
out though that a finer grained control can be important, to avoid  
exhausting memory with the cache.  Luckily, Ruby's syntax makes it  
trivial to use my library to alter a unique object as well.

Here's an example of using my library to memoize an instance method,  
the intended usage:

#!/usr/local/bin/ruby -w

# instance_methods.rb
#
#  Created by James Edward Gray II on 2006-01-23.
#  Copyright 2006 Gray Productions. All rights reserved.

require "memoizable"

class Fibonacci
   extend Memoizable

   def fib( num )
     return num if num < 2
     fib(num - 1) + fib(num - 2)
   end
   memoize :fib
end

puts "This method is memoized, and will run very fast..."
start = Time.now
puts "fib(100):  #{Fibonacci.new.fib(100)}"
puts "Run time:  #{Time.now - start} seconds"

puts
puts "All objects share a cache, so this call, is even faster..."
start = Time.now
puts "fib(100):  #{Fibonacci.new.fib(100)}"  # simple cache hit
puts "Run time:  #{Time.now - start} seconds"

__END__

Also, here is how you would use the library to affect individual  
objects:

#!/usr/local/bin/ruby -w

# singleton_objects.rb
#
#  Created by James Edward Gray II on 2006-01-23.
#  Copyright 2006 Gray Productions. All rights reserved.

require "memoizable"

class Fibonacci
   def fib( num )
     return num if num < 2
     fib(num - 1) + fib(num - 2)
   end
end

slow = Fibonacci.new

puts "This method is not memoized and thus slow..."
start = Time.now
puts "slow.fib(30):  #{slow.fib(30)}"
puts "    Run time:  #{Time.now - start} seconds"

fast = Fibonacci.new
class << fast  # memoize just this object
   extend Memoizable
   memoize :fib
end

puts
puts "We can fix that for a unique object..."
start = Time.now
puts "fast.fib(30):  #{fast.fib(30)}"
puts "    Run time:  #{Time.now - start} seconds"

puts
puts "But the original is still slow..."
start = Time.now
puts "slow.fib(30):  #{slow.fib(30)}"
puts "    Run time:  #{Time.now - start} seconds"

__END__

My library also works for class/module methods and even top-level  
methods, though I will spare you those examples.

The other difference between our libraries is that Daniel's supports  
using a file for persistent caching, while my library supports using  
a custom cache object.  That means that it's a little more work to  
cache to a file using mine, but you can do other kinds of caching as  
well.  Here's a file cache example:

#!/usr/local/bin/ruby -w

# file_persistance.rb
#
#  Created by James Edward Gray II on 2006-01-23.
#  Copyright 2006 Gray Productions. All rights reserved.

require "memoizable"

#
# A trivial implementation of a custom cache.  This cache uses disk  
storage,
# instead of a Hash in memory.  Access is slower than using an in- 
memory cache,
# though still much faster than a non-memoized method, but persistant  
between
# program runs.
#
# *WARNING*:  This implementation is not thread-safe!
#
class FileCache
   def initialize( path )
     @path = path
   end

   def []( key )
     if File.exist? @path
       File.foreach(@path) do |entry|
         return entry.split(" ").last.to_i if entry =~ /\A#{key}: /
       end
     end
     nil
   end

   def []=( key, value )
     File.open(@path, "a") { |cache| cache.puts "#{key}: #{value}" }
   end
end

class Fibonacci
   extend Memoizable

   def fib( num )
     return num if num < 2
     fib(num - 1) + fib(num - 2)
   end
   memoize :fib, FileCache.new("fib_cache.txt")
end

puts "This method is memoized using a file-based cache.  See  
fib_cache.txt..."
start = Time.now
puts "fib(100):  #{Fibonacci.new.fib(100)}"
puts "Run time:  #{Time.now - start} seconds"

puts
puts "Run again to see the file cache at work."

__END__

You can find an example using weak references and the actual library  
code in the "Memoization" section of the following article from my blog:

http://blog.grayproductions.net/articles/2006/01/20/caching-and- 
memoization

The point of posting all this here is to give people a chance to  
express concerns over my implementation.  Daniel was avoiding going  
down this road because of issues raised by this community.  Raise  
away.  ;)

If there is any interest, and we don't prove the library horribly  
broken, I would be happy to package it up.

Thanks.

James Edward Gray II