The One Cache With No Staleness
Every lesson in this chapter so far has been mostly about staleness. How long a copy stays right, what happens when it stops being right, and how you find out. This one is different.
A pure function returns the same result for the same arguments forever, so a stored result cannot become incorrect. Everything the rest of this chapter worries about simply does not apply.
The absence of staleness is why memoisation gets applied so freely, and why its two real costs go unexamined. Both of them are measurable.
The Lookup Is Not Free
Memoisation is usually drawn as a shortcut. It is really an extra layer, and on a miss all of that overhead happened and the real function still ran, so a miss is strictly slower than not having memoised at all.
The question is never whether memoisation is fast. It is whether the work you skip on a hit exceeds the work you add on every call. The script at scripts/labs/memo/crossover.py measures where that line sits.
At 67 percent hits and one operation of work, memoising measured 1.3 times slower than not , because the key construction, hash and probe cost more than the work they replaced.
The flat line is one divided by one minus the hit rate, which is the arithmetic bound. The measurement sitting just above it is expected, because a hit also skips the function call itself, and a result far above it would mean the benchmark was wrong.
Memoisation cannot make a function faster than its miss rate allows. At a 67 percent hit rate the very best it can ever do is about three times, however expensive the function is.
Nothing changed except how many distinct arguments were used. Count the distinct arguments a function will actually see before memoising it: a function called a million times with a million different arguments gains nothing and stores a million entries.
The Table Is Never Freed
In the measured run, 20,000 distinct arguments produced a table of 19,023 entries, and nothing in the pattern would ever have removed any of them. It presents as a slow memory climb that a restart fixes, which sends people looking in the wrong place.
Because traffic is usually concentrated on a small head of arguments, a modest limit keeps almost all the benefit while making the worst case impossible. Its failure mode is a lower hit rate, which is a graph, and not a crash.
Purity Is Assumed More Often Than Checked
The mutable return value is the subtlest. Handing back the same list on every hit means any caller that modifies it has silently modified your cache, and every later caller receives the modified version. Return a copy, or return something immutable.
An impure memoised function looks like it works. It returns the right answer during development, when the underlying thing has not changed yet, and returns a stale one in production hours later with no expiry to save it.
Concurrency, Alternatives and the Textbook Case
This is the stampede from earlier in the chapter with the correctness half removed. Because the function is pure the results agree, so it shows up only as unexplained CPU, usually right after a restart.
Here memoisation changes the complexity class, from exponential to linear. The hit rate is effectively total and the arguments are a small bounded range. Almost no real function has all three of those properties.
Where It Pays, and How to Check
Look at the argument space before the function body. Most good cases are recognisable purely from the signature: a function taking a short string from a fixed vocabulary is a candidate, and a function taking an identifier is not, whatever it does inside.
functools.cache is exactly lru_cache(maxsize=None), which never evicts. Reach for the bounded version by default: the difference is one argument, and the failure mode of getting it wrong is the process being killed.
Quick Check
Knowledge Check
4 questions - Score 80% to pass
You memoise a very cheap pure function that sees 20,000 distinct arguments across 60,000 calls. What happens to performance?
A memoised function has a 67 percent hit rate. What is the most speedup it can ever achieve?
You put an unbounded memo decorator on a method of a class. What is the risk beyond memory growth?
Which of these functions is safe to memoise?
