32 views

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

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

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu