How should I avoid memoization causing bugs in Ruby?
- by Andrew Grimm
Is there a consensus on how to avoid memoization causing bugs due to mutable state?
In this example, a cached result had its state mutated, and therefore gave the wrong result the second time it was called.
class Greeter
def initialize
@greeting_cache = {}
end
def expensive_greeting_calculation(formality)
case formality
when :casual then "Hi"
when :formal then "Hello"
end
end
def greeting(formality)
unless @greeting_cache.has_key?(formality)
@greeting_cache[formality] = expensive_greeting_calculation(formality)
end
@greeting_cache[formality]
end
end
def memoization_mutator
greeter = Greeter.new
first_person = "Bob"
# Mildly contrived in this case,
# but you could encounter this in more complex scenarios
puts(greeter.greeting(:casual) << " " << first_person) # => Hi Bob
second_person = "Sue"
puts(greeter.greeting(:casual) << " " << second_person) # => Hi Bob Sue
end
memoization_mutator
Approaches I can see to avoid this are:
greeting could return a dup or clone of @greeting_cache[formality]
greeting could freeze the result of @greeting_cache[formality]. That'd cause an exception to be raised when memoization_mutator appends strings to it.
Check all code that uses the result of greeting to ensure none of it does any mutating of the string.
Is there a consensus on the best approach? Is the only disadvantage of doing (1) or (2) decreased performance? (I also suspect freezing an object may not work fully if it has references to other objects)
Side note: this problem doesn't affect the main application of memoization: as Fixnums are immutable, calculating Fibonacci sequences doesn't have problems with mutable state. :)
