ben-manes / caffeine / #5687

100%

master: 100%

push

github

Adapt the window by hit density with starvation-guarded probes

Large caches size the admission window by the within-sample hit density
of the two regions, ln(windowDensity / mainDensity), taking proportional
steps that are immune to the cross-sample hit rate swings of a phasey
workload. The signal is resident-only, so a region earning ~nothing is
its blind state: it cannot see what a different split would earn, and
holding such a position can pin the window at an extreme (constructible
steady-state workloads pinned it ~28pp below LRU at any scale).

Starved samples at a blind corner therefore probe by hit rate. Walks
are bounded by a sample budget, by a reversal that crosses back through
the probe's start, and by an absolute hit rate veto that undoes damage.
An endpoint is adjudicated under strict confirmation: an up probe is
kept only when its window out-earns, per slot, main's marginal rate,
the probation density frozen when the probe armed. Capacity claimed
from main displaces probation's coldest entries, main's average is
dominated by its protected core and vetoes winning positions, and the
walk's own demotions enrich the live probation rate into an absorbing
false veto, which is why the baseline is frozen; down probes keep the
average-density comparison, the window having no marginal substructure
to price against. A crash re-arms the refractory without doubling,
since an exogenous workload shift is indistinguishable from probe
damage and mispricing it would starve the re-exploration the shift
calls for. Escalating commitment resolves the stray-exit dilemma:
first-round probes exit cheaply when the watched region earns without
confirmation (stray and transferred hits scale with a region's size,
and thin-signal workloads correctly at the floor must not pay deep-walk
displacement), while each adjudicated failure lengthens the refractory
ladder and its deeper rungs commit the walk past the stray zone,
converting a deep silent reuse band from an abso... (continued)

4312 of 4323 branches covered (99.75%)

208 of 208 new or added lines in 6 files covered. (100.0%)

8611 of 8613 relevant lines covered (99.98%)

1.0 hits per line