slackfront: the worst-case-op vs space-slack frontier of a dynamic hash table

A growable open-addressing hash table has to move its entries into a bigger array sometimes. The textbook version does it all at once (a synchronous rehash), which gives a great average but a single insert that stalls for the whole table. You can de-amortize that: grow by a small factor and migrate a few slots per operation. The question this repo answers, provably and then on hardware:

• How slowly are you allowed to migrate? There is a hard floor: w * alpha >= 1, where alpha is the transient space slack (grow to (1+alpha)x) and w is the moves per insert. It is tight at w = ceil(1/alpha). Proved by pigeonhole, verified by an armed non-vacuity control.
• What does buying a flat tail actually cost on an Apple M4, and does bounding the migration even suffice? It does not, on a contiguous table, and the reason is the interesting part.

Correctness and the bound are proved (exact tests); the costs are measured (bootstrap CIs). They are kept separate.

The proved bound (pigeonhole, exact)

At a grow the table holds C live entries; the new array has C(1+alpha) slots, so alpha*C free ones. At most alpha*C inserts can happen before that array is itself full, and those inserts must also drain the C old entries, so w*(alpha*C) >= C, i.e. w >= 1/alpha. The two-array construction migrating ceil(1/alpha) slots per insert matches it. So w*alpha = Theta(1) is the whole frontier between migration rate and space slack, distinct from the textbook amortized growth-factor result and from probe-complexity lower bounds (which say nothing about resize slack).

The construction is verified exactly: differential against std::HashMap over millions of seeded insert/get/erase interleavings (get correct at every migration cursor), an exhaustive small-state check forcing two migrations, and a tightness control: w = ceil(1/alpha) - 1 is forced to grow again before the old array drains (an observable invariant break) while w = ceil(1/alpha) survives with per op moves <= w.

The cost on M4 (measured, bootstrap CIs)

Two disciplines over one shared open-addressing core (linear probing, tombstone erase, one hash, one lazily-zeroed allocator, so the only axis is resize policy): B = synchronous grow x2 (the std/hashbrown shape), D = de-amortized grow (1+alpha) at <= w moves per insert.

At N = 2^23, medians with BCa 95% CIs over 15 runs:

metric	B (synchronous x2)	D (de-amortized, alpha=0.5, w=2)
median insert	84 ns	167 ns
p99.99 insert	750 ns	6.4 us
max insert	81.3 ms [80.4, 82.0]	1.06 ms [1.05, 1.07]
get	16.3 ns	24.7 ns

B's single worst insert is a full rehash: it relocates Theta(N) entries (7.3M at N = 2^23) and stalls 81 ms, at every power-of-two threshold. D's migration is bounded to w = 2 moves, so it never rehashes, and its worst insert is 77x smaller and CI-separated. D pays for the flat tail: 2x the median insert, and +51% on lookups measured right after growth, when D is still mid-migration and every get probes both the new and old array (a fully-drained D probes one array like B, and both designs use the same % cap core, so the gap is the two-array lookup, not the indexing).

The twist: bounding migration is necessary but not sufficient

D's worst insert is 1.06 ms, not microseconds, and it still grows with N. That is not migration (bounded at 2 moves) and not rehash (D does none). It is the cost of the contiguous array itself:

• Eager initialization is O(N). A vec![Empty; cap] clone-fill touches every slot; the allocation probe measures this directly at 2.2 ms then 9.1 ms as the array quadruples (linear), which would put an O(N) stall right back into D.
• Lazy allocation removes it. Backing the arrays with alloc_zeroed (calloc, which serves large sizes from lazily-zeroed mmap pages) makes the grow allocation O(1) (measured 41 ns, flat), and the new pages fault in only as migration writes them. This is what the table does, and it is why D's worst insert dropped from ~9 ms (eager) to ~1 ms.
• The residual ~1 ms is not the allocation (the probe puts that at 41 ns): it is the page-table work of managing the O(N) contiguous array, unmapping the drained old array on the op that empties it and faulting the new one in. No migration rate removes it, because the array is contiguous.

So on a contiguous table you can have a bounded number of moves per op and still not have an O(1)-worst-case insert. Getting genuine O(1) means abandoning contiguity: an extendible table (a directory of fixed-capacity subtables, split one per grow, which Go's map adopted in golang/go#54766) never allocates or frees an O(N) array, at the cost of a directory indirection on every lookup. That corner is described here from the literature, not measured; it completes the frontier: you cannot simultaneously have an O(1) worst-case op, a near-full contiguous array, and a single-probe lookup. Each of the three designs gives up exactly one.

Reproduce

./run.sh

Needs a recent Rust (edition 2021) and Python 3 (standard library only; the CI bootstrap is pure Python). CPU only, single thread. The tests are deterministic; the timings vary run to run but the orderings and the CI-separated gaps do not.

Files

• src/lib.rs: the shared open-addressing core, the synchronous table B, the de-amortized table D, and the correctness/tightness tests.
• src/bin/bench.rs: insert-tail, get-throughput, and the allocation probe.
• sweep.py: bootstrap-CI aggregation (pure Python).
• PREREG.md: the pre-registration.
• run.sh: reproduces everything.

Scope

Apple M4, CPU only, single thread, u64 keys and values. The bound is a model result for contiguous open addressing; the numbers are this implementation. The extendible corner E is cited, not measured.

License

MIT.