Skip to main content
Vansh Verma
← Lab

slackfront

confirmedcertificateRust · Apple M4Systems & data structuresJuly 14, 2026

the question

What is the tight frontier between migration rate and space slack for a de-amortized open-addressing hash resize, and what does a flat insert tail cost on M4?

what came out

Confirmed. Any contiguous open-addressing table growing by (1+alpha) at at most w moves per insert must satisfy w*alpha>=1, proved by pigeonhole and tight at w=ceil(1/alpha). On M4 the de-amortized worst insert is 1.06ms versus 81.3ms for synchronous rehash, but bounding migration is necessary not sufficient: a residual O(N) page-table cost remains.

method & receipts

  • Result: confirmed
  • Pre-registered — the prediction was written down and committed before the run.
  • Reproducible — one script re-runs the whole thing from scratch.
  • Tested — a correctness/benchmark suite ships alongside the code.

→ read the code and re-run it

github.com/v-code01/slackfront