Code Review: Thread Safety of a Python Compute-and-Cache Function

You are shown a short piece of Python and asked: "Suppose someone sent you this code in a code review. What would you say?" The function returns a cached result if one exists. Otherwise it performs an expensive computation, stores the result in the cache, and returns it. The snippet below is a minimal reconstruction of that flow. `expensive_computation` stands for a slow, deterministic call. ```python cache = {} def compute(x): if x in cache: return cache[x] result = expensive_computation(x) cache[x] = result return result ``` Assume `compute` is called concurrently from multiple threads in the same Python process. The interviewer pushes the discussion one layer at a time. ### Clarifying Questions - Is `expensive_computation` free of side effects, so that running it twice for the same input only wastes work? Or would a duplicate call be incorrect, for example because it charges a customer or writes to an external system? - Are the callers threads in one process, or separate processes or machines that an in-process lock cannot coordinate? - If the computation raises an exception, should the failure be cached, or should the next caller retry? - Must the cache stay bounded in memory, or can it grow with every distinct input? - Which Python runtime is this: standard CPython with the global interpreter lock, or a free-threaded build? ### Part 1 — Initial Review Comments What feedback would you give on this code, given that it runs under concurrent calls? Describe the problem with a concrete sequence of events. ```hint Interleave two callers Write out the steps two threads take when both call `compute` with the same new input at nearly the same time. ``` #### What This Part Should Cover - The specific interleaving that causes the problem, and its consequences for cost and correctness. - Other review comments the code invites beyond concurrency. ### Part 2 — Guarantee a Single Computation Add locking so that concurrent callers for the same input trigger `expensive_computation` only once. Walk through why your version is correct when several threads miss at the same moment. ```hint Consider what changes while you wait A thread that finds the cache empty may have to wait for the lock. Think about what another thread could have done during that wait. ``` #### What This Part Should Cover - Which checks and writes the lock protects, and why each one is necessary. - The behavior of threads that were waiting for the lock when the first computation finished. ### Part 3 — Choose Where the Lock Goes On which lines should the lock be acquired and released? What happens if the lock is held too broadly, and what happens if it covers too little? ```hint Look at the cost of a hit Ask what a caller whose result is already cached has to wait for under each placement. ``` #### What This Part Should Cover - The effect of an overly broad lock on cache hits and overall throughput. - The effect of an overly narrow lock on correctness. - A refinement that avoids blocking computations for unrelated inputs. ### Part 4 — Python Dictionaries Under Concurrent Access How does a Python `dict` behave when multiple threads read and write it at the same time? Can a reader see an old value or a new value, and can it see something in between? ```hint Separate single operations from sequences Distinguish what a single dictionary lookup or assignment guarantees from what a sequence of them guarantees. ``` #### What This Part Should Cover - What a single dictionary operation guarantees in CPython, and which runtime details that relies on. - Why a check followed by an action is still unsafe. - Which value a concurrent reader can observe relative to a write. ### What a Strong Answer Covers - A precise description of the concurrency problem and a fix that is correct under concurrent misses without serializing cache hits. - Awareness of the cost of holding one lock during a slow computation, and a per-input alternative. - Accurate Python-specific reasoning about the global interpreter lock and atomicity, without claiming that it makes the original code thread-safe. - Error handling, memory growth, and the limits of an in-process lock. ### Follow-up Questions 1. If `expensive_computation` raises for one input while other threads are waiting on that input, what should the waiting threads see, and when should the input be retried? 2. How would you write a test that reliably shows the duplicate computation before the fix and its absence after it? 3. How does the design change if the cache moves to a shared store used by several processes or machines? 4. What goes wrong with a non-reentrant lock if `expensive_computation` itself calls `compute` for a smaller input?