statcache · research · also StatCache cache model

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

  1. Berg and Hagersten. StatCache: A Probabilistic Approach to Efficient and Accurate Data Locality Analysis. ISPASS 2004, sections 2-4. (accessed 2026-11-18)
  2. Uppsala University. Efficient Modeling Technology: random-replacement and LRU models. (accessed 2026-11-18)
  3. Hesela. Exact random-replacement state ledgers and cold-start denominators; constructed traces. (accessed 2026-11-18)

Further reading

  1. Hesela. Bounded exact random-replacement evaluator in Python. (accessed 2026-11-18)
  2. Hesela. Independent path-enumeration tests and accounting checks. (accessed 2026-11-18)
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.

JSON: /data/terms/statcache.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. StatCache. Hesela. 2026-11-18. https://hesela.dev/terms/statcache/