Working-set footprint
A working-set footprint is the average number of distinct data identities accessed across all complete windows of a specified length in a trace.
For n requests and a window of w requests, average the distinct counts over n-w+1 complete windows. This is a trace statistic, not the amount of resident memory. The mean that includes truncated initial windows instead averages over n endpoints; report which convention is used. [1] [3]
Finite-trace formulas retain first- and last-access corrections. A long-trace approximation cannot silently replace those terms for a short observation. HOTL explicitly states a reuse-window condition for converting footprint statistics to cache misses. [2] [1]
Hesela's exact constructed traces BBACA and ACBBA both access A twice, B twice and C once. Their complete-window footprint curves are identical: 1, 7/4, 7/3, 3, 3. Yet initially empty, fully associative, two-entry LRU caches with demand admission miss 3/5 and 4/5 respectively. Thus this average curve and these frequencies alone do not determine the finite-trace LRU miss count. These are logical examples, not measured workloads. [4]
Including truncated initial windows is not always a downward shift. At window length three, ABBBBBBB and its reversal BBBBBBBA have the same complete-window footprint 7/6, but prefix means 5/4 and 9/8. Their signed differences are +1/12 and -1/24 identities. If F is the complete mean and S_initial sums distinct counts in the first w-1 prefixes, then n*(P-F)=S_initial-(w-1)*F. This is a deterministic accounting identity, not a statistical bias estimate. [8] [3]
Relations
- related
- Working set, Miss-ratio curve
Limitations
- State the identity unit, clock, endpoint treatment and cache model before interpreting footprint as a capacity requirement. [1, 2]
- A long trace alone does not make endpoint effects small when the requested window grows with it; use the explicit window/trace-length bound and do not interpret it as a cache-miss guarantee. [8]
Citations
- Xiaoya Xiang, Chen Ding, Hao Luo and Bin Bao. HOTL: a Higher Order Theory of Locality. ASPLOS 2013, sections 2.2 and 2.7.
- Yuan et al. A Relational Theory of Locality. ACM TACO 16(3), Article 33 (2019), sections 2.4.2-2.4.6. DOI 10.1145/3341109.
- Peter J. Denning. Working Set Analytics. ACM Computing Surveys 53(6), Article 113 (2021), appendix. DOI 10.1145/3399709.
- Hesela: exact finite-window footprints and cold LRU witness; inputs, integer sums, fractions and reproduction.
- Hesela: signed endpoint ledger, conservative two-sided bound and periodic controls; generated exact examples.
Further reading
- Hesela: CC0 absence-gap footprint calculation.
- Hesela: method, limitations, tests and unchanged LRU dependency.
- Hesela: identical window footprints can hide different LRU misses.
Sources & caveats
- Primary full-text sections reviewed 2026-11-18; no author benchmark replication or new hardware measurement.
- Exact constructed examples generated from versioned CC0 code; tests independently enumerate complete and truncated windows.
- The absence-gap calculation is an equivalent form of the established boundary-aware Xiang formula, not a new algorithm.