# GreedyDual-Size: one offset, the same cache decisions

Constructed arithmetic cases, not a trace benchmark or device experiment.
See the [corpus record](https://hesela.dev/terms/greedydual-size/) for context.

## Reproduce

Python 3 standard library only. Put model.py, test_model.py and results.json in
the same directory, then run:

```sh
python3 -B model.py
python3 -B -m unittest -v test_model.py
python3 -B -O -m unittest -v test_model.py
```

The first command prints the deterministic packet. `model.py --write` regenerates it.
Tests compare every recorded step, not only aggregate hit counts.

## Method

The direct implementation subtracts the victim's residual priority from every
surviving resident. The second stores priorities relative to a common offset.
Their invariant is `residual[x] = priority[x] - offset`.
Admission and hit refresh restore the same cost density in both representations.

Objects have immutable integer sizes and nonnegative integer costs. Every object
fits individually. Both start empty, admit on misses and choose the alphabetically
first ID on a priority tie. Multiple victims can be needed for a single admission.
Fractions are exact; neither floating-point rounding nor an epsilon breaks ties.

Six designed examples cover fractional density, multiple evictions, hit refresh,
two cost choices and zero-cost ties. A bounded exhaustive test enumerates
9,840 trace/capacity combinations: all three-ID traces of length 0 through 7 at
capacities 3, 4 and 5 with one declared mixed-size/cost catalogue.
This does not exhaust all valid inputs.

## A Finite-Trace Counterexample

Use capacity 4, object sizes A=1, B=3, C=1 and requests A,B,C,A,C,A,B.
Both runs start empty and use the same declared identifier-order tie rule.
Only the cost definition changes.

| GDS cost choice | Request hits / requests | Hit size units / requested | Missed size units |
| --- | --- | --- | --- |
| Unit cost for every object | 3 / 7 | 3 / 11 | 8 |
| Cost equals object size | 2 / 7 | 2 / 11 | 9 |

Setting a byte objective does not guarantee the best byte-hit outcome on every
finite trace. This designed witness refutes that stronger claim; it does not
estimate which choice usually performs better. The original algorithm is not
being claimed defective. These counts are generated from the six-case packet
and checked against fixed expectations.

Files: [model](model.py), [tests](test_model.py), [all inputs and results](results.json).

## Limits

A separate 64-resident check replaces 63 survivor-priority assignments
with one offset assignment on the next miss. Both models still scan for a victim.
Counters exclude search, input validation, refresh, accounting and output snapshots.
There is no measured runtime speedup or production-readiness claim.
Counts include subtraction/assignment by zero when a tie leaves a zero debit.

Request-hit, byte-hit and miss-cost totals use different denominators or units.
Cost totals from examples with different cost definitions are not measurements
of a common physical quantity. No denominator means no ratio.

Excluded: mutable objects, TTL, stale-data validation, admission bypass, partial
reads, prefetching, writeback, concurrency, compressed size and queueing delay.

## Sources And Rights

- [Cao and Irani, USITS 1997](https://www.usenix.org/legacy/publications/library/proceedings/usits97/full_papers/cao/cao.pdf), section 4 and Figure 5.
- [Young, Algorithmica 2002](https://www.cs.ucr.edu/~neal/Young02Online.pdf), section 1 and Figure 1; DOI 10.1007/s00453-001-0124-5.
- [DULO, FAST 2005](https://www.usenix.org/legacy/event/fast05/tech/full_papers/jiang/jiang_html/index.html), section 3.4: separate disk-sequence adaptation.

Consulted 2026-11-03. Original papers' traces, figures and performance measurements
are not redistributed. Code and inputs are Hesela-authored; this packet does not
grant rights to third-party papers.