ben-manes / caffeine / #5673

100%

master: 100%

push

github

Make CampPolicy faithful to the CAMP reference

The prior implementation diverged from the published algorithm and
the authors' reference (scdblab/CAMP): the cost/size ratio was
truncated without the paper's scale-by-max-size step, collapsing
every sub-1 ratio to 0; priority was stored per queue rather than
per entry; the inflation value L was re-derived (and could deflate)
on each hit instead of advancing monotonically on eviction; and each
queue was keyed on its most-recent entry rather than its head.

Mirror the reference: scale the ratio by the largest observed size
before rounding, store H = L + cost per entry, advance L to the new
minimum on eviction, and key each queue on its head. Validated
bit-for-bit against the reference (with its intended cost tie-break)
across weighted and penalty traces.

Add a camp.tie-break setting: "cost" (default, matches the reference)
or "lru" (the paper's stated tie-break). The reference builds a cost
comparator but never wires it to its heap, so it ships an arbitrary
tie-break; cost matches its intent.

4192 of 4203 branches covered (99.74%)

8472 of 8475 relevant lines covered (99.96%)

1.0 hits per line