Your thoughts on #memo?

tcsnide · August 23, 2010, 5:22pm

Like to get some thoughts on the following technique for memoization:

Memoize a method.

class MemoExample

attr_accessor :a

def m

memo{ @a }

end

ex = MemoExample.new

ex.a = 10

ex.m #=> 10

ex.a = 20

ex.m #=> 10

def memo(&block)
key = eval(‘method’, block)
val = block.call
singleton_class = (class << self; self; end)
singleton_class.send(:define_method, key){ val }
val
end

Downside / upsides to the approach? Any suggestions for improvement?
Or is this just an altogether bad idea?

tcsnide · August 23, 2010, 5:42pm

2010/8/23 Intransition [email protected]:

val = block.call
singleton_class = (class << self; self; end)
singleton_class.send(:define_method, key){ val }
val
end

I could not get that to work on 1.9.1:

17:33:49 ~$ irb19
Ruby version 1.9.1
irb(main):001:0> def memo(&block)
key = eval(‘method’, block)
val = block.call
singleton_class = (class << self; self; end)
singleton_class.send(:define_method, key){ vairb(main):002:1> l }
key = eval(‘method’, block)
irb(main):003:1> val = block.call
irb(main):004:1> singleton_class = (class << self; self; end)
irb(main):005:1> singleton_class.send(:define_method, key){ val }
irb(main):006:1> val
irb(main):007:1> end
=> nil
irb(main):008:0> class ME
irb(main):009:1> attr_accessor :a
irb(main):010:1> def m;memo { @a }; end
irb(main):011:1> end
=> nil
irb(main):012:0> ex=ME.new
=> #ME:0x10049a74
irb(main):013:0> ex.a=10
=> 10
irb(main):014:0> ex.m
TypeError: wrong argument type Proc (expected Binding)
from (irb):2:in eval' from (irb):2:in memo’
from (irb):10:in m' from (irb):14 from /opt/bin/irb19:12:in ’
irb(main):015:0>

Also I believe the results would not be like your comments suggest
since you redefine the method all the time. Am I missing something?

Downside / upsides to the approach? Any suggestions for improvement?
Or is this just an altogether bad idea?

I do not see the advantage over plain definition of

def ex.m; 10; end

since you are storing a single value anyway. It seems your approach
is only advantageous if you need to access instance variables because
then it spares some ugly syntax. But since you have to call #memo
explicitly you can even pass the value to bind to the method as well,
e.g.

def memo(name, val)
(class << self; self; end).define_method(name){ val }
end

ex.memo :a, 10

As long as you have to invoke the method setting the value explicitly
you do not gain anything, do you? Somehow I must be missing something
but I can’t see it right now.

Kind regards

robert

tcsnide · August 23, 2010, 5:55pm

Yikes. There’s rarely a good reason to need to call eval. And the rest
of
this seems really awkward, too. I would recommend watching Dave T.’
metaprogramming screencast, where he solves the metaprogramming problem
(literally) 9 different ways, and talks about the pros and cons. It’s at
http://pragprog.com/screencasts/v-dtrubyom/the-ruby-object-model-and-metaprogrammingand
you can either get just episode 5, or get the whole screencast, it’s
well worth the money.

tcsnide · August 23, 2010, 6:48pm

On 8/23/10, Intransition [email protected] wrote:

The use case for #memo is an alternative to:

def m
@m ||= …
end

But differs in that it avoids the need for an instance variable. I
tend to use the “@m ||=” idiom a lot, though I wonder about it’s
threading implications, and whether something like #memo would be more
robust.

Your #memo method is no more re-entrant than the instance variable
example you gave above. If you want it to be re-entrant, you need to
have a mutex.

Also, I seem to recall that methods defined via define_method are
slower than methods defined via def. But I couldn’t see a way to
rewrite your code using def instead…

tcsnide · August 23, 2010, 6:20pm

On Aug 23, 11:37 am, Robert K. [email protected] wrote:

irb(main):003:1> val = block.call
irb(main):012:0> ex=ME.new
irb(main):015:0>
Looks like you can’t pass a Proc to eval in 1.9+. Wonder why that was
gotten rid of? Ironically I only leaned one could even do that at all
a few month ago! I love having to unlearn.

Looks like it can be fixed with:

key = eval(‘method’, block.binding)

Also I believe the results would not be like your comments suggest
since you redefine the method all the time. Am I missing something?

After the first time, the original method would no longer be
accessible (at least not via normal method calling).

explicitly you can even pass the value to bind to the method as well,
but I can’t see it right now.
Yes, part of the reason for this design is to avoid restating the
method name. That’s the only reason a block is used in fact, to gain
access to the callers binding so as to get the method name.

The use case for #memo is an alternative to:

def m
@m ||= …
end

But differs in that it avoids the need for an instance variable. I
tend to use the “@m ||=” idiom a lot, though I wonder about it’s
threading implications, and whether something like #memo would be more
robust.

tcsnide · August 24, 2010, 3:40am

On Aug 23, 1:52 pm, Benoit D. [email protected] wrote:

def m

ex.m #=> 10

Or is this just an altogether bad idea?
It is pretty bad because it redefines the method, however all the
meta-programming stuff is rather interesting, I think.

What do you think of it?

I find the approach of extending Method interesting. I will have to
play with that.

Are you always getting the same method object and thus the same cache
for memoize2?

tcsnide · August 23, 2010, 7:53pm

On 23 August 2010 17:18, Intransition [email protected] wrote:

val = block.call
singleton_class = (class << self; self; end)
singleton_class.send(:define_method, key){ val }
val
end

Downside / upsides to the approach? Any suggestions for improvement?
Or is this just an altogether bad idea?

It looks a bit weird, and eval is really ugly^

I recently wrote two crazy implementations of memoize:

github.com

eregon/project_euler/blob/master/014.rb#L64-93


      
          class Integer
            attr_reader :calc
            def sequence(n = self, i = 1)
              (n == 1 or (n.calc and i += n.calc-1)) ? @calc = i : sequence(n.even? ? n/2 : 3*n+1, i+1)
            end
          end
          
          
#p (1..1_000_000).max_by(&:sequence) # 837799, 7.3s
          
          
# With Memoize
          class Method
            def memoize
              method = name
              original = "org_#{name}"
              cache = {}
              owner.class_eval {
                alias_method original, method
                define_method(method) { |arg|
                  if cache.key? arg
                    cache[arg]
                  else

The second seems rather inefficient, while the first seems good.
I’m here saving the only argument to determine what to cache.

It is pretty bad because it redefines the method, however all the
meta-programming stuff is rather interesting, I think.

What do you think of it?

B.D.

tcsnide · August 24, 2010, 3:52am

On Aug 23, 12:47 pm, Caleb C. [email protected] wrote:

threading implications, and whether something like #memo would be more
robust.

Your #memo method is no more re-entrant than the instance variable
example you gave above. If you want it to be re-entrant, you need to
have a mutex.

Ah, thanks Caleb. So to be on the “safe” side I will have to use a
mutex for any memoization code I might devise --there’s no way around
it.

Also, I seem to recall that methods defined via define_method are
slower than methods defined via def. But I couldn’t see a way to
rewrite your code using def instead…

Well, speed wise, I imagine the mutex will really take care of
that