statstack · research · also StatStack cache model

StatStack

StatStack estimates fully associative LRU cache miss ratios from sparsely sampled intervals between references to the same cache line.

Related Observatory article: Read on hesela.com

Mechanism: sampled intervals feed an expected stack-distance distribution, which approximates the distribution used to estimate misses. StatCache instead models random replacement. [1] [2]

Naming: the paper calls the count of intervening accesses reuse distance and the count of distinct intervening lines stack distance. Its first quantity is a request-index reuse interval minus one; immediate repetition gives zero. [1]

Averaging: thresholding an expected distance can hide misses when individual distances straddle capacity. Sampling and approximation errors are separate; smaller sampling windows can reduce phase mixing but miss longer reuse behavior. [1]

Worked example: the final A in ABBA and ABCA has request-index interval 3, but distinct-entry distances 1 and 2. At two-slot LRU capacity, one of these two reuses misses. Comparing their mean distance 1.5 with capacity 2 predicts neither miss. This is a constructed illustration of averaging, not a StatStack implementation. [3]

Relations

related
Reuse time, Reuse distance, Miss-ratio curve, SHARDS, StatCache, Average eviction time (AET)

Citations

  1. Eklov and Hagersten. StatStack: Efficient Modeling of LRU Caches. ISPASS 2010; thesis Paper I, sections I.3-I.6. (accessed 2026-11-18)
  2. Uppsala University. Efficient Modeling Technology: separate random-replacement and LRU models. (accessed 2026-11-18)
  3. Hesela. Constructed reuse intervals and mean-distance threshold example; exact event ledgers. (accessed 2026-11-18)

Further reading

  1. Hesela. Executable averaging example, using the existing bounded exact reuse evaluator. (accessed 2026-11-18)
Sources & caveats
  • Paper I was read in the author's thesis copy, PDF pages 41-66. No original benchmark data, sampler or implementation was reproduced.
  • The example checks conditional averaging only; it does not estimate StatStack accuracy or storage latency.

JSON: /data/terms/statstack.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

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