Memoisation trade-offs

Why this matters

Some functions give the same answer every time you call them with the same input, and they take a long time to compute it. A program that calls such a function again and again with the same inputs wastes time repeating work it already did. The fix is to write the answer down the first time, and read it back the next time. This is called memoisation. The word comes from "memo", a note to remember something.

Memoisation is a deal. You get speed, and you pay with memory, because every written-down answer takes space. Sometimes the deal is excellent. Sometimes the notes cost more room than the time they save. A good programmer can tell the difference by counting, not by guessing.

This lesson covers the cost of storing answers, the point where a stored answer saves more time than it takes in space, and the limits you can place on a cache. Hash table costs, which explain why a lookup in the stored answers is fast, are covered in the previous lesson of this module. The neighbouring lessons on counting steps and recursion trees explain how to predict the cost of a recursive function before you run it.

The idea: a notebook of answers

Picture a student doing homework with a set of hard questions. Question 7 depends on question 6, which depends on question 5, and so on. The student solves question 5 and writes the answer on a sheet of paper. When question 6 needs question 5's answer, the student reads the sheet instead of solving it again. The sheet is the cache. A cache is any place where you keep results so you do not have to compute them again.

The sheet of paper costs something. It takes space on the desk, and if the student writes down every answer ever worked out, the pile of paper grows. The trade is clear: time saved against paper used.

In a program, the sheet is usually a dictionary or a list. The key is the input to the function, and the value is the answer. Before doing the work, the function checks the dictionary. If the input is there, it returns the stored answer. If not, it does the work, stores the answer, and returns it.

Worked example 1: Fibonacci without and with a cache

The Fibonacci numbers start with 0 and 1, and each later number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, and so on. The number fib(n) is the n-th number in this list.

The most direct way to write this is also the most wasteful. It is recursive: the function calls itself. To find fib(n), call fib(n - 1) and fib(n - 2) and add the results. The code below counts how many times the function runs. A counter is passed in so the count is clear.

Naive Fibonacci
fib(10) = 55, calls = 177
fib(20) = 6765, calls = 21891
fib(25) = 75025, calls = 242785
fib(30) = 832040, calls = 2692537

Look at fib(5) by hand to see why. It calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). Now fib(3) has been worked out twice, and each time it does the whole job again. The same smaller answers come back many times. The number of calls grows fast: fib(30) makes 2692537 calls, and fib(40) would make more than 330 million. The time grows exponentially, which means it multiplies by a fixed amount each time n goes up by one.

Now add the notebook. Before working out fib(n), the function checks whether it has already written that answer down.

Fibonacci with a dict cache
fib(10) = 55
  calls = 19, entries stored = 9
fib(20) = 6765
  calls = 39, entries stored = 19
fib(30) = 832040
  calls = 59, entries stored = 29
fib(100) = 354224848179261915075
  calls = 199, entries stored = 99

The numbers tell the story. For fib(30), the naive version made 2692537 calls. The cached version made 59 calls and stored 29 answers. The cache turned an exponential amount of work into work that grows in a straight line with n. Each new answer is computed once and then read back.

The price is memory. The cache holds one entry for each n from 2 up to the target, so it stores about n entries. For fib(100), that is 99 entries. There is one more cost that is easy to miss: the recursion itself. The function goes n levels deep before it starts returning answers, and each level holds a frame (the record Python keeps for one active call) while it waits. So this version uses about n entries for the cache plus about n frames for the recursion.

Worked example 2: counting paths on a grid

Here is a problem with the same shape and more room for mistakes. A robot stands at the top left corner of a grid. It can move one step right or one step down. How many different routes lead to the bottom right corner?

Let paths(r, c) be the number of routes to a point that is r steps down and c steps right of the start. A point on the top row or the left column has exactly one route: go straight. Any other point can be reached from the point above it or from the point to its left, so paths(r, c) is the sum of those two.

The code below does the counting in the direct way, and counts the calls.

Grid paths, naive recursion
5x5 grid: paths = 252, calls = 503
10x10 grid: paths = 184756, calls = 369511
12x12 grid: paths = 2704156, calls = 5408311

Now the cache is handled by Python's functools.lru_cache, a built-in decorator that stores results for you. A decorator is a line above a function that wraps it with extra behaviour. Here the decorator is written inside a function, so each cache limit can be tried separately.

Grid paths, cached with lru_cache
5x5 grid: paths = 252
  misses = 35, hits = 16, entries stored = 35
10x10 grid: paths = 184756
  misses = 120, hits = 81, entries stored = 120
12x12 grid: paths = 2704156
  misses = 168, hits = 121, entries stored = 168
100x100 grid: paths = 90548514656103281165404177077484163874504589675413336841320
  misses = 10200, hits = 9801, entries stored = 10200

The cache reports two numbers. A miss is a call that had to do the real work and store a new answer. A hit is a call that found the answer already stored. For the 12 by 12 grid, the cache had 168 misses and 121 hits. The naive version made 5408311 calls for the same answer.

The entry count has a simple form. For an r by c grid, the cache stores one entry for every point (r, c) with both numbers from 0 up to the grid size, except the start point (0, 0), which is never asked for. That is (r + 1) times (c + 1) minus 1 entries. For the 12 by 12 grid that is 13 times 13 minus 1, which is 168. This is O(r times c) memory, the number of points in the grid.

When does the cache pay off?

A cache has two costs and one benefit. The costs are the memory for the entries, and the code needed to check and fill the cache. The benefit is the work skipped when a question comes back. A cache pays off when the benefit is bigger than the cost, in terms you can count.

The simplest test is to run the same function on two different streams of questions. The example below asks the same slow function a thousand questions. In one stream, the questions repeat ten different values. In the other, every question is different.

Same function, two query streams
10 distinct inputs, 1000 queries: work = 10, hits = 990, entries stored = 10
1000 distinct inputs, 1000 queries: work = 1000, hits = 0, entries stored = 1000

In the first stream, the cache stores 10 answers and saves 990 pieces of work. That is a clear win: 10 small entries buy 990 skipped computations.

In the second stream, the cache stores 1000 answers and saves nothing. Every answer is written down and never read again. The program uses more memory and gains no speed. This is the bad case, and it is common: a cache added to a function whose inputs almost never repeat.

To decide between the two cases, count two numbers from a trial run:

• The work avoided, which is the number of hits multiplied by the cost of one computation. In recursive functions, a single hit can avoid a whole branch of calls, so count calls, not hits, when you have them.
• The memory used, which is the number of entries multiplied by the size of one entry.

A cache is worth keeping when the work avoided is large compared with the memory held. The Fibonacci numbers show the extreme case. The naive version made 2692537 calls for fib(30), and the cache made 59 calls and held 29 entries. The memory cost was small and the time saving was enormous.

Be careful with the rule "hits must be more than entries". It sounds right, but it can mislead. In the 10 by 10 grid, the cache had 81 hits and 120 entries, so there were fewer hits than entries. Yet the naive version made 369511 calls, and the cached version made 201 calls in total (120 misses and 81 hits). Each hit in the grid skipped a whole branch of calls, so a few hits saved a great deal. Count the calls saved, not only the hits.

Limiting the cache

An unbounded cache keeps every answer forever. For a function with many distinct inputs, this can use more memory than the computer has. A bounded cache keeps only a fixed number of entries. When it is full and a new answer arrives, it drops an old one. The maxsize option of lru_cache sets this limit. The name stands for "least recently used": the entry dropped is the one that has gone unread the longest.

A bounded cache can keep memory small, but it can throw away answers that are needed again. The next example compares the grid from before with an unbounded cache and a cache holding only 16 entries.

Bounded cache: limit the number of entries
12x12 grid, maxsize=None: misses = 168, hits = 121, entries stored = 168
12x12 grid, maxsize=16: misses = 168, hits = 121, entries stored = 16
30x30 grid, maxsize=None: misses = 960, hits = 841, entries stored = 960
30x30 grid, maxsize=16: misses = 7891, hits = 6090, entries stored = 16

For the 12 by 12 grid, the 16-entry cache gives the same misses and hits as the unbounded cache, but it stores only 16 entries instead of 168. For the 30 by 30 grid, the small cache has 7891 misses, against 960 for the unbounded cache. The small cache is much smaller, but it does about eight times as much work. The answers it dropped were needed again soon after.

The lesson is that a limit moves the cost from memory to time. Choose the limit from a test run, using the miss count to see how much work the limit adds.

Measuring the memory of a cache

The memory held by a cache can be measured with the standard library's tracemalloc module, which records how many bytes the program allocates. The example below fills a dictionary cache for Fibonacci numbers up to 300 and then reports the bytes in use.

entries stored = 299, memory held = 23920 bytes

That is about 80 bytes per entry. Another run or Python version can print a different number, so treat the last digits as an estimate. It includes the dictionary's own table and the large integers stored as answers. The Fibonacci answers grow in size as n grows, so later entries are bigger than earlier ones. The memory cost of a cache depends on what you store, not only on how many entries there are.

Common mistakes

Most memoisation bugs are one of five kinds: a wrong key, an unusable key, a cache that grows without limit, a recursion that goes too deep, or a result that changes.

Mistake 1: a key that leaves out an input. The cache key must include every input that changes the answer. This function takes two inputs, but the cache is keyed only on the exponent:

power_bad(2, 3) = 8
power_bad(5, 3) = 8 (should be 125)

The second call finds 3 in the cache, left over from the first call with base 2, and returns 8 without any error message. The fix is to key the cache on both inputs, for example with bad[(base, exp)]. Wrong answers like this are the hardest bugs to notice, because the program runs without complaint.

Mistake 2: an input that cannot be a key. A dictionary key must be hashable, which means it cannot change after it is created. A list can change, so it cannot be a key. Calling a cached function with a list gives an error:

TypeError: unhashable type: 'list'

Convert the list to a tuple, such as tuple(values), before passing it to the cached function. A tuple cannot change, so it works as a key.

Mistake 3: a recursion that goes too deep. A memoised function still recurses, and Python limits the depth of recursion. With the default limit, a Fibonacci call for n = 5000 fails:

RecursionError: maximum recursion depth exceeded

The cache removed the repeated work, but the first call to fib_memo(5000) still goes 5000 levels deep before any answer is stored. A fix is to compute the answers from the bottom up with a loop, which uses no recursion at all, or to store answers in a fixed order so that smaller values are already in the cache.

Mistake 4: an unbounded cache in a long-running program. A web server or a long batch job that caches every answer will grow its memory without end if the inputs keep changing. Use a bounded cache, such as lru_cache(maxsize=...), when the inputs are not limited in advance. Check the memory of a long run, not only of a short test.

Mistake 5: caching a result that changes. A cache is safe only when the same input always gives the same answer. If the answer depends on the current time, a file, a database or a random number, a cached answer goes out of date or becomes wrong. Cache only pure answers, or give cached answers an expiry.

Practice

Exercise 1. Using the formula that the naive Fibonacci call count is 2 times fib(n + 1) minus 1, predict the number of calls for fib(5). Then check your answer with the naive code.

Show the answer.

The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, so fib(6) is 8. The formula gives 2 times 8 minus 1, which is 15. Running the naive code with n = 5 gives 15 calls.

Exercise 2. The dictionary cache for fib_cached stores one entry for each n from 2 up to the target. How many entries does it store for fib(50)?

Show the answer.

The entries are for n = 2, 3, ..., 50. That is 49 values. The check from the earlier example agrees: fib(10) stored 9 entries, which is 10 minus 1, and the same pattern gives 50 minus 1 for fib(50). Running the code confirms 49 entries and the answer 12586269025.

Exercise 3. The lru_cache grid cache stores one entry for each point in an r by c grid, except the start point. How many entries does it store for a 20 by 30 grid? Check the answer by running the code.

Show the answer.

The formula is (r + 1) times (c + 1) minus 1. For r = 20 and c = 30, that is 21 times 31 minus 1, which is 651 minus 1, so 650. Running the code gives 650 misses, which equals the number of entries stored in an unbounded cache.

Exercise 4. A function takes 2 milliseconds to compute. A cache entry takes 100 bytes. A program asks it 1000000 questions. Work out the time saved and the memory used in two cases: (a) the questions use only 10 different inputs, and (b) every question uses a different input.

Show the answer.

Case (a): the cache stores 10 answers, which is 1000 bytes, and 999990 questions are hits. Each hit saves 2 milliseconds, so the time saved is 1999980 milliseconds, which is about 2000 seconds or 33 minutes. The memory cost is negligible.

Case (b): the cache stores 1000000 answers, which is 100 megabytes. No question is a hit, so the time saved is zero. The cache costs 100 megabytes and gives nothing back. This is the case where a cache should not be used.

Exercise 5. Write a function count_steps(n) that counts the number of ways to climb n stairs when each move takes 1 or 2 stairs. The answer for n = 1 is 1 and for n = 2 is 2. Use a dictionary cache. Run it for n = 10 and n = 30, and report how many entries the cache holds for n = 30.

Show the answer.

count_steps(10) = 89
entries after n = 10: 8
count_steps(30) = 1346269
entries after n = 30: 28

The answers follow the Fibonacci pattern shifted by one, so count_steps(10) is fib(11), which is 89. The entries are for n = 3 to 10, which is 8 entries, and for n = 3 to 30, which is 28 entries.

Summary

• Memoisation stores each answer the first time it is computed, and reads it back the next time, so a repeated call costs one lookup instead of a whole new computation.
• The memory cost grows with the number of stored entries, and each entry can be large if the answers are large.
• A cache pays off when the work it avoids is large compared with the memory it holds, and a function whose inputs rarely repeat gains almost nothing from one.
• A bounded cache caps memory at the cost of extra recomputation, and the miss count shows how much extra work the cap adds.
• Common bugs come from keys that leave out an input, keys that cannot be stored, deep recursion and caches that grow without limit.