Persistent B+-tree prototype for Dict (design 1b, stage D2) — 2026-10-28

Question. Stage D2 replaces Dict k v (map[string]V, copied on every insert: O(n)) with a persistent B+-tree behind a phantom-typed handle. The review set a gate before the migration starts: 400 ns or less per insert at 1e5 keys, trying leaf widths 8, 16 and 32.

Verdict: the gate is NOT met. The best variant measured 504 ns per random insert at 1e5 keys under the Sky runtime's GOGC=400, and 622 ns under Go's default GOGC=100. The D2 migration was therefore not started, and the dict-counts program of xtask perf-gate stays red (it is not weakened).

Every number below is a line of bench.txt, produced by go test -run XXX -bench . -benchmem -count=1 . in this directory, once with the default GOGC and once with GOGC=400, on an Apple M-series laptop with Go 1.26.1. One run each: treat differences under about 10% as noise.

VariantLayoutinsert, 1e5 random keys (ns) GOGC 100 / 4001e6 get+insert, 1e5 keys (ns per update) GOGC 100 / 400
v1 bt.go, W8erased any keys + values, comparator func, exact-length slices, 3 allocs per node950 / 757820 / 664
v1, W16843 / 682666 / 543
v1, W32942 / 691628 / 475
v2 bt2.go, W8fixed [W]any arrays, one alloc per node866 / 631928 / 625
v3 bt3.go, W8keys typed K (here int, pointer-free), values any699 / 590641 / 521
v3, W16622 / 504528 / 421
v3, W32678 / 517485 / 364
v4 bt4.go, W16(key, value) pair entries760 / 559747 / 533

What the numbers say:

What would change the verdict (not done here): a transient builder for Dict.fromList / foldl-into-a-dict shapes that the compiler can prove linear, or an arena for path copies. Neither fits the review's constraints for this release.

Files: bt*.go (the four variants), bt*_test.go (a model test against a Go map for each variant, including old versions staying unchanged, and the benchmarks), bench.txt (the raw output).