Last active
August 3, 2017 18:05
-
-
Save jsl/3372927dfe547ad79debbd1ac8a32785 to your computer and use it in GitHub Desktop.
Memoization: premature optimization is the root of (at least some) evil
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment