# Minimizing memory allocations

**URL:** <https://rubytalk.org/t/minimizing-memory-allocations/24234>\
**Category:** ruby-talk\
**Created:** [22 January 2006 14:12 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234 "2006-01-22T14:12:51Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ilmari\_Heikkinen](https://avatars.discourse-cdn.com/v4/letter/i/b9e5f3/32.png) [@Ilmari\_Heikkinen](https://rubytalk.org/u/Ilmari_Heikkinen)\
**Post date:** [22 January 2006 14:12 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/1 "2006-01-22T14:12:51Z")

</div>

So there I was this morning, staring at an ObjectSpace counter telling  
me that I'm allocating 1500 Arrays and 10000 Floats per frame. Which  
pretty much ground my framerate to ground by requiring a 0.2s GC run  
every other frame. So I decided to get down and rid my code of as many  
allocations as possible.

The first thing I discovered was a bit of code looking like this (not  
to mention that each was actually getting called several times per  
frame due to a bug):

@mtime = ([@mtime] + ([@stroke||nil,  
@fill||nil].compact+children).map{|c| c.mtime}).max

Quite unreadable, and it was responsible for a large part of the Array  
allocations too. A quick change whittled Array allocation count for  
that method to 0, with the price of making it less idiomatic:

children.each{|c|  
&nbsp;&nbsp;cm = c.mtime  
&nbsp;&nbsp;@mtime = cm if cm \> @mtime  
}  
if @stroke  
&nbsp;&nbsp;sm = @stroke.mtime  
&nbsp;&nbsp;@mtime = sm if sm \> @mtime  
end  
if @fill  
&nbsp;&nbsp;fm = @fill.mtime  
&nbsp;&nbsp;@mtime = fm if fm \> @mtime  
end

Now the Array allocations dropped down to hundreds, a much more  
reasonable number, but still way too much compared to what was  
happening in the frame. The only thing that should've changed was one  
number. So the extra 500 Arrays were a bit of a mystery.

Some investigation revealed places where I was using  
Array#each\_with\_index. Very nice, very idiomatic, very allocating a  
new Array on each iteration. So replace by the following and watch the  
alloc counts fall:

i = 0  
arr.each{|e|  
&nbsp;&nbsp;do\_stuff\_with e  
&nbsp;&nbsp;i += 1  
}

By doing that in a couple of strategic places and some other  
optimizations, the Array allocation count fell to 150. Of which 90  
were allocated in the object Z-sorting method, which'd require a C  
implementation to get its allocation count to 0. The Array allocation  
fight was heading towards diminishing returns, and my current scene  
didn't need to use Z-sorting, so I turned my attention to the Floats.

By now, the Float count had also dropped a great deal, but it was  
still a hefty 3000 Floats per frame. With each float weighing 16  
bytes, that was nearly 3MB per second when running at 60fps. Searching  
for the method that was allocating all those Floats, i ran into  
something weird. #transform was allocating 6-32 Floats per call. And  
it's one of the functions that get called for every scene object, in  
every frame. Also, it's written in C.

That left me stymied. Surely there must be some mistake, I thought,  
the C function didn't seem to be allocating \_any\_ Ruby objects. But  
little did I know.

The C function called the NUM2DBL-macro in several places to turn Ruby  
numbers into doubles. Reading the source for NUM2DBL told that it  
calls the rb\_num2dbl C function. Which takes a Ruby number and returns  
a C double. Reading the source to rb\_num2dbl revealed this:

01361 double  
01362 rb\_num2dbl(val)  
01363 VALUE val;  
01364 {  
01365 switch (TYPE(val)) {  
01366 case T\_FLOAT:  
01367 return RFLOAT(val)-\>value;  
01368  
01369 case T\_STRING:  
01370 rb\_raise(rb\_eTypeError, "no implicit conversion to float  
from string");  
01371 break;  
01372  
01373 case T\_NIL:  
01374 rb\_raise(rb\_eTypeError, "no implicit conversion to float  
from nil");  
01375 break;  
01376  
01377 default:  
01378 break;  
01379 }  
01380  
01381 return RFLOAT(rb\_Float(val))-\>value;  
01382 }

rb\_Float gets called on all Fixnums and Bignums, which there happened  
to be quite a deal of in my scene state arrays. Checking out rb\_Float  
gave the explanation for the Float allocations:

01326 switch (TYPE(val)) {  
01327 case T\_FIXNUM:  
01328 return rb\_float\_new((double)FIX2LONG(val));  
01329  
01333 case T\_BIGNUM:  
01334 return rb\_float\_new(rb\_big2dbl(val));

In order to turn a Fixnum into a double, it's allocating a new Float!  
With that figured out, I took and rewrote rb\_num2dbl as rb\_num\_to\_dbl,  
this time handling Fixnums and Bignums as special cases as well:

double rb\_num\_to\_dbl( VALUE val )  
{  
&nbsp;&nbsp;switch (TYPE(val)) {  
&nbsp;&nbsp;&nbsp;&nbsp;case T\_FLOAT:  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return RFLOAT(val)-\>value;

&nbsp;&nbsp;&nbsp;&nbsp;case T\_FIXNUM:  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return (double)FIX2LONG(val);

&nbsp;&nbsp;&nbsp;&nbsp;case T\_BIGNUM:  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return rb\_big2dbl(val);

&nbsp;&nbsp;&nbsp;&nbsp;case T\_STRING:  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rb\_raise(rb\_eTypeError, "no implicit conversion to float from string");  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break;

&nbsp;&nbsp;&nbsp;&nbsp;case T\_NIL:  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rb\_raise(rb\_eTypeError, "no implicit conversion to float from nil");  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break;

&nbsp;&nbsp;&nbsp;&nbsp;default:  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break;  
&nbsp;&nbsp;}  
&nbsp;&nbsp;return RFLOAT(rb\_Float(val))-\>value;  
}

The result? Float allocations fell to 700 per frame from the original  
3000. And now I'm getting a GC run "only" every 36 frames. Not perfect  
by any means, but a decent start.

Have stories of your own? Tips for memory management? Ways to track  
allocations? Post them, please.

Cheers,  
Ilmari

---

<div class="post-metadata">

**Author:** ![Eero\_Saynatkari1](https://avatars.discourse-cdn.com/v4/letter/e/46a35a/32.png) [@Eero\_Saynatkari1](https://rubytalk.org/u/Eero_Saynatkari1)\
**Post date:** [22 January 2006 15:34 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/2 "2006-01-22T15:34:41Z")

</div>

Ilmari Heikkinen wrote:

> So there I was this morning, staring at an ObjectSpace counter telling  
> me that I'm allocating 1500 Arrays and 10000 Floats per frame. Which  
> pretty much ground my framerate to ground by requiring a 0.2s GC run  
> every other frame. So I decided to get down and rid my code of as many  
> allocations as possible.
> 
> \< snip due to ruby-forum restrictions /\>
> 
> In order to turn a Fixnum into a double, it's allocating a new Float!  
> With that figured out, I took and rewrote rb\_num2dbl as rb\_num\_to\_dbl,  
> this time handling Fixnums and Bignums as special cases as well:
> 
> \< snip /\>
> 
> The result? Float allocations fell to 700 per frame from the original  
> 3000. And now I'm getting a GC run "only" every 36 frames. Not perfect  
> by any means, but a decent start.

Nice! I wonder if this would be eligible for core patching?

> Have stories of your own? Tips for memory management? Ways to track  
> allocations? Post them, please.

Nope, but I enjoyed reading this one, thanks!

> Cheers,  
> Ilmari

E

> **···**
>
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Ilmari\_Heikkinen](https://avatars.discourse-cdn.com/v4/letter/i/b9e5f3/32.png) [@Ilmari\_Heikkinen](https://rubytalk.org/u/Ilmari_Heikkinen)\
**Post date:** [22 January 2006 15:54 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/3 "2006-01-22T15:54:08Z")

</div>

Argh, sorry, magnitude error. The correct GC run time is 0.02s. Not so  
bad, but still a 60fps -\> 20fps glitch.

> **···**
>
> On 1/22/06, Ilmari Heikkinen \<ilmari.heikkinen@gmail.com\> wrote:
> 
> > pretty much ground my framerate to ground by requiring a 0.2s GC run

---

<div class="post-metadata">

**Author:** ![John\_Carter](https://avatars.discourse-cdn.com/v4/letter/j/2bfe46/32.png) [@John\_Carter](https://rubytalk.org/u/John_Carter)\
**Post date:** [23 January 2006 03:14 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/4 "2006-01-23T03:14:56Z")

</div>

> The result? Float allocations fell to 700 per frame from the original  
> 3000. And now I'm getting a GC run "only" every 36 frames. Not perfect  
> by any means, but a decent start.

Good Stuff.

> Have stories of your own? Tips for memory management? Ways to track  
> allocations? Post them, please.

Ok, here goes...

Useful trick one...

Just because Ruby has GC, doesn't mean it knows what is Garbage, merely what isn't currently referenced.

ie. Remember to actively drop references you will never need via things like...

&nbsp;&nbsp;&nbsp;$big\_hairy\_global = nil  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;or  
&nbsp;&nbsp;&nbsp;@fat\_instance\_variable = nil

Trick Two...

Memoization

class Foo  
&nbsp;&nbsp;&nbsp;def initialize( thing)  
&nbsp;&nbsp;&nbsp;end  
end

foo = Foo.new( thing)

becomes...

class Foo  
&nbsp;&nbsp;&nbsp;@@memo = Hash.new{|hash,key| hash[key] = Foo.new( key)}

&nbsp;&nbsp;&nbsp;def create\_foo( thing)  
&nbsp;&nbsp;&nbsp;&nbsp;@@memo[thing]  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def initialize( thing)  
&nbsp;&nbsp;&nbsp;end

end

foo = Foo.create\_foo( thing)

Trick 3

Sometimes it doesn't pay to iterate over each line.

Sometimes just read the whole ruddy file in in one bang shoot and regex over the whole thing.

ie. Instead of...  
open( 'foo.txt') do |inf|  
&nbsp;&nbsp;&nbsp;inf.each\_line do |line|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;line.chomp!  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if line =~ /thingy/  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# do stuff  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;end  
end

Try...

IO.read( 'foo.txt').scan(/thingy/){ #do stuff}

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

Carter's Clarification of Murphy's Law.

"Things only ever go right so that they may go more spectacularly wrong later."

From this principle, all of life and physics may be deduced.

> **···**
>
> On Sun, 22 Jan 2006, Ilmari Heikkinen wrote:

---

<div class="post-metadata">

**Author:** ![Gavin\_Kistner2](https://avatars.discourse-cdn.com/v4/letter/g/b9e5f3/32.png) [@Gavin\_Kistner2](https://rubytalk.org/u/Gavin_Kistner2)\
**Post date:** [22 January 2006 17:12 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/5 "2006-01-22T17:12:35Z")

</div>

In a completely separate world (Lua code running under a scene graph written in C++; no Ruby anywhere) I recently hit a place where I thought I needed to allocate ~200 Vector objects per frame.

(I was using a recursive function to calculate 3D bezier curves[1], which needed to allocate and preserve 4 new Vector objects each call.)

It was causing noticeable lurching when the GC kicked in occasionally. I found two interesting things:

1) Running Lua's GC manually \*every frame\* resulted in better memory performance and faster overall framerate than running it every 2 or 10 or 50 or 100 frames. My only (lame) guess was that waiting longer yielded a larger memory pool too wade through when looking for items to GC. (?)

2) Because I really didn't need to preserve the 200 Vectors from frame to frame (the final results of the recursive calculation were copied into the position vectors for points on the line), I was able to remove the per-frame memory allocations altogether by abstracting the Vector allocation into a pooled-vector manager. Doing this gave me far-better frame rates than I was getting with the GC-every-frame approach.

This isn't applicable specifically to Ruby, but applicable generally: when you can't remove memory allocations, see if you can at least re-use them.

In an attempt to make this post Ruby-specific, I give you a pooled object manager that I've just written, based on the Lua version I wrote at work. You create a pool by specifying an object that is the template/factory, and a method to call on that object (defaults to 'new'). Every time you ask for an object, it will hand you one from the pool, or create a new instance. The #reset method makes all items in the pool re-usable again (i.e. call at the start of a new frame).

class ObjectPool  
&nbsp;&nbsp;&nbsp;def initialize( template, method=:new, template\_in\_pool=false )  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@template = template  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@method = method  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@pool =   
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if template\_in\_pool  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@pool \<\< template  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;reset  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;# Make all items in the pool available again  
&nbsp;&nbsp;&nbsp;def reset  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@next\_available = 0  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;# Remove references to all items not currently in use  
&nbsp;&nbsp;&nbsp;def drain  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@pool[@next\_available..-1] = nil  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;# Return a new item from the pool, creating a new one if needed  
&nbsp;&nbsp;&nbsp;def next  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;unless item = @pool[@next\_available]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@pool \<\< ( item = @template.send( @method ) )  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@next\_available = @next\_available + 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;item  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def inspect  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"\<ObjectPool of #{@pool.size} #{@template}\>"  
&nbsp;&nbsp;&nbsp;end  
end

class Vector  
&nbsp;&nbsp;&nbsp;attr\_accessor :x, :y, :z  
&nbsp;&nbsp;&nbsp;def initialize( x=0, y=0, z=0 ) @x, @y, @z = x,y,z end  
&nbsp;&nbsp;&nbsp;def clone() self.class.new( @x, @y, @z ) end  
&nbsp;&nbsp;&nbsp;def inspect() "\<Vector:0x#{object\_id.to\_s(16)} #@x,#@y,#@z\>" end  
end

> **···**
>
> On Jan 22, 2006, at 8:54 AM, Ilmari Heikkinen wrote:
> 
> > On 1/22/06, Ilmari Heikkinen \<ilmari.heikkinen@gmail.com\> wrote:
> > 
> > > pretty much ground my framerate to ground by requiring a 0.2s GC run
> > 
> > Argh, sorry, magnitude error. The correct GC run time is 0.02s. Not so  
> > bad, but still a 60fps -\> 20fps glitch.
> 
> ##################################################################  
> # Showing how to create a pool of class instances  
> ##################################################################  
> pool = ObjectPool.new( Vector )  
> p pool  
> #=\> \<ObjectPool of 0 Vector\>
> 
> 3.times{ |i|  
> &nbsp;&nbsp;&nbsp;v = pool.next  
> &nbsp;&nbsp;&nbsp;v.x = v.y = v.z = i  
> &nbsp;&nbsp;&nbsp;p v  
> }  
> #=\> \<Vector:0x195518 0,0,0\>  
> #=\> \<Vector:0x195392 1,1,1\>  
> #=\> \<Vector:0x19520c 2,2,2\>
> 
> p pool  
> #=\> \<ObjectPool of 3 Vector\>
> 
> pool.reset  
> 3.times{ p pool.next }  
> #=\> \<Vector:0x195518 0,0,0\>  
> #=\> \<Vector:0x195392 1,1,1\>  
> #=\> \<Vector:0x19520c 2,2,2\>
> 
> p pool  
> #=\> \<ObjectPool of 3 Vector\>
> 
> ##################################################################  
> # Showing how to create a pool based off of a template object  
> ##################################################################  
> v = Vector.new( 1, 2, 3 )  
> pool2 = ObjectPool.new( v, :clone, true )  
> p pool2  
> #=\> \<ObjectPool of 1 #\<Vector:0x32ad64\>\>
> 
> 3.times{ p pool2.next }  
> #=\> \<Vector:0x1956b2 1,2,3\>  
> #=\> \<Vector:0x194672 1,2,3\>  
> #=\> \<Vector:0x1944ec 1,2,3\>
> 
> pool2.reset  
> 3.times{ p pool2.next }  
> #=\> \<Vector:0x1956b2 1,2,3\>  
> #=\> \<Vector:0x194672 1,2,3\>  
> #=\> \<Vector:0x1944ec 1,2,3\>
> 
> p pool2  
> #=\> \<ObjectPool of 3 #\<Vector:0x32ad64\>\>
> 
> [1] [http://www.antigrain.com/research/adaptive\_bezier/index.html#toc0003](http://www.antigrain.com/research/adaptive_bezier/index.html#toc0003)

---

<div class="post-metadata">

**Author:** ![Dave\_Howell2](https://avatars.discourse-cdn.com/v4/letter/d/7ab992/32.png) [@Dave\_Howell2](https://rubytalk.org/u/Dave_Howell2)\
**Post date:** [26 January 2006 17:44 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/6 "2006-01-26T17:44:11Z")

</div>

Er, um, huh?

All foo-links are tapping into a global-to-class hash called @@memo. OK...  
Foo.new has been rendered useless, apparently torturing anybody who forgets by returning nil as a non-error?  
Foo.create\_foo(thing) does, well, I have no idea. What's "thing" supposed to be? And why is create\_foo using square brackets?

Sigh. Sometimes Ruby is \*too\* idiomatic.

What \*is\* "memo-ization?"

> **···**
>
> On Jan 22, 2006, at 19:14, John Carter wrote:
> 
> > Trick Two...
> > 
> > Memoization
> > 
> > class Foo  
> > &nbsp;&nbsp;def initialize( thing)  
> > &nbsp;&nbsp;end  
> > end
> > 
> > foo = Foo.new( thing)
> > 
> > becomes...
> > 
> > class Foo  
> > &nbsp;&nbsp;@@memo = Hash.new{|hash,key| hash[key] = Foo.new( key)}
> > 
> > &nbsp;&nbsp;def create\_foo( thing)  
> > &nbsp;&nbsp;&nbsp;@@memo[thing]  
> > &nbsp;&nbsp;end
> > 
> > &nbsp;&nbsp;def initialize( thing)  
> > &nbsp;&nbsp;end
> > 
> > end
> > 
> > foo = Foo.create\_foo( thing)

---

<div class="post-metadata">

**Author:** ![Interfecus](https://avatars.discourse-cdn.com/v4/letter/i/d78d45/32.png) [@Interfecus](https://rubytalk.org/u/Interfecus)\
**Post date:** [24 January 2006 15:45 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/7 "2006-01-24T15:45:41Z")

</div>

I don't know anything about Lua, but Ruby is unlikely to see and speed  
benefits from garbage collecting every frame unless you're deep in  
swap. Ruby uses a "mark and sweep" garbage collection scheme, which I  
believe means that garbage collecting time is mostly proportional to  
the number of current, referenced objects, not the amount of junk left  
behind.

---

<div class="post-metadata">

**Author:** ![MenTaLguY1](https://avatars.discourse-cdn.com/v4/letter/m/97f17d/32.png) [@MenTaLguY1](https://rubytalk.org/u/MenTaLguY1)\
**Post date:** [26 January 2006 18:16 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/8 "2006-01-26T18:16:42Z")

</div>

Quoting Dave Howell \<groups@grandfenwick.net\>:

> Sigh. Sometimes Ruby is \*too\* idiomatic.
> 
> What \*is\* "memo-ization?"

It isn't actually a ruby-specific term:

> **[Memoization](https://en.wikipedia.org/wiki/Memoization)**
>
> In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls to pure functions and returning the cached result when the same inputs occur again. Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually recursive descent parsing. It is a type of caching, distinct from other forms of caching such as buffering and page replacement. Th...

-mental

---

<div class="post-metadata">

**Author:** ![John\_Carter](https://avatars.discourse-cdn.com/v4/letter/j/2bfe46/32.png) [@John\_Carter](https://rubytalk.org/u/John_Carter)\
**Post date:** [26 January 2006 20:59 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/9 "2006-01-26T20:59:02Z")

</div>

I sense deep confuzzlement so let's take that a lot slower.

OK, so this trick cannot be used everywhere. For example if I ask you to give me a new pink car, I expect you to go off, build a new car, paint it pink and give it to me. If are ask you again, I expect you to do it again and give me another (different) brand new pink car.

Suppose in the particular application I had I didn't really care it was a different one, I just wanted a pink car NOW, fast. If it's the same one as you gave me last time, in this particular application, I don't care so long as it isn't blue. I could have kept hold of the old pink car, but that's too much work, sometimes I use green, sometimes red cars, sometimes pink. This is a garbage collected system, so it's easier for me grab a new pink car when I need one than to keep track of my old ones.

This form of memo-ization is just to skip the "new" when I already have made one pink car, and just give exactly the same one as I made last time.

Ok, now the little idiomatic bit.

Suppose @@memo is a brand spanking new empty Hash object.

What does @@memo["pink"] return?

By default it returns nil.

But you can make it return whatever you damn well feel like.

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

@@memo["pink"]

Will say, oo, I have no "pink" element, I better go off and make one then, fortunately I have a block on my "new" so I know how to do that.

ps.

If everybody in your country had a pink car, what would you have?

Answer:

A Pink Carnation.

Ok, so using pink cars was a "blooming" silly example... :-))

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

Carter's Clarification of Murphy's Law.

"Things only ever go right so that they may go more spectacularly wrong later."

From this principle, all of life and physics may be deduced.

> **···**
>
> On Fri, 27 Jan 2006, Dave Howell wrote:
> 
> > On Jan 22, 2006, at 19:14, John Carter wrote:
> > 
> > > Trick Two...
> > > 
> > > Memoization
> > > 
> > > class Foo  
> > > &nbsp;&nbsp;def initialize( thing)  
> > > &nbsp;&nbsp;end  
> > > end
> > > 
> > > foo = Foo.new( thing)
> > > 
> > > becomes...
> > > 
> > > class Foo  
> > > &nbsp;&nbsp;@@memo = Hash.new{|hash,key| hash[key] = Foo.new( key)}
> > > 
> > > &nbsp;&nbsp;def create\_foo( thing)  
> > > &nbsp;&nbsp;&nbsp;@@memo[thing]  
> > > &nbsp;&nbsp;end
> > > 
> > > &nbsp;&nbsp;def initialize( thing)  
> > > &nbsp;&nbsp;end
> > > 
> > > end
> > > 
> > > foo = Foo.create\_foo( thing)
> > 
> > Er, um, huh?
> > 
> > All foo-links are tapping into a global-to-class hash called @@memo. OK...  
> > Foo.new has been rendered useless, apparently torturing anybody who forgets by returning nil as a non-error?  
> > Foo.create\_foo(thing) does, well, I have no idea. What's "thing" supposed to be? And why is create\_foo using square brackets?
> > 
> > Sigh. Sometimes Ruby is \*too\* idiomatic.
> > 
> > What \*is\* "memo-ization?"

---

<div class="post-metadata">

**Author:** ![Paul\_Brannan](https://avatars.discourse-cdn.com/v4/letter/p/76d3ee/32.png) [@Paul\_Brannan](https://rubytalk.org/u/Paul_Brannan)\
**Post date:** [26 January 2006 15:55 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/10 "2006-01-26T15:55:34Z")

</div>

The marking time is proportional to the number of referenced objects,  
and the sweeping time is proportional to the number of objects that get  
swept. In general, the longer the time between sweeps, the more objects  
need to be swept.

Invoking the GC every frame probably won't improve average frame rate,  
but it may help decrease the variance of the time it takes to process  
each frame (so you get more consistent performance).

Paul

> **···**
>
> On Wed, Jan 25, 2006 at 12:45:41AM +0900, Timothy Goddard wrote:
> 
> > I don't know anything about Lua, but Ruby is unlikely to see and speed  
> > benefits from garbage collecting every frame unless you're deep in  
> > swap. Ruby uses a "mark and sweep" garbage collection scheme, which I  
> > believe means that garbage collecting time is mostly proportional to  
> > the number of current, referenced objects, not the amount of junk left  
> > behind.

---

<div class="post-metadata">

**Author:** ![Dave\_Howell2](https://avatars.discourse-cdn.com/v4/letter/d/7ab992/32.png) [@Dave\_Howell2](https://rubytalk.org/u/Dave_Howell2)\
**Post date:** [26 January 2006 19:48 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/11 "2006-01-26T19:48:59Z")

</div>

I didn't think it was. That's why the comment and the question are in separate paragraphs.

I might be able to guess what it is if I could read the Ruby code. But I can't figure out what the code does.

> **···**
>
> On Jan 26, 2006, at 10:16, mental@rydia.net wrote:
> 
> > Quoting Dave Howell \<groups@grandfenwick.net\>:
> > 
> > > Sigh. Sometimes Ruby is \*too\* idiomatic.
> > > 
> > > What \*is\* "memo-ization?"
> > 
> > It isn't actually a ruby-specific term:

---

<div class="post-metadata">

**Author:** ![Dave\_Howell2](https://avatars.discourse-cdn.com/v4/letter/d/7ab992/32.png) [@Dave\_Howell2](https://rubytalk.org/u/Dave_Howell2)\
**Post date:** [26 January 2006 21:18 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/12 "2006-01-26T21:18:18Z")

</div>

Ha ha. Except that if everybody in my country had a Car.create\_car("pink") car, then the entire country would have exactly one car. I can't figure out what it's good for; any example I can think of in my head is just a complicated way of doing something simple. Either "well, I'll just keep the object around in the first place," or "no, I would have to have my very OWN pink car, not be FlexCar-ing it with other parts of the program"

> **···**
>
> On Jan 26, 2006, at 12:59, John Carter wrote:
> 
> > OK, so this trick cannot be used everywhere.
> > 
> > Suppose @@memo is a brand spanking new empty Hash object.
> > 
> > What does @@memo["pink"] return?
> > 
> > By default it returns nil.
> > 
> > But you can make it return whatever you damn well feel like.
> > 
> > @@memo = Hash.new{|hash,key| hash[key] = Car.new(key)}
> > 
> > @@memo["pink"]
> > 
> > Will say, oo, I have no "pink" element, I better go off and make one then, fortunately I have a block on my "new" so I know how to do that.
> > 
> > ps.
> > 
> > If everybody in your country had a pink car, what would you have?

---

<div class="post-metadata">

**Author:** ![John\_Carter](https://avatars.discourse-cdn.com/v4/letter/j/2bfe46/32.png) [@John\_Carter](https://rubytalk.org/u/John_Carter)\
**Post date:** [26 January 2006 23:08 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/13 "2006-01-26T23:08:56Z")

</div>

Exactly. Which is why it's a lousy example, except in the sense it clearly alerts you to the deficiency of the scheme.

Where I used the trick most recently was in parsing .c and .h files for various useful info I needed to process the header files #include'd as well.

ie. #include "pink\_car.h"

Initially my code was just...

&nbsp;&nbsp;&nbsp;subresult = ParseFile.new( "pink\_car.h")  
but then I noticed I was reparsing common header files far more often than I needed to. Hence memoization trick. A very simple two line change and off I go again with a good burst of speed.

Of course after parsing all the files I need to remember to @@memo = nil  
to actually release the memory...

Why use a class variable for this? It's Good Encapsulation. Who should know whether you have \_ever\_ produced a pink car before? All the pink car users? Or the car factory? Answer, the Car Factory, ie. the Car class.

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

Carter's Clarification of Murphy's Law.

"Things only ever go right so that they may go more spectacularly wrong later."

From this principle, all of life and physics may be deduced.

> **···**
>
> On Fri, 27 Jan 2006, Dave Howell wrote:
> 
> > > If everybody in your country had a pink car, what would you have?
> > 
> > Ha ha. Except that if everybody in my country had a Car.create\_car("pink") car, then the entire country would have exactly one car.

---

<div class="post-metadata">

**Author:** ![Logan\_Capaldo](https://avatars.discourse-cdn.com/v4/letter/l/7ea924/32.png) [@Logan\_Capaldo](https://rubytalk.org/u/Logan_Capaldo)\
**Post date:** [27 January 2006 01:27 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/14 "2006-01-27T01:27:14Z")

</div>

Often memoization is used to speed up functions that are referentially transparent

( Referentially transparent means that  
given a function f, a == b implies that f(a) == f(b). In other words, if you call the function with the same argument, more than once you'll always get back the same answer. def f(x); x +1; end is referentially transparent. Well, unless someone has been playing with Integer#+. IO#gets for instance is not.)

when they take a long time to process. One example is computing the fibonacci sequence (an equally silly example as the car.). If you use memoization, all of a sudden the naive recursive implementation isn't nearly as bad.

since f(0 or 1) = 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;and f(x) = f(x - 1) + f(x - 2)  
you'll notice that f(x) = f(x - 2) + f(x - 3) + f(x - 2). Since we are memoizing, it only computes f(x-2) once, the second time it needs f(x-2) its an O(1) hash lookup, and so on. Normally of course recursive fibonacci is O(2\*\*n).

> **···**
>
> On Jan 26, 2006, at 4:18 PM, Dave Howell wrote:
> 
> > On Jan 26, 2006, at 12:59, John Carter wrote:
> > 
> > > OK, so this trick cannot be used everywhere.
> > > 
> > > Suppose @@memo is a brand spanking new empty Hash object.
> > > 
> > > What does @@memo["pink"] return?
> > > 
> > > By default it returns nil.
> > > 
> > > But you can make it return whatever you damn well feel like.
> > > 
> > > @@memo = Hash.new{|hash,key| hash[key] = Car.new(key)}
> > > 
> > > @@memo["pink"]
> > > 
> > > Will say, oo, I have no "pink" element, I better go off and make one then, fortunately I have a block on my "new" so I know how to do that.
> > > 
> > > ps.
> > > 
> > > If everybody in your country had a pink car, what would you have?
> > 
> > Ha ha. Except that if everybody in my country had a Car.create\_car("pink") car, then the entire country would have exactly one car. I can't figure out what it's good for; any example I can think of in my head is just a complicated way of doing something simple. Either "well, I'll just keep the object around in the first place," or "no, I would have to have my very OWN pink car, not be FlexCar-ing it with other parts of the program"

---

<div class="post-metadata">

**Author:** ![Henry\_Maddocks](https://avatars.discourse-cdn.com/v4/letter/h/f475e1/32.png) [@Henry\_Maddocks](https://rubytalk.org/u/Henry_Maddocks)\
**Post date:** [27 January 2006 09:51 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/15 "2006-01-27T09:51:47Z")

</div>

Ruby Hashes, Blocks & Memoization

[http://opengl.geek.nz/ruby.html](http://opengl.geek.nz/ruby.html)

> **···**
>
> On 27/01/2006, at 8:48 AM, Dave Howell wrote:
> 
> > On Jan 26, 2006, at 10:16, mental@rydia.net wrote:
> > 
> > > Quoting Dave Howell \<groups@grandfenwick.net\>:
> > > 
> > > > Sigh. Sometimes Ruby is \*too\* idiomatic.
> > > > 
> > > > What \*is\* "memo-ization?"
> > > 
> > > It isn't actually a ruby-specific term:
> > 
> > I didn't think it was. That's why the comment and the question are in separate paragraphs.
> > 
> > I might be able to guess what it is if I could read the Ruby code. But I can't figure out what the code does.

---

<div class="post-metadata">

**Author:** ![Alex\_Combas](https://avatars.discourse-cdn.com/v4/letter/a/ba8739/32.png) [@Alex\_Combas](https://rubytalk.org/u/Alex_Combas)\
**Post date:** [28 January 2006 00:19 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/16 "2006-01-28T00:19:24Z")

</div>

Hello,  
I would really like to learn more about memoization  
but unfortunately the gem doesnt seem to install properly on  
my system (Ubuntu Linux) and I was told that in order  
to get downloaded gems to work I would probably have  
to uninstall the apt versions of ruby and rebuild everything  
from source.

I dont really want to do that, so I was wondering if  
the memoization library is small enough that I could  
just put a copy into my path and include it that way,  
rather than as an installed gem.

Does that sound like a sane alternative, or is my only  
option to rip the ruby deb's out of my system and  
start from scratch?

> **···**
>
> --  
> Alex Combas  
> [http://noodlejunkie.blogspot.com/](http://noodlejunkie.blogspot.com/)

---

<div class="post-metadata">

**Author:** ![James\_Britt4](https://avatars.discourse-cdn.com/v4/letter/j/a3d4f5/32.png) [@James\_Britt4](https://rubytalk.org/u/James_Britt4)\
**Post date:** [28 January 2006 00:35 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/17 "2006-01-28T00:35:36Z")

</div>

Alex Combas wrote:

> Hello,  
> I would really like to learn more about memoization  
> but unfortunately the gem doesnt seem to install properly on  
> my system (Ubuntu Linux) and I was told that in order  
> to get downloaded gems to work I would probably have  
> to uninstall the apt versions of ruby and rebuild everything  
> from source.

Do you know this to be an Ubuntu issue, or just a problem you recently noticed? There have been, I believe, some problems with the gem servers the last day or so, and it may worth taking another crack at gem installation.

James

---

<div class="post-metadata">

**Author:** ![James\_Edward\_Gray\_II](https://avatars.discourse-cdn.com/v4/letter/j/ea5d25/32.png) [@James\_Edward\_Gray\_II](https://rubytalk.org/u/James_Edward_Gray_II)\
**Post date:** [28 January 2006 01:10 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/18 "2006-01-28T01:10:34Z")

</div>

You bet. It's a single file. Just download the source from RubyForge and move /lib/memoize.rb into your path. It will work just fine.

James Edward Gray II

> **···**
>
> On Jan 27, 2006, at 6:19 PM, Alex Combas wrote:
> 
> > I dont really want to do that, so I was wondering if  
> > the memoization library is small enough that I could  
> > just put a copy into my path and include it that way,  
> > rather than as an installed gem.

---

<div class="post-metadata">

**Author:** ![Alex\_Combas](https://avatars.discourse-cdn.com/v4/letter/a/ba8739/32.png) [@Alex\_Combas](https://rubytalk.org/u/Alex_Combas)\
**Post date:** [28 January 2006 05:04 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/19 "2006-01-28T05:04:55Z")

</div>

Thanks James!  
Wow, dont want to fanboy here, but wow.

$cat fib.rb  
def fib(n)  
&nbsp;&nbsp;return n if n \< 2  
&nbsp;&nbsp;fib(n-1) + fib(n-2)  
end  
puts fib(35)

$ time ruby fib.rb  
9227465

real 0m41.121s  
user 0m37.128s  
sys 0m3.854s

$cat mem\_fib.rb  
require "memoize"  
include Memoize  
def fib(n)  
&nbsp;&nbsp;return n if n \< 2  
&nbsp;&nbsp;fib(n-1) + fib(n-2)  
end  
memoize(:fib)  
puts fib(35)

$ time ruby mem\_fib.rb  
9227465

real 0m0.011s  
user 0m0.008s  
sys 0m0.003s

Yikes! This is definitly something I'm going to need to learn to use, and use  
as often as possible. So anywho, took a quick peek at memoize.rb and was  
again just blown away but this time because the entire file was only 39 lines  
of code including white space! How can this be?

Unfortuantely, there are no comments to be had, so I was wondering  
if someone would be so kind as to reply with inserted comments in the code,  
(yes I know ruby is supposed to be readable, but im new, ok? 🙂  
Just as a precaution so that I don't make any weird assumptions,  
something I'm prone to do. This would be greatly appreciated.

Bored? Nothing to do on a Friday night?  
Well here is some source. Comment away all you bored rubyists!

module Memoize  
&nbsp;&nbsp;&nbsp;MEMOIZE\_VERSION = "1.2.0"

&nbsp;&nbsp;&nbsp;# Memoize the method +name+. If +file+ is provided, then the method results  
&nbsp;&nbsp;&nbsp;# are stored on disk rather than in memory. This consumes virtually no  
&nbsp;&nbsp;&nbsp;# memory and is persistant.  
&nbsp;&nbsp;&nbsp;def memoize(name, file=nil)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;meth = method(name)

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

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if file  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(class \<\< self; self; end).class\_eval do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;define\_method(name) do |\*args|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;unless cache.has\_key?(args)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cache[args] = meth.call(\*args)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;File.open(file, "wb+"){|f| Marshal.dump(cache, f) }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cache[args]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(class \<\< self; self; end).class\_eval do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;define\_method(name) do |\*args|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if cache.has\_key?(args)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cache[args]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cache[args] ||= meth.call(\*args)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cache  
&nbsp;&nbsp;&nbsp;end

> **···**
>
> On 1/27/06, James Edward Gray II \<james@grayproductions.net\> wrote:
> 
> > You bet. It's a single file. Just download the source from  
> > RubyForge and move /lib/memoize.rb into your path. It will work just  
> > fine.
> 
> --  
> Alex Combas  
> [http://noodlejunkie.blogspot.com/](http://noodlejunkie.blogspot.com/)

---

<div class="post-metadata">

**Author:** ![James\_Britt4](https://avatars.discourse-cdn.com/v4/letter/j/a3d4f5/32.png) [@James\_Britt4](https://rubytalk.org/u/James_Britt4)\
**Post date:** [28 January 2006 06:39 UTC](https://rubytalk.org/t/minimizing-memory-allocations/24234/20 "2006-01-28T06:39:00Z")

</div>

Alex Combas wrote:

> ...

> Yikes! This is definitly something I'm going to need to learn to use, and use  
> as often as possible. So anywho, took a quick peek at memoize.rb and was  
> again just blown away but this time because the entire file was only 39 lines  
> of code including white space! How can this be?
> 
> Unfortuantely, there are no comments to be had, so I was wondering  
> if someone would be so kind as to reply with inserted comments in the code,  
> (yes I know ruby is supposed to be readable, but im new, ok? 🙂  
> Just as a precaution so that I don't make any weird assumptions,  
> something I'm prone to do. This would be greatly appreciated.

Basically, the arguments to the target method are used as a hash key into a cache. The cache hash is stored either in memory, or (optionally) on disk.

If you give memoize a file name it will serialize the results cache to and from disk using Ruby's Marshal code.

Otherwise, the cache just sits in memory.

The code defines a singleton method of the same name as the target method. Calls to the target method are passed to this singleton method; it has first crack at looking to see if there is a cached value.

If it has the value, then it is returned; all done.

Otherwise, the value is obtained by calling the original method defined in the class source code, the results are cached (and the file updated, if defined) and the value returned.

The neat part is the use of a singleton method to intercept calls to the target method:

class Foo

&nbsp;&nbsp;&nbsp;include Memoize

&nbsp;&nbsp;&nbsp;def initialize  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memoize :baz  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def baz val  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;"Baz sez #{val}"  
&nbsp;&nbsp;&nbsp;end

end

When you call

&nbsp;&nbsp;foo = Foo.new  
&nbsp;&nbsp;foo.baz( 'Hey.' )

the first baz invoked is the singleton method defined on foo. If it does not have a cached value, it calls the baz method defined in the Foo class.

&nbsp;&nbsp;puts foo.singleton\_methods # baz

(But note that an in-memory hash will exist for each instance. A file allows for all instances to share values, and to have those values persist from runs of the application, but may introduce race conditions.)

> **···**
>
> --  
> James Britt
> 
> "Blanket statements are over-rated"

[Next page](https://rubytalk.org/t/minimizing-memory-allocations/24234.md?page=2)