When does memoizing a trip planner's route-distance lookup stop paying for the memory it holds?
answer
- space bought, time saved
- the hit rate decides everything
- lookup cost versus computation cost
- cheap on the second demand only
- unique arguments make it strictly worse
basics
~20 sMemoization buys time with space, so it pays only when keys repeat often enough. It stops paying when arguments are near-unique, when the computation is cheaper than building and comparing the key, or when retained entries starve the rest of the process.
solid answer
~50 sA memo trades space for time, and the trade is arithmetic. Without it every call costs the full computation `c`; with it a call costs a lookup `l` plus `c` on a miss, so the memo wins roughly when `hit_rate * c` exceeds `l` plus the amortised cost of holding the entries. That makes four ways for it to stop paying: arguments that barely repeat, so the hit rate is near zero and you pay lookup and memory for nothing; a computation so cheap that hashing and comparing a composite key costs more than it saves; entries retained long after their last use, which charges the rest of the process for memory it needed; and a working set larger than a capped table, so entries are evicted just before they would have been hit. Note that it makes the second demand cheap, not the first.
go deeper
Remember the shape of the deal: you keep answers around so you do not compute them twice. It only helps if the same arguments actually come back, and the memory you keep is not free.
Be able to state the comparison: expected cost becomes a probe plus the computation on a miss, so the memo wins when hit rate times computation cost beats the probe. Then name the cases where that fails.
Bring numbers from a running system: hit rate, distinct keys against calls, entry footprint, and the latency distribution rather than the mean. Be ready to say you removed a memo because the traffic had no repetition.
The judgment is where repetition is worth manufacturing - normalising keys, scoping caches to a unit of work, pre-populating a known hot set - against simply making the computation cheaper for everyone, which helps the first caller too.
## The trade in one line Memoization spends memory to avoid repeating work. Purity is what makes the spend legal - a stored result of a function of its arguments can never be wrong - but legal is not the same as worthwhile. The question is always whether the work you avoid is worth more than the space and bookkeeping you took on. ## The arithmetic Let `c` be the cost of computing one route distance, `l` the cost of forming the key and probing the table, and `h` the fraction of calls that find an entry already there. - Uncached, the expected cost per call is `c`. - Cached, it is `l + (1 - h) * c`. The memo is worth it when `h * c > l`, plus whatever the retained entries cost the rest of the system. Two consequences fall straight out. First, a low hit rate is fatal no matter how expensive the computation is: at `h = 0` you pay `l + c` on every call, strictly worse than not caching. Second, memoization changes the cost of the **second** demand for a key, never the first - the first caller for a pair of stops pays full price, so a cold table leaves the slow tail of your latency distribution exactly where it was. ## The four ways it stops paying 1. **Keys barely repeat.** The hit rate is a property of the traffic, not of the function. Distances between named stops repeat heavily; distances between raw coordinates typed by users repeat almost never. Any key that folds in a request identifier, a session, or a timestamp makes every call unique and guarantees `h` near zero. 2. **The computation is cheap relative to the key.** Building a composite key, hashing it and comparing it on collision is real work. When the underlying computation is a few arithmetic steps, the memo can be measurably slower than recomputing while also using more memory. 3. **Retention outlives usefulness.** Yesterday's stop pairs still occupy the table. The cost does not show up at the call site; it shows up as less memory for everything else in the process and more work for whatever reclaims memory. 4. **The working set exceeds a capped table.** Cap the table and entries can be evicted just before their next use. You then pay the bookkeeping of a cache and collect almost none of the hits - the worst of both arrangements. ## Which way each factor pushes | factor | pushes toward memoizing | pushes against | |---|---|---| | repeat rate of arguments | the same few pairs asked constantly | nearly every call a fresh pair | | cost per computation | a search or a traversal | a handful of arithmetic steps | | key size and shape | a small pair of stable identifiers | a large composite that must be built each call | | number of distinct keys | bounded by a stop catalogue | unbounded, growing with traffic | | memory headroom | plenty, and the entries are small | tight, with other work competing for it | ## How to tell which case you are in Measure rather than argue, because every term above is observable: - **hit rate** - the single most decisive number, and the cheapest to collect; - **distinct key count against call count** - if they are close, the traffic has no repetition to exploit; - **cost per computation against cost per lookup** - time both, on the real key shape; - **entry size times entries retained** - the memory the rest of the process no longer has; - **the latency distribution, not the mean** - a memo flatters the average while the first-caller tail is untouched. ## What the trade is not It is not a correctness lever: for a pure lookup, no setting of the size, the eviction policy or the lifetime can produce a wrong answer, which is exactly why this stays a benchmarking question. It is also not a substitute for a cheaper algorithm. If the route computation is quadratic in the number of stops, memoizing hides it for repeat callers while the first caller for every new pair still waits. And it is not free concurrency-wise: a table shared by many callers has to be coordinated, and that coordination is part of `l`. The honest summary is that memoization is a bet on repetition. Purity tells you the bet is safe to place; only the traffic tells you whether it wins.
- Which single measurement would you collect first before keeping or removing a memo on this lookup?The hit rate. Every other term in the trade is dominated by it: at a high hit rate an expensive computation is avoided most of the time, and at a hit rate near zero the memo costs a probe plus the full computation on every call and is strictly worse than no cache. Distinct key count against call count tells you the same story if hit rate is not instrumented.
- Why can a memo improve average latency while leaving the slow tail of requests untouched?Because it makes the second demand for a key cheap, not the first. Every key's first caller pays the full computation, so the tail of the distribution is made of cold-key requests and stays exactly where it was. Only pre-populating the table for the keys you expect moves that tail, and that has its own cost.
- The team adds a request identifier to the memo key so entries can be traced. What happens?Every call becomes a distinct key, so the hit rate collapses to zero. The table then grows one entry per request while every caller still pays the full computation plus the probe - a leak wearing a cache's clothing. Tracing information belongs beside the entry, never inside the key.
saying these in an interview costs you the question
- Assumes caching is automatically worth it because the function is pure.
- Ignores hit rate and argues only from how slow the computation is.
- Thinks a memo lowers the latency of the first call for a key.
- Treats the memory held by retained entries as costing nothing.
- Puts a request identifier or timestamp in the key and expects hits.
- Believes a size cap can make results wrong rather than just slower.