reuse-distance · research · also LRU stack distance, distinct-reference distance

Reuse distance

Reuse distance counts distinct identities accessed strictly between consecutive references to the same cache entry.

Immediate repetition has distance zero; a first appearance has no finite distance in a cold-start trace. Under equal-size, fully associative LRU with immediate demand admission, a reuse hits when its distance d is less than capacity C. Equality is a miss. [1]

Some literature instead reports a one-based stack position s = d + 1, which hits when s <= C. Check the convention before comparing values or thresholds. [2]

In 0,1,1,1,0 the final 0 has distance 1; in 0,1,2,3,0 it has distance 3. Both have three intervening requests, so request count alone does not give distinct-entry distance. [3]

Relations

related

Least recently used replacement, Miss-ratio curve, Cache inclusion property, SSD mapping cache

Citations

1. Ding and Zhong. Reuse Distance Analysis. UR-CS-TR-741, February 2001, section 2.1 and Figures 1-3. (accessed 2026-10-19)
2. Wires et al. Characterizing Storage Workloads with Counter Stacks. OSDI 2014, sections 2 and 3.2. (accessed 2026-10-19)
3. Hesela. LRU sizing from distinct-entry reuse distances; constructed examples. (accessed 2026-10-19)

JSON: /data/terms/reuse-distance.json