# AdaptSize: check the arithmetic before replaying the cache

AdaptSize controls admission to a CDN's memory-resident hot-object cache. Its
NSDI 2017 design uses p = exp(-s/c), with size s and parameter c in the same units,
and periodically tunes c using recent object sizes and request counts.
The target is object/request hit ratio, not bytes saved. Eviction uses a concurrent
LRU variant. A rejected admission still needs to serve the miss. [1]

## An extracted C expression changes the curve

The public authors' repository at commit
`6deab4b303ed26c2e75d5efff6fea4e575a1485f` declares the parsed size as
`long`; its parameter patch declares `opt_threshold` as `uint`.
The expression passed to exp divides those integers before conversion to double.
Under the tested LP64 types, a size of 4 bytes and parameter of 8 bytes gives
1, whereas floating division gives exp(-0.5), approximately 0.606531. [2,3]

The [native C probe](admission.c) isolates that arithmetic using signed long and
unsigned int. It checks the required type widths before executing. It does not
build Varnish or execute the complete upstream module.

| Size s, bytes | Parameter c, bytes | Integer division inside exp | Floating division inside exp |
| --- | --- | --- | --- |
| 4 | 8 | 1 | 0.606531 |
| 7 | 8 | 1 | 0.416862 |
| 8 | 8 | 0.367879 | 0.367879 |
| 12 | 8 | 0.367879 | 0.223130 |
| 16 | 8 | 0.135335 | 0.135335 |

For nonnegative s and positive c in this experiment, the integer expression is
exp(-floor(s/c)). Values below c all produce 1. Casting the already-computed
quotient to double does not recover its discarded fraction. The corrected
comparison casts an operand **before** division. Whole multiples are useful
controls because the two expressions agree there.

These are computed admission probabilities, not observed hit ratios. No random
generator is sampled and no object residence, eviction, tuning, parsing, overflow,
concurrency or network workload is modeled. The source comparison does not
establish which code produced the paper's measurements or invalidate those
measurements. The repository describes its system as a proof of concept. [2]

## Reproduce

Requires Python 3, a C11 compiler named cc, libm, 64-bit long and 32-bit unsigned int.

```sh
python3 -B verify.py
python3 -B -m unittest discover -s . -p test_verify.py
python3 -B -O -m unittest discover -s . -p test_verify.py
```

Download [verify.py](verify.py), [test_verify.py](test_verify.py),
[admission.c](admission.c) and [results.json](results.json) into one directory.
The verifier compiles with -O0 and -O2 in temporary directories, checks all
2,144 (s,c) pairs at each level, and compares 11 recorded boundary cases.
It rejects missing rows, reordered identities, nonfinite results and changed
source hashes. The full grid is c = 1..32 and s = 0..4c. Zero is an arithmetic
control, not a claim about cache eligibility. This is deterministic evidence;
there is no statistical confidence interval or performance measurement.

## Research context

The paper evaluates historical CDN traces from two servers, using simulations
and a Varnish-based testbed. Its memory-cache objective and disk-cache byte
objective have different denominators. The model and those workloads do not
establish a universal benefit for SSD caches or today's proxy configurations. [1]

## Sources

1. Berger, Sitaraman and Harchol-Balter. [AdaptSize: Orchestrating the Hot Object Memory Cache in a Content Delivery Network](https://www.usenix.org/system/files/conference/nsdi17/nsdi17-berger.pdf). NSDI 2017, pp. 483-498, sections 4-6.
2. Authors' pinned [module](https://github.com/dasebe/AdaptSize/blob/6deab4b303ed26c2e75d5efff6fea4e575a1485f/AdaptSizeVmod/src/vmod_autoparam.c), [parameter patch](https://github.com/dasebe/AdaptSize/blob/6deab4b303ed26c2e75d5efff6fea4e575a1485f/VarnishPatches/params.patch) and [README](https://github.com/dasebe/AdaptSize/blob/6deab4b303ed26c2e75d5efff6fea4e575a1485f/README.md). BSD-2-Clause repository; no full upstream source is redistributed here.
3. WG14 [N1570](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf), sections 6.3.1.8 and 6.5.5: arithmetic conversions and integer division.

Source access and native capture: 2026-11-18.
