How Go’s New Swiss Table Map Boosts Performance: A Deep Dive

Hash tables are a core data structure in computer science, providing the foundation for map types in many languages, including Go. The concept was first introduced by Hans Peter Luhn in a 1953 IBM memo, which described placing items into "buckets" and handling collisions with linked lists—today known as separate chaining hash tables[1]. In 1954, Gene M. Amdahl, Elaine M. McGraw, and Arthur L. Samuel used an "open addressing" scheme for IBM 701 programs, later formalized by W. Wesley Peterson in 1957 as linear probing open addressing[2][3].

Open Addressing Hash Table

In an open addressing hash table all entries reside in a single backing array. Each position, called a slot , is selected by a hash function hash(key). When a slot is occupied, a probe sequence is followed to find the next free slot. The article demonstrates this with a 16‑slot example: inserting key 98 maps to slot 7 (empty) and is placed directly, while inserting key 25 maps to slot 3 (already holds key 56), triggering linear probing through slots 4, 5 and finally slot 6 where the key is stored.

Example

The backing array and slot contents are illustrated with an image (omitted here). The example shows how hash(key) % 16 determines the initial slot and how linear probing resolves collisions. It also discusses load factor, typical maximum values of 70‑90 %, and the growth policy of doubling the array size when the load factor is exceeded.

Swiss Table

Swiss Table is a variant of open addressing introduced by Google in 2017 and open‑sourced in the Abseil C++ library[5]. It groups the backing array into logical groups of 8 slots (larger groups are possible). Each group has a 64‑bit control word where each byte indicates whether the corresponding slot is empty, deleted, or occupied; for occupied slots the byte stores the low 7 bits of the slot’s hash ( h2).

Insertion follows these steps:

Compute hash(key) and split it into high 57 bits ( h1) and low 7 bits ( h2).

Use h1 % 2 (for two groups) to select the first group.

Check the group for an existing entry with the same key (update case).

If none, search for an empty slot within the group.

If the group is full, move to the next group and repeat.

Step 3 is the "magic" of Swiss Table: the control word enables a SIMD‑accelerated byte‑wise comparison of all eight h2 values in parallel, quickly producing a list of candidate slots. Matching h2 bytes indicate potential matches that are then verified by full key comparison (the 7‑bit hash collision probability is 1/128). This parallel probe reduces the average number of comparisons and allows a higher maximum load factor with lower memory usage.

Go's Challenges

Go’s built‑in map has two unusual properties that complicate adopting Swiss Table directly. First, incremental growth limits the latency of any single insertion: when the map reaches its maximum load factor, only the table containing the new entry is resized, copying at most 1 024 entries. Swiss Table assumes a one‑time growth of the whole table, making this incompatible.

Second, Go permits modifications during iteration (explicitly allowed by the language spec[10]), requiring semantics such as: deleted entries are omitted, updated entries yield the new value, and newly inserted entries may or may not appear. Traditional iteration that walks the backing array in memory order would break these semantics because a growth operation can reshuffle the layout.

To reconcile this, Go splits a map into multiple independent Swiss Tables (an instance of extendible hashing[9]). Each sub‑table stores up to 1 024 entries, and the high bits of the hash select which sub‑table to use. During iteration, the iterator holds a reference to the current sub‑table; if that sub‑table grows, the iterator continues using the old version for ordering, while consulting the new version to determine whether a previously seen key still exists and to fetch its latest value. This approach respects Go’s iteration semantics while keeping growth latency bounded.

Future Work

Micro‑benchmarks show that Go 1.24 map operations are about 60 % faster than Go 1.23, with an overall geometric mean CPU‑time improvement of roughly 1.5 % across full‑application workloads. Ongoing work includes improving locality for map operations that miss the CPU cache[12] and extending SIMD‑based control‑word comparisons to larger groups (e.g., 16 slots) on architectures that support wider SIMD instructions, which could further reduce probe lengths.

Acknowledgments

The Swiss Table implementation in Go builds on contributions from many developers, notably YunHao Zhang (@zhangyunhao116), PJ Malloy (@thepudds), and Peter Mattis (@petermattis) who created the github.com/cockroachdb/swiss library[16]. The Go 1.24 map implementation heavily leverages this work.

References

[1] Separate chaining hash tables: https://en.wikipedia.org/wiki/Hash_table#Separate_chaining

[2] "Addressing for Random‑Access Storage": https://ieeexplore.ieee.org/document/5392733

[3] Open addressing with linear probing: https://en.wikipedia.org/wiki/Hash_table#Open_addressing

[4] Pattern‑defeating quicksort: https://arxiv.org/pdf/2106.05123.pdf

[5] Abseil C++ library: https://abseil.io/blog/20180927-swisstables

[6] Swiss Table design: https://abseil.io/about/design/swisstables

[7] SIMD: https://en.wikipedia.org/wiki/Single_instruction,_multiple_data

[8] Implementation details: https://cs.opensource.google/go/go/+/master:src/internal/runtime/maps/group.go;drc=a08984bc8f2acacebeeadf7445ecfb67b7e7d7b1;l=155?ss=go

[9] Extendible hashing: https://en.wikipedia.org/wiki/Extendible_hashing

[10] Go spec on iteration order: https://go.dev/ref/spec#For_statements

[11] Micro‑benchmark discussion: https://go.dev/issue/54766#issuecomment-2542444404

[12] Improving map locality: https://go.dev/issue/70835

[16] CockroachDB Swiss library: https://pkg.go.dev/github.com/cockroachdb/swiss