Ruby MRH (Most Recently Hangman) for 4 June 2013

Skip to first unread message


Jun 4, 2013, 3:31:57 AM6/4/13
to pdxruby
Good morning, fellow rubyologists!

I suspect most of you are familiar with the ruby memoization idiom for
caching the results of parameterless pure functions, so that we only pay
the cost of evaluation if they are used and even then only the first

def foo
@foo ||= (expensive_operation_here)

And many of you are likely also familiar with the extension of this
pattern, via a hash, to support functions that take arguments:

def bar(a,b,c)
@bar ||= {}
@bar[[a,b,c]] ||= (expensive_function_of_a_b_and_c_here)

This second form is often good enough, but the transformation does
introduce a risk; if the parent object is long lived, and the method is
called (over the course of its lifetime) with many different values for
a,b, and c, the caching hash can grow arbitrarily large.

The usual solution is to introduce a LRU (least recently used) cache so
that only the N most recently requested entries would be saved in the
cache. For many common access patterns that gives you most of the
speed-up for a small fraction of the cost. It's not too hard to

def bar(a,b,c)
cache_size = 40
@bar ||= []
i = 0
i += 1 while i < @bar.length && @bar[i].first != [a,b,c]
if i == @bar.length
if @bar.length == cache_size
i -= 1
@bar[i] = [[a,b,c],(expensive_function_of_a_b_and_c_here)]

Not to hard, but pretty darned ugly. And pretty finicky. It's also
fairly tangled up with the implementation of the function, which means
that if we want to do the same thing for ten functions we'll have ten
copies of code that (if we're lucky) just repeats the logic over and

What we'd really like is a way to factor the LRU logic out into
something that could be reused with roughly the same amount of effort as
the earlier examples. Something that would let us write things like:

def bar(a,b,c)
@bar ||= LRU(40) { |a,b,c| expensive_function_of_a_b_and_c_here }

Fortunately (admit it, you knew this was coming) in ruby 1.9 and later
this isn't too hard to do. You just need to define a helper that
returns the right sort of object:

def LRU(n,&b)
____k____k____h________k____h__h_______h______h>=n; b______

That's the basic idea, at any rate. Now all you need to do is fill in a
few details....

See y'all at the meeting,

-- Markus

Reply all
Reply to author
0 new messages