From: Mauricio Fernandez <mfp@...>
Date: 2006-01-02T20:38:08+09:00
Subject: Re: Memoization, files and Marshal?

--1yeeQ81UyVL57Vl7
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

On Sun, Jan 01, 2006 at 09:32:56PM +0900, Daniel Berger wrote:
> > sorry, don't know how that's running on linux in the first place... you need:
> >
> >    --- a.rb	2005-12-31 20:30:59.000000000 -0700
> >    +++ b.rb	2005-12-31 20:31:10.000000000 -0700
> >    @@ -1,9 +1,10 @@
> >     def memoize_to_file(name, file)
> >    +  meth = method(name)
> >       cache = Hash.new.update(Marshal.load(File.read(file))) rescue {}
> >       (class << self; self; end).class_eval do
> >          define_method(name) do |*args|
> >             unless cache.has_key?(args)
> >    -          cache[args] = method(name).call(*args)
> >    +          cache[args] = meth.call(*args)
> >               File.open(file, "wb+"){|f| Marshal.dump(cache, f) }
> >             end
> >             cache[args]
[...]
> Thanks, that did the trick nicely.  It's now part of memoize 1.2.0. :)

Dumping the cache on every miss seems expensive.
I changed the code to save it once every N misses, and made the cache update
atomic to prevent problems with:
* concurrent executions of the memoized method (processes and threads)
* no HD space being left (the previous cache state is preserved)

I also applied those changes to memoize.rb 1.2.0 and generalized it to work
with instance methods, see the patch after memo.rb.

batsman@tux-chan:/tmp$ cat memo.rb
def memoize_to_file(name, file = nil, period = -1)
  meth = method(name)
  cache = Hash.new.update(Marshal.load(File.read(file))) rescue {}
  save_cache_proc = lambda do
    tmpfile = "#{file}.#{Process.pid}"
    begin
      File.open(tmpfile, "wb+"){|f| Marshal.dump(cache, f) }
      File.rename tmpfile, file
    rescue Exception
    end
  end
  at_exit { save_cache_proc.call } if file
  calls = period
  (class << self; self; end).class_eval do
     define_method(name) do |*args|
        unless cache.has_key?(args)
          cache[args] = meth.call(*args)
          if file && period != -1 && (calls -= 1) <= 0
            calls = period
            save_cache_proc.call
          end
        end
        cache[args]
     end
  end
end

def fib(n)
 return n if n < 2
 fib(n-1) + fib(n-2)
end

def fib2(n)
 return n if n < 2
 fib2(n-1) + fib2(n-2)
end

def fib3(n)
 return n if n < 2
 fib3(n-1) + fib3(n-2)
end


memoize_to_file "fib", "fib.cache", 1
memoize_to_file "fib2", "fib2.cache"
memoize_to_file "fib3", "fib3.cache", 10
require 'benchmark'
Benchmark.bmbm(10) do |bm|
  bm.report("period 1") { fib  1000  }
  bm.report("period 10"){ fib3 1000  }
  bm.report("at_exit")  { fib2 1000  }
end
batsman@tux-chan:/tmp$ ruby memo.rb
Rehearsal ---------------------------------------------
period 1    4.030000   0.510000   4.540000 (  5.507344)
period 10   0.430000   0.060000   0.490000 (  0.570224)
at_exit     0.030000   0.000000   0.030000 (  0.039652)
------------------------------------ total: 5.060000sec

                user     system      total        real
period 1    0.000000   0.000000   0.000000 (  0.000035)
period 10   0.000000   0.000000   0.000000 (  0.000033)
at_exit     0.000000   0.000000   0.000000 (  0.000035)




The patch to memoize.rb:

--- memoize.rb.orig	2006-01-02 11:02:54.000000000 +0100
+++ memoize.rb	2006-01-02 12:31:46.000000000 +0100
@@ -1,39 +1,106 @@
 module Memoize
    MEMOIZE_VERSION = "1.2.0"
-   
+
+   def self.memoize(recv, name, file=nil, period=-1)
+      class << recv; self end.instance_eval{ instance_memoize(name, file, period) }
+   end
+
+   def memoize(name, file=nil, period=-1)
+      Memoize.memoize(self, name, file, period)
+   end
+end
+
+class Module
    # Memoize the method +name+.  If +file+ is provided, then the method results
-   # are stored on disk rather than in memory.  This consumes virtually no
-   # memory and is persistant.
-   def memoize(name, file=nil)
-      meth = method(name)
-      
+   # are stored on disk in addition to the in-memory cache.
+   def instance_memoize(name, file=nil, period=-1)
+      meth = instance_method(name)
+
       if file
          cache = Hash.new.update(Marshal.load(File.read(file))) rescue {}
       else
          cache = {}
       end
-      
-      if file
-         (class << self; self; end).class_eval do
-            define_method(name) do |*args|
-               unless cache.has_key?(args)
-                  cache[args] = meth.call(*args)
-                  File.open(file, "wb+"){|f| Marshal.dump(cache, f) }
-               end
-               cache[args]
-            end
+
+      save_cache_proc = lambda do
+         tmpfile = "#{file}.#{Process.pid}"
+         begin
+            File.open(tmpfile, "wb+"){|f| Marshal.dump(cache, f) }
+            File.rename tmpfile, file
+         rescue Exception
          end
-      else
-         (class << self; self; end).class_eval do
-            define_method(name) do |*args|
-               if cache.has_key?(args)
-                  cache[args]
-               else
-                  cache[args] ||= meth.call(*args)
-               end
+      end
+
+      at_exit { save_cache_proc.call } if file
+
+      calls = period
+      define_method(name) do |*args|
+         unless cache.has_key?(args)
+            cache[args] = meth.bind(self).call(*args)
+            if file && period != -1 && (calls -= 1) <= 0
+               calls = period
+               save_cache_proc.call
             end
          end
+         cache[args]
       end
+
       cache
    end
-end
\ No newline at end of file
+end
+
+if __FILE__ == $0
+   def fib(n)
+      return n if n < 2
+      fib(n-1) + fib(n-2)
+   end
+
+   def fib2(n)
+      return n if n < 2
+      fib2(n-1) + fib2(n-2)
+   end
+
+   def fib3(n)
+      return n if n < 2
+      fib3(n-1) + fib3(n-2)
+   end
+
+   include Memoize
+
+   module DumbFib
+      def fib(n)
+         return n if n < 2
+         fib(n-1) + fib(n-2)
+      end
+   end
+
+   DumbFib2 = DumbFib.clone
+
+   memoize :fib, "xfib.memoize.cache", 1
+   memoize :fib2, "xfib2.memoize.cache"
+   memoize :fib3, "xfib3.memoize.cache", 10
+
+   class Dummy1
+      include DumbFib
+      instance_memoize :fib, "xfib.dumb1.cache"
+   end
+   class Dummy2
+      include DumbFib2
+   end
+   module DumbFib2
+      instance_memoize :fib, "xfib.dumb2.cache"
+   end
+
+   require 'benchmark'
+   runs = 1
+   Benchmark.bmbm(10) do |bm|
+      dummy1 = Dummy1.new
+      dummy2 = Dummy2.new
+      bm.report("period 1") { runs.times{ fib  500  } }
+      bm.report("period 10"){ runs.times{ fib3 500  } }
+      bm.report("at_exit")  { runs.times{ fib2 500  } }
+      bm.report("at_exit''")  { runs.times{ dummy1.fib 500  } }
+      bm.report("at_exit'''")  { runs.times{ dummy2.fib 500  }; runs = 100000}
+   end
+
+end


batsman@tux-chan:/tmp$ ruby memoize.rb
Rehearsal ----------------------------------------------
period 1     0.870000   0.160000   1.030000 (  1.247975)
period 10    0.100000   0.010000   0.110000 (  0.151390)
at_exit      0.010000   0.000000   0.010000 (  0.034512)
at_exit''    0.020000   0.000000   0.020000 (  0.030174)
at_exit'''   0.010000   0.000000   0.010000 (  0.030094)
------------------------------------- total: 1.180000sec

                 user     system      total        real
period 1     0.490000   0.000000   0.490000 (  0.548635)
period 10    0.500000   0.000000   0.500000 (  0.539279)
at_exit      0.500000   0.000000   0.500000 (  0.562339)
at_exit''    0.490000   0.000000   0.490000 (  0.534087)
at_exit'''   0.490000   0.000000   0.490000 (  0.541301)
batsman@tux-chan:/tmp$ ruby memoize.rb
Rehearsal ----------------------------------------------
period 1     0.000000   0.000000   0.000000 (  0.000048)
period 10    0.000000   0.000000   0.000000 (  0.000019)
at_exit      0.000000   0.000000   0.000000 (  0.000017)
at_exit''    0.000000   0.000000   0.000000 (  0.000019)
at_exit'''   0.000000   0.000000   0.000000 (  0.000018)
------------------------------------- total: 0.000000sec

                 user     system      total        real
period 1     0.480000   0.000000   0.480000 (  0.533512)
period 10    0.490000   0.000000   0.490000 (  0.542617)
at_exit      0.500000   0.000000   0.500000 (  0.544705)
at_exit''    0.500000   0.000000   0.500000 (  0.551834)
at_exit'''   0.490000   0.000000   0.490000 (  0.538747)


I also attached the full sources for your convenience.

-- 
Mauricio Fernandez

--1yeeQ81UyVL57Vl7
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="memoize.rb"

module Memoize
   MEMOIZE_VERSION = "1.2.0"

   def self.memoize(recv, name, file=nil, period=-1)
      class << recv; self end.instance_eval{ instance_memoize(name, file, period) }
   end

   def memoize(name, file=nil, period=-1)
      Memoize.memoize(self, name, file, period)
   end
end

class Module
   # Memoize the method +name+.  If +file+ is provided, then the method results
   # are stored on disk in addition to the in-memory cache.
   def instance_memoize(name, file=nil, period=-1)
      meth = instance_method(name)

      if file
         cache = Hash.new.update(Marshal.load(File.read(file))) rescue {}
      else
         cache = {}
      end

      save_cache_proc = lambda do
         tmpfile = "#{file}.#{Process.pid}"
         begin
            File.open(tmpfile, "wb+"){|f| Marshal.dump(cache, f) }
            File.rename tmpfile, file
         rescue Exception
         end
      end

      at_exit { save_cache_proc.call } if file

      calls = period
      define_method(name) do |*args|
         unless cache.has_key?(args)
            cache[args] = meth.bind(self).call(*args)
            if file && period != -1 && (calls -= 1) <= 0
               calls = period
               save_cache_proc.call
            end
         end
         cache[args]
      end

      cache
   end
end

if __FILE__ == $0
   def fib(n)
      return n if n < 2
      fib(n-1) + fib(n-2)
   end

   def fib2(n)
      return n if n < 2
      fib2(n-1) + fib2(n-2)
   end

   def fib3(n)
      return n if n < 2
      fib3(n-1) + fib3(n-2)
   end

   include Memoize

   module DumbFib
      def fib(n)
         return n if n < 2
         fib(n-1) + fib(n-2)
      end
   end

   DumbFib2 = DumbFib.clone

   memoize :fib, "xfib.memoize.cache", 1
   memoize :fib2, "xfib2.memoize.cache"
   memoize :fib3, "xfib3.memoize.cache", 10

   class Dummy1
      include DumbFib
      instance_memoize :fib, "xfib.dumb1.cache"
   end
   class Dummy2
      include DumbFib2
   end
   module DumbFib2
      instance_memoize :fib, "xfib.dumb2.cache"
   end

   require 'benchmark'
   runs = 1
   Benchmark.bmbm(10) do |bm|
      dummy1 = Dummy1.new
      dummy2 = Dummy2.new
      bm.report("period 1") { runs.times{ fib  500  } }
      bm.report("period 10"){ runs.times{ fib3 500  } }
      bm.report("at_exit")  { runs.times{ fib2 500  } }
      bm.report("at_exit''")  { runs.times{ dummy1.fib 500  } }
      bm.report("at_exit'''")  { runs.times{ dummy2.fib 500  }; runs = 100000}
   end

end

--1yeeQ81UyVL57Vl7--