Ruby MRH (Most Recently Hangman) for 4 June 2013

[markus]

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
time:

def foo
@foo ||= (expensive_operation_here)
end

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)
end

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
implement:

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
@bar.shift
i -= 1
end
@bar[i] = [[a,b,c],(expensive_function_of_a_b_and_c_here)]
end
@bar[i].last
end

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
over.

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 }
@bar[a,b,c]
end

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)
h___
____k____k____h________k____h__h_______h______h>=n; b______
end

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