# Finite-window footprints

CC0-1.0 for Hesela's code and constructed examples. Source papers retain their own rights.
Generated 2026-11-18. No hardware measurement, workload sample or author benchmark replication.

## Definitions and reproduction

The input is a nonempty finite sequence of string identities of equal-size logical objects.
Time is the request index, not seconds. There is no inferred history before the first request.
For window length w and trace length n, count distinct identities in each of n-w+1
complete windows. Store their integer sum S and the reduced fraction S/(n-w+1).
Separately average the trailing windows at all n endpoints, truncating the first w-1
windows at the start of the trace. The denominator of this second mean is n.

Run `node --test model.test.mjs`, then `node capture.mjs --check` with model.mjs,
model.test.mjs, capture.mjs and evidence.json in one directory and the existing
https://hesela.dev/research/reuse-distance.mjs one directory above it. The evidence records the SHA-256 of model.mjs.

## Exact implementation

For each identity, collect the request counts g in its absence gaps: before the
first appearance, between appearances and after the last. A gap contains
max(g-w+1,0) complete windows without that identity. If D identities occur, then

S(w) = D*(n-w+1) - sum_over_all_gaps max(g-w+1,0).

Histogram the gaps, then use descending suffix counts and weighted sums to obtain
every S(w). Prefix-window totals use forward runs ending at the next occurrence
or trace end: each occurrence contributes min(w,run_length). A second histogram
computes these totals. With expected constant-time Map operations, both curves
take O(n+D) time and O(n+D) space, including output; the direct test oracle instead
constructs Sets for every window. The one-million-request limit keeps integer
arithmetic exact in JavaScript and bounds allocation; this is not a streaming profiler.
No performance benchmark is claimed.

The gap calculation is an equivalent absence-count form of the boundary-aware
Xiang formula described in HOTL section 2.7. It is not a newly discovered algorithm.
Yuan et al. (2019), sections 2.4.2-2.4.6, distinguish finite-trace terms and endpoint
corrections; Denning (2021), appendix, distinguishes complete-window footprint
from the mean with truncated initial windows. These are different denominators.

## Interpretation

ABCABC has four complete length-three windows, each containing three identities:
footprint 3. Its six prefix-window counts are 1,2,3,3,3,3: mean 5/2.
ABBBA has complete-window footprints 1,3/2,5/3,2,2. Consecutive increments from
length two to three and three to four are 1/6 and 1/3. Thus this exact finite curve
does not justify a blanket concavity assumption.

HOTL section 2.7 explicitly conditions footprint-to-miss conversion and uses
a long-trace approximation. For ABCABC in an initially empty three-slot fully
associative demand-admission LRU cache, the first three references miss and the
last three hit: 3/6. The zero slope between footprint windows three and four does
not erase those cold misses. This is an initial-state/boundary example, not an
accuracy evaluation of HOTL or a claim that the published conditional theory fails.

## A complete-footprint collision

The constructed traces BBACA and ACBBA have the same counts A=2, B=2, C=1.
At all five complete-window lengths their average footprints are identical:
1, 7/4, 7/3, 3, 3. Yet a cold two-slot LRU cache misses 3/5 and 4/5 respectively.
BBACA hits on its second B and final A; ACBBA hits only on its second B.
This proves that the complete-window average footprint curve, even accompanied
by these identity frequencies, does not determine cold finite-trace LRU misses.
It does not test an estimator on a representative storage workload.

The witness was found by exhaustive ternary-trace search in increasing lengths
through five, then relabelled without changing equality, counts or misses.
Tests independently enumerate windows for all 3279 ternary traces of lengths
one through seven and compare the existing reuse-distance profiler against a
separate LRU queue at capacities 0..3 (13116 comparisons). No minimality or new
theorem claim is made. The LRU dependency remains unchanged.

## Signed endpoint accounting

Let F be the complete-window mean, P the mean over all n truncated-prefix
endpoints, and S_initial the sum of distinct counts in prefixes of lengths
1 through w-1. Splitting the sum gives the exact identity

n*(P-F) = S_initial - (w-1)*F.

Denning's appendix gives this decomposition. The signed ledger below is Hesela's
worked deduction, not a new theorem or a measured estimator bias. For ABBBBBBB
at w=3, complete counts sum to 7 over 6 windows; S_initial=3. Thus F=7/6,
P=10/8=5/4 and P-F=1/12. Reversing the trace keeps every complete-window count
distribution unchanged but changes S_initial to 2: P=9/8, P-F=-1/24.
Including short initial windows therefore need not lower the mean.

If m identities occur and k=min(w,m), every nonempty counted window has between
1 and k identities. Consequently |P-F| <= (w-1)*(k-1)/n. This conservative
two-sided deterministic bound follows by bounding each initial count and F;
it is not a confidence interval and need not be tight. The bound is zero for
w=1 or m=1. A one-sided inequality alone should not be reported as an
absolute-error guarantee.

For a repeated cycle of p different identities with n>=p requests, every full
window contains k=min(w,p) identities. The initial sums are sums of min(t,p).
Therefore F=k and P-F=-k*(k-1)/(2*n), for every 1<=w<=n, including an incomplete
last cycle. For ABC repeated 1, 2, 10 and 100 times at w=3, the deficits are
1, 1/2, 1/10 and 1/100 identities. This is a controlled family, not a storage trace.
If all n identities are distinct and w=n instead, F=n and P=(n+1)/2; relative
difference tends to one half, not zero. Trace length must be interpreted together
with window length and the access pattern.

Reproduce with `node --test endpoints.test.mjs` and
`node capture-endpoints.mjs --check` alongside the existing model.
The ledger serializes reduced rational integers as strings and uses BigInt for
intermediate cross-products. Its JSON records hashes of the model and tests.
The unchanged absence-gap implementation is independently checked by direct
window enumeration; all 21,324 trace/window pairs over ternary traces of lengths
1..7 check the identity, bound and reversal invariance. Periodic controls and
large-integer arithmetic have separate tests. There is no cache-policy or
hardware model in this endpoint calculation.

## Sources

- Xiang, Ding, Luo and Bao. HOTL: a Higher Order Theory of Locality. ASPLOS 2013,
  sections 2.2 and 2.7. https://www.cs.rochester.edu/~cding/dpal/files/Xiang%2B_ASPLOS13.pdf
- Yuan, Ding, Smith, Denning and Zhang. A Relational Theory of Locality.
  ACM TACO 16(3), Article 33, 2019. DOI 10.1145/3341109.
  https://denninginstitute.com/pjd/PUBS/TACO-2019.pdf
- Denning. Working Set Analytics. ACM Computing Surveys 53(6), Article 113,
  2021, appendix. DOI 10.1145/3399709.
  https://denninginstitute.com/pjd/PUBS/working-set-analytics-2021.pdf

All three sources accessed 2026-11-18. Read relevant full-text sections, not just abstracts.
