StatCache
StatCache estimates fully associative random-replacement cache miss ratios from sampled intervals between references to the same cache line.
Mechanism: for L full cache slots, a resident line survives n independent uniform evictions with probability (1 - 1/L)^n. StatCache approximates the intervening miss count using a local miss ratio, solves an implicit equation and combines short-window estimates. [1]
Naming: its reuse distance counts all intervening references, not distinct lines. First references have no reuse interval, and the estimator excludes cold misses. The later StatStack model targets LRU instead. [1] [2]
Worked example: in an empty two-slot cache, ABCA has three certain cold misses and a 1/2 chance of missing the last A. The expected total is 3.5 misses across four requests, or 7/8. Excluding cold misses gives 1/8 per request, but 1/2 per reuse. B fills a free slot; only C can evict A before its reuse. [3]
Interpretation: ABBA has the same two intervening references before the last A but no eviction. LRU misses all four ABCA requests. The exact synthetic ledgers illustrate accounting and policy differences, not StatCache accuracy or storage latency. [3]
Relations
- related
- StatStack, Reuse time, Miss-ratio curve
Citations
- Berg and Hagersten. StatCache: A Probabilistic Approach to Efficient and Accurate Data Locality Analysis. ISPASS 2004, sections 2-4.
- Uppsala University. Efficient Modeling Technology: random-replacement and LRU models.
- Hesela. Exact random-replacement state ledgers and cold-start denominators; constructed traces.
Further reading
- Hesela. Bounded exact random-replacement evaluator in Python.
- Hesela. Independent path-enumeration tests and accounting checks.
Sources & caveats
- The full eight-page paper was reviewed. The original sampler, SPEC workloads and benchmark results were not reproduced.
- The example uses exact fractions over every possible replacement path, not Monte Carlo sampling or measured device behavior.