Golang maps after Swiss Tables

Gábor Koós on the map-internals change that shipped in Golang 1.24: the bucket-plus-overflow hash table was replaced with a design derived from Abseil's Swiss Tables. The language surface did not move at all — map[K]V, make, indexing, delete, range all behave as before — so the whole thing is invisible until you look at a profile.

What the old design was

Each map owned an array of buckets, each bucket holding up to 8 key/value pairs plus a tophash array used to reject non-matching slots before comparing keys. Overflowing a bucket allocated another one and chained it:

type bmap struct {   // bucket with 8 slots
	tophash  [8]uint8
	keys     [8]K
	values   [8]V
	overflow *bmap
}

The design was not broken. It supported incremental growth — during a resize the map kept both bucket arrays and evacuated old buckets lazily as operations touched them, so nobody paid for a full rehash in one call. What it cost was locality. Once hot buckets started spilling, a lookup walked a pointer chain across non-contiguous memory, and the practical load-factor ceiling sat around 81% (roughly 6.5 of 8 slots) before collision and growth pressure got expensive.

What Swiss Tables do differently

Two ideas: compact per-slot metadata, and contiguous groups. A key is hashed once and the hash split — h1 picks the starting group, h2 becomes a short fingerprint stored in a control byte alongside the slot's state (empty, deleted, occupied). A group is 8 slots with its 8 control bytes packed together, so one tight operation reads the state and fingerprint of every slot in the group.

Lookup then never touches key bytes speculatively:

g = startGroup(h1)
for {
	matches = matchFingerprint(ctrl[g], h2)
	for each pos in matches {
		if keys[g][pos] == key { return vals[g][pos] }
	}
	if hasEmpty(ctrl[g]) { return not found }
	g = nextGroup(g)
}

The hasEmpty termination is what makes it correct rather than merely fast: in open addressing, hitting an empty slot proves the key was never inserted along this probe sequence, because insertion would have taken that slot first. Deletion doesn't compact — it writes a tombstone, since immediate compaction makes single deletes expensive and can break probe continuity. The bill for that arrives later, as tombstone density lengthening probes until a growth or reorganization pass cleans up.

Because probe work stays a linear scan over compact metadata, useful load factors move up into the high 80s (the figure usually quoted for 8-slot groups is 87.5%), which means less per-entry overhead and fewer growth events for the same number of keys.

Notably, Golang does not use SIMD for the control-byte scan the way Abseil's C++ implementation does on x86. Per the cockroachdb/swiss README, dropping into Golang assembly for the probe loop carries non-trivial function-call overhead, so the runtime uses SWAR (SIMD within a register) instead. The locality argument, not the vector instructions, is where the win comes from — which is the same lesson as false-sharing-alignment-128, where the observable effect of cache-line layout depends entirely on what the microarchitecture underneath is doing.

The Golang-specific half

A straight Abseil port would not have worked. Classic open-addressing tables resize by allocating a bigger table and reinserting everything, and a hot request path cannot absorb an occasional full-table rehash. So storage is organized as several smaller Swiss-style tables behind a directory, conceptually extendible hashing: high hash bits select a segment, probing happens inside it, and when a segment crosses its threshold only that segment splits and the directory entry is updated. Growth stays local, memory movement is bounded to the splitting segment, and the directory update is cheap.

That segmentation also carries the two constraints that have nothing to do with speed. Iteration ordering in Golang is deliberately loose but not arbitrary — the runtime cannot expose torn state or lose entries that should still be visible — so iterators are tied to map-internal versioning and traversal metadata that survives entries moving as segments split. And keys and values can contain pointers, so every relocation has to stay correct under the write barrier; smaller relocation steps mean a smaller blast radius per barriered write.

The numbers, and the gap between them

Michael Pratt's summary on the tracking issue (golang/go#54766) reports large-map access and assignment around 30–35% faster, iteration about 10% faster overall and up to roughly 60% faster on low-load large maps, and a geometric-mean speedup of about 1.5% on the Sweet full-application benchmark suite. The 1.24 release notes attribute about 2–3% average CPU reduction to runtime work overall, of which maps are one part.

The 30% versus 1.5% gap is the whole story. Microbenchmarks keep one operation hot in cache; real services spend their time in parsing, syscalls, RPC boundaries, scheduling and GC assists, so map wins dilute unless maps dominate the profile. Cloudflare's DNS cache work saw a smaller gap: 56% per entry in the benchmark, 42–43% in resident memory (big-pineapple-dns-cache-layout). The Golang team went further and questioned their own benchmarks in #70700, calling out branch-predictor-friendly key patterns, power-of-two map sizes and harness overhead as distortions — restructuring the benchmarks moved the observed deltas substantially. One fix that came out of that work improved small-map hit latency for unpredictable keys by about 1.7x (roughly 25ns to 14ns) and misses by about 1.3x.

python-dict-quadratic-time shows the memory side of the same effect in Python: a dict gets nine times slower per key between the smallest and the largest map, with no change in algorithm, because at a million entries lookups miss the cache.

On memory the reported range is 0–25% reduction, workload-dependent, which follows from the higher occupancy and the absence of overflow chains.

The regressions are documented too. #70835, still open, tracks cold-cache behavior: directory indirection and multiple allocations can make a miss more expensive than before, and a Prometheus benchmark in that thread showed higher runtime.mapaccess1_fast64 CPU on 1.24.2 than on 1.23 for its workload shape. The GOEXPERIMENT=mapsplitgroup experiment, which separates keys from values within a group, is one of the layouts being tried against it. Separately, #70617 covers clear(m) costing time proportional to allocated table size on maps that were once large and are now sparse.

What it means in practice

Upgrading is the entire action item; there is no code to change. The honest reading of the numbers is that lookup- or insert-heavy services with medium-to-large maps get a free speedup, and profiles dominated by cold misses, very sparse huge maps, or tight clear/reuse loops need measuring rather than assuming.

Two behaviors survived the rewrite unchanged and still bite. Maps never shrink their backing storage after deletions, so clear(m) on a map that once burst large keeps that memory and pays a cost proportional to the allocated groups:

m := make(map[string]int)
for {
    populate(m)
    process(m)
    clear(m)   // cheap when m is consistently sized; not when m grew once and shrank
}

And delete-dominated hot paths exercise the tombstone path in every probe group, so they benefit less than pure lookup or insert workloads. Neither needs application involvement to stay correct — they just cap the upside.

The symbols worth watching in a CPU profile are runtime.mapaccess1, runtime.mapassign and runtime.mapiterinit; the direct way to quantify the change for your own code is a go tool pprof diff between a 1.23 and a 1.24+ build. That measure-don't-extrapolate discipline is the same one go-bounds-checks-unsafe applies at a much smaller scale, and the same reason compiler-codegen-luck is worth reading before trusting any single microbenchmark delta. golang-green-tea-gc shows the trap in its sharpest form: the new collector cuts wall clock by roughly a third while the L3 cache-miss rate doubles or worse, because the reads that disappeared were the ones L3 was already serving.