Nuby Tip for the Day : Memoization

ruby-talk
1

So you have written your ruby app.

It works.

So you throw it at a really Big Problem....and it grinds to a
halt. Too slow, too much memory.

If I find I that keep recreating an object, here is a trick that I
sometimes play...

Replace...

···

-------------
   class BigExpensiveMadeOften
     def initialize( unique_name)
       # Big expensive computation
     end
   end
   .
   # Some Inner Loop
   bem = BigExpensiveMadeOften.new( unique_name)
-------------
with...
   class BigExpensiveMadeOften
     def initialize( unique_name)
       # Big expensive computation
     end

    @@memo = Hash.new {|hash,key|
         result = BigExpensiveMadeOften.new( unique_name)
         hash[key] = result
     }

     def BigExpensiveMadeOften.create( unique_name)
       return @@memo[unique_name]
     end
   end
   .
   # Some Inner Loop
   bem = BigExpensiveMadeOften.create( unique_name)
-------

and hey presto, instead of recreating a BigExpensiveMadeOften object
every time, it just immediately returns one of them out of the memo cache.

Really an easy optimization to do.

John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@tait.co.nz
New Zealand

The universe is absolutely plastered with the dashed lines exactly one
space long.

2

Just a little correction to a worthy post...

John Carter wrote:
...

  class BigExpensiveMadeOften
    def initialize( unique_name)
      # Big expensive computation
    end

   @@memo = Hash.new {|hash,key|
        result = BigExpensiveMadeOften.new( unique_name)

                                               ^^^^^^^^^^^
                                             should be "key"

3

Yep. You could also make it transparent for the clients of your class:

class BigExpensiveMadeOften
  def initialize(unique_name)
    # Big expensive computation
  end

  @@memo = Hash.new { |hash,key|
    result = BigExpensiveMadeOften.allocate
    result.__send__(:initialize, key)
    hash[key] = result
  }

  def BigExpensiveMadeOften.new(unique_name)
    @@memo[unique_name]
  end
end

foo = BigExpensiveMadeOften.new('foo')
bar = BigExpensiveMadeOften.new('bar')
p foo
p bar
foo = BigExpensiveMadeOften.new('foo')
p foo

···

On 2004-11-01 12:58:27 +0900, John Carter wrote:

Really an easy optimization to do.

--
Florian Frank

4

Just a little correction to a worthy post...

thanks

John Carter wrote:
...

  class BigExpensiveMadeOften
    def initialize( unique_name)
      # Big expensive computation
    end

make that
     @@memo = Hash.new {|hash,key| hash[key] = BigExpensiveMadeOften.new( key)}

Reminder for the day for not so Nubies...

Every reference to a string is a String.new, so sometimes factoring out string constants out of inner loops can be a big win...

(1..1000).each do |i|
   if (i % 2) == 0
     a << 'Was even'
   else
     a << 'Was odd'
end

Creates 500 indentical instances of 'Was even' and 500 identical instances of 'Was odd'

EVEN_MSG = 'Was even'
ODD_MSG = 'Was odd'

(1..1000).each do |i|
   if (i % 2) == 0
     a << EVEN_MSG
   else
     a << ODD_MSG
end

Saves you 998 strings

=======foo.rb==========
a=
(1..1000).each do |i|
   a << 'This is a great big string'
end

p a[100]
a[100][0] = 32

p a[99]
p a[100]
p a[101]

b = "This is an long string"

a=
(1..1000).each do |i|
   a << b
end

p a[100]
a[100][0] = 32

p a[99]
p a[100]
p a[101]

···

On Mon, 1 Nov 2004, Joel VanderWerf wrote:

ruby -w foo.rb
"This is a great big string"
" his is a great big string"
"This is a great big string"
"This is an long string"
" his is an long string"

John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@tait.co.nz
New Zealand

The universe is absolutely plastered with the dashed lines exactly one
space long.

5

Florian Frank ha scritto:

···

On 2004-11-01 12:58:27 +0900, John Carter wrote:

Really an easy optimization to do.

Yep. You could also make it transparent for the clients of your class:

and you can write your own memoize() method or Memoized class, to transform a method/class into what you want transparently

6

Possibly you meant a string literal. A reference is what the variable
ends up holding.

Brian Mitchell

···

On Mon, 1 Nov 2004 14:01:34 +0900, John Carter <john.carter@tait.co.nz> wrote:

On Mon, 1 Nov 2004, Joel VanderWerf wrote:

> Just a little correction to a worthy post...

thanks

> John Carter wrote:
> ...
>> class BigExpensiveMadeOften
>> def initialize( unique_name)
>> # Big expensive computation
>> end
>>

make that
     @@memo = Hash.new {|hash,key| hash[key] = BigExpensiveMadeOften.new( key)}

Reminder for the day for not so Nubies...

Every reference to a string is a String.new, so sometimes factoring out string constants out of inner loops can be a big win...

7

This is how I did it:

  http://ntecs.de/blog/Blog/PerformanceQuantenSprung.rdoc

I think Robert Feldt's implementation in AspectR (?) is much more
advanced, in that each class can have it's own cache.

Regards,

  Michael

···

On Mon, Nov 01, 2004 at 06:33:50PM +0900, gabriele renzi wrote:

Florian Frank ha scritto:
>On 2004-11-01 12:58:27 +0900, John Carter wrote:
>
>>Really an easy optimization to do.
>
>
>Yep. You could also make it transparent for the clients of your class:

and you can write your own memoize() method or Memoized class, to
transform a method/class into what you want transparently