Make a Dict-Based Memoization Cache Safe for Concurrent Threads

A slow, expensive function is wrapped in a module-level dictionary that memoizes its results:

cache = {}

def compute(x):
 if x in cache:
 return cache[x]
 result = expensive(x)
 cache[x] = result
 return result

compute is now called from many threads at the same time. What problems does that cause, and how would you change the code?

Clarifying Questions

• Is expensive(x) deterministic and free of side effects, or is running it twice for the same x harmful (for example, it calls a paid external service or writes data)?
• Can expensive(x) raise, and should a failure be remembered or retried on the next call?
• Is the set of distinct inputs bounded, or can the cache grow without limit?
• Which runtime is this: CPython with its global interpreter lock, a free-threaded build, or a language whose plain hash map is not safe for concurrent writers?
• Is expensive mostly waiting on I/O, or mostly using the CPU?

Part 1 — What goes wrong

Explain what can happen when several threads call compute concurrently, using concrete interleavings.

What This Part Should Cover

• The check-then-act window, and what happens when several callers miss the same key together
• Which guarantees the runtime's dictionary does and does not give under concurrent access
• The consequences when expensive is slow, non-deterministic, or has side effects

Part 2 — Fix it and choose the lock scope

Make compute safe for concurrent callers. Compare at least two places to put the lock, and say what each one costs when many threads ask for different keys versus the same key.

What This Part Should Cover

• Whether each candidate prevents duplicate computation, and whether it keeps the dictionary consistent
• What each lock scope serializes, and the effect on throughput
• What happens to waiting callers when the computation raises, so that a failure neither poisons the cache nor leaves threads blocked