How to memoize

Memoization is an optimisation technique that works by caching the results of slow functions. It’s easy to implement, but a production-ready implementation is considerably trickier. And how do you test that your implementation is correct, and useful?

I’ll show you the tricky bits in implementing memoization, where I’ll touch on Ruby metaprogramming and memory management. Lastly, I’ll show how to measure and verify that memoization is meaningful.

Transcript

1. PRESENTATION TITLE: [REDACTED] AUTHOR: DENIS DEFREYNE (@DDFREYNE) OCCASION: RUG45B, 2018-03-01
 
 AUDIENCE: INHABITANTS OF EARTH
2. What do you do when you have an expensive function, and you need to use its return value multiple times?
3. def total_price vat = calc_base_price * VAT_RATE calc_base_price + vat end

4. def total_price base_price = calc_base_price vat = base_price * VAT_RATE base_price + vat end
5. 0 LOCAL VARIABLES
6. A B C D E F G H B1 B2
7. children
8. children.map(&:depth)
9. children.map(&:depth).max
10. children.map(&:depth).max || 0
11. (children.map(&:depth).max || 0) + 1
12. def depth (children.map(&:depth).max || 0) + 1 end
13. A B C D E F G H B1 B2
14. a.depth = b.depth + 1 A B C D E F G H B1 B2
15. a.depth = b.depth + 1 b.depth = [b1.depth, c.depth].max + 1 A B C D E F G H B1 B2
16. a.depth = b.depth + 1 b.depth = [b1.depth, c.depth].max + 1 … A B C D E F G H B1 B2
17. a.depth = b.depth + 1 b.depth = [b1.depth, c.depth].max + 1 … b2.depth = f.depth + 1 A B C D E F G H B1 B2
18. a.depth = b.depth + 1 b.depth = [b1.depth, c.depth].max + 1 … b2.depth = f.depth + 1 e.depth = f.depth + 1 A B C D E F G H B1 B2
19. a.depth = b.depth + 1 b.depth = [b1.depth, c.depth].max + 1 … b2.depth = f.depth + 1 e.depth = f.depth + 1 … A B C D E F G H B1 B2
20. def depth (children.map(&:depth).max || 0) + 1 end
21. def depth @_depth ||= (children.map(&:depth).max || 0) + 1 end
22. 1 MEMOIZATION USING ||=
23. def fib(n) case n when 0 0 when 1 1 else fib(n - 1) + fib(n - 2) end end
24. def fib(n) case n when 0 0 when 1 1 else fib(n - 1) + fib(n - 2) end end fib(0) = 0 fib(1) = 1 fib(2) = 1 fib(3) = 2 fib(4) = 3 fib(5) = 5 fib(6) = 8 fib(7) = 13 fib(8) = 21 fib(9) = 34
26. fib(40)
27. fib(40) = fib(38) + fib(39)
28. fib(40) = fib(38) + fib(39) = fib(38) + fib(37) + fib(38)
29. fib(40) = fib(38) + fib(39) = fib(38) + fib(37) + fib(38) = fib(36) + fib(37) + fib(37) + fib(38)
30. fib(40) = fib(38) + fib(39) = fib(38) + fib(37) + fib(38) = fib(36) + fib(37) + fib(37) + fib(38) = fib(36) + fib(37) + fib(37) + fib(36) + fib(37)
31. fib(40) = fib(38) + fib(39) = fib(38) + fib(37) + fib(38) = fib(36) + fib(37) + fib(37) + fib(38) = fib(36) + fib(37) + fib(37) + fib(36) + fib(37) = …
32. fib(40) takes 15 seconds
 on my 3.1 GHz machine!
33. def fib(n) init = [0, 1] while init.size <= n init << init.last(2).sum end init[n] end
34. def fib(n) @fib ||= {} @fib[n] ||= case n when 0 0 when 1 1 else fib(n - 1) + fib(n - 2) end end
35. 2 ARGUMENT-AWARE MEMOIZATION USING ||=
36. def fib(n) … end memoize :fib
37. def memoize(method_name) end
38. def memoize(method_name) end
39. def memoize(method_name) nonmemoized_method_name = '__nonmemoized_' + method_name.to_s alias_method nonmemoized_method_name, method_name end
40. def memoize(method_name) nonmemoized_method_name = '__nonmemoized_' + method_name.to_s alias_method nonmemoized_method_name, method_name define_method(method_name) do |*args| send(nonmemoized_method_name, *args) end end
41. def memoize(method_name) nonmemoized_method_name = '__nonmemoized_' + method_name.to_s alias_method nonmemoized_method_name, method_name define_method(method_name) do |*args| send(nonmemoized_method_name, *args) end end
42. def memoize(method_name) nonmemoized_method_name = '__nonmemoized_' + method_name.to_s alias_method nonmemoized_method_name, method_name define_method(method_name) do |*args| @cache ||= {} method_cache = (@cache[method_name] ||= {}) send(nonmemoized_method_name, *args) end end
43. def memoize(method_name) nonmemoized_method_name = '__nonmemoized_' + method_name.to_s alias_method nonmemoized_method_name, method_name define_method(method_name) do |*args| @cache ||= {} method_cache = (@cache[method_name] ||= {}) method_cache[args] = send(nonmemoized_method_name, *args) end end
44. def memoize(method_name) nonmemoized_method_name = '__nonmemoized_' + method_name.to_s alias_method nonmemoized_method_name, method_name define_method(method_name) do |*args| @cache ||= {} method_cache = (@cache[method_name] ||= {}) if method_cache.key?(args) method_cache[args] else method_cache[args] = send(nonmemoized_method_name, *args) end end end
45. 3 GENERIC MEMOIZATION USING #MEMOIZE
46. class Node def depth (children.map(&:depth).max || 0) + 1 end memoize :depth end
47. h = Node.new g = Node.new(h) f = Node.new(g) e = Node.new(f) d = Node.new(e) c = Node.new(d) b2 = Node.new(f) b1 = Node.new(b2) b = Node.new(c, b1) a = Node.new(b)
 
 p a.depth
 B C D E F G B1 B2 B C D E B1 B2
48. h = Node.new g = Node.new(h) f = Node.new(g) e = Node.new(f) d = Node.new(e) c = Node.new(d) b2 = Node.new(f) b1 = Node.new(b2) b = Node.new(c, b1) a = Node.new(b)
 
 a.freeze
 p a.depth B C D E F G B1 B2 B C D E B1 B2
49. node.rb:123:in `depth': can't modify frozen Node (FrozenError)
50. def memoize(method_name) nonmemoized_method_name = '__nonmemoized_' + method_name.to_s alias_method nonmemoized_method_name, method_name define_method(method_name) do |*args| @cache ||= {} method_cache = (@cache[method_name] ||= {}) if method_cache.key?(args) method_cache[args] else method_cache[args] = send(nonmemoized_method_name, *args) end end end
51. def memoize(method_name) nonmemoized_method_name = '__nonmemoized_' + method_name.to_s alias_method nonmemoized_method_name, method_name define_method(method_name) do |*args| @cache ||= {} method_cache = (@cache[method_name] ||= {}) if method_cache.key?(args) method_cache[args] else method_cache[args] = send(nonmemoized_method_name, *args) end end end
52. def memoize(method_name) nonmemoized_method_name = '__nonmemoized_' + method_name.to_s alias_method nonmemoized_method_name, method_name method_cache = {} define_method(method_name) do |*args| instance_cache = (method_cache[self] ||= {}) if instance_cache.key?(args) instance_cache[args] else instance_cache[args] = send(nonmemoized_method_name, *args) end end end
53. 4 GENERIC MEMOIZATION SUPPORTING #FREEZE
54. We’re running out of memory!
55. def memoize(method_name) nonmemoized_method_name = '__nonmemoized_' + method_name.to_s alias_method nonmemoized_method_name, method_name method_cache = {} define_method(method_name) do |*args| instance_cache = (method_cache[self] ||= {}) if instance_cache.key?(args) instance_cache[args] else instance_cache[args] = send(nonmemoized_method_name, *args) end end end
57. require 'weakref'
 
 ref = WeakRef.new("hi")
 ref.upcase
58. require 'weakref'
 
 ref = WeakRef.new("hi")
 ref.upcase # a> HI

59. require 'weakref'
 
 ref = WeakRef.new("hi")
 ref.upcase # a> HI
 GC.start
 ref.upcase
60. require 'weakref'
 
 ref = WeakRef.new("hi")
 ref.upcase # a> HI
 GC.start
 ref.upcase # WeakRef45RefError (Invalid Reference - probably recycled)
61. require 'ref' ref = RefnoSoftReference.new("hello")
 ref.object.upcase # a> HI
62. define_method(method_name) do |*args| instance_cache = (method_cache[self] ||= {}) value = instance_cache[args]&.object if value value else instance_cache[args] = Ref45SoftReference.new( send(original_method_name, *args) ) end end
63. RefnoSoftReference.new(123) # a> ArgumentError (cannot define finalizer for Integer)
64. class ValueWrapper attr_reader :value def initialize(value) @value = value end end
65. define_method(method_name) do |*args| instance_cache = (method_cache[self] ||= {}) value = instance_cache[args]&.object if wrapper wrapper.value else value = send(original_method_name, *args) wrapper = ValueWrapper.new(value) instance_cache[args] = RefnoSoftReference.new(wrapper) value end end
66. 5 GENERIC MEMORY-EFFICIENT MEMOIZATION
67. Thread safety? Nöpe.
68. (I’ll get around to that, eventually.)
69. EXECUTIVE SUMMARY TIME
70. We now have a memoization mechanism that… * … has a nice API * … supports multiple arguments * … supports frozen objects * … is memory-efficient * … and soon will be thread-safe
71. I love immutability.
72. You don’t have to implement this yourself, ever. Give ddmemoize a try: github.com/ddfreyne/ddmemoize
73. require 'ddmemoize' class FibFast DDMemoize.activate(self) memoized def run(n) if n == 0 0 elsif n == 1 1 else run(n - 1) + run(n - 2) end end end
74. DDMemoize.print_metrics memoization │ hit miss % ────────────┼─────────────────── FibFast#fib │ 998 1001 49.9%
75. Q&A