Memoization: premature optimization is the root of (at least some) evil

memoization_complexity.rb

require 'minitest/autorun'

# Many Ruby programmers have a tendency to use memoization too frequently.
# Memoization, when used correctly, can add value to some code by making it
# faster. However, we should remember that pure functions - ones that only rely
# on inputs to produce their result are the simplest. Memoizing, where we save
# state in the form of calculated results, makes our functions impure, and we
# have to be careful that we're not introducing bugs.
describe "how memoization adds extra complexity, and why it should usually be avoided" do

  describe "#add2 as a simple, pure function" do

    def add2(addend)
      addend + 2
    end

    it "adds two to the result" do
      add2(2).must_equal 4
    end

    it "is correct even when called with different argument values" do
      add2(2).must_equal 4
      add2(4).must_equal 6
    end
  end

 # One of the most common ways that bugs are added through improper memoization
 # is adding memoization to a function that accepts arguments, and neglecting to
 # memoize based on the argument values.
  describe "#add2_with_improper_memoization" do

    def buggy_add2(addend)
    @_result ||= addend + 2
    end

    it "returns the correct result when called the first time" do
      buggy_add2(2).must_equal 4
    end

    it "returns the wrong result when called with a different argument value" do
      buggy_add2(2).must_equal 4

      # Bug!
      buggy_add2(4).must_equal 6
    end
  end

  # To fix the bug, you would need to memoize the result based on the value of
  # the argument. As with any addition of state, this adds complexity. You need
  # to think about the following:
  #
  # 1. You will be using more memory as you cache return results for different
  #    argument values. On a production system, you may have to implement some
  #    kind of eviction algorithm (e.g., LRU) in order to achieve your desired
  #    efficiency while keeping memory use within a reasonable limit.
  # 2. You will have additional code not only to write, but to test. This
  #    will increase development time.
  # 3. As you increase code complexity, system modifications and extensions will
  #    become more complicated. Think about the long-term cost of your
  #    optimizations in the system. What if someone moves the function to a
  #    place where the cached result stays in memory for longer? How long will
  #    it take the engineering team to track down the memory leak caused by your
  #    memoization, and how much production traffic will it affect?
  #
  # How do you know if an optimization is worthwhile? Make sure that speed in
  # your system is a *feature*. If someone isn't prioritizing your optimization
  # work, and paying you to make the code faster in that particular section,
  # don't do it - implement the simple, pure function and move on.
  describe "#add2_with_proper_memoization" do

    def add2_memoized_properly(addend)
      @_result ||= []
      @_result[addend] ||= addend + 2
    end

    it "returns the correct result when called the first time" do
      add2_memoized_properly(2).must_equal 4
    end

    it "still returns correct results with different argument values" do
      add2_memoized_properly(2).must_equal 4
      add2_memoized_properly(4).must_equal 6
    end
  end
end