runtime: add indirect extendible hash map (ixmap) as alternative map implementation

[vnmakarov]

Proposal Details

Author: Vladimir Makarov

Last updated: Jul 16, 2026

Proposal Details

This proposal adds an alternative Go builtin map implementation based on indirect extendible hash tables, activated via GOEXPERIMENT=ixmap. It improves map performance across practically all key and value types, with the most significant gains for larger key/value pairs.

Since this proposal concerns performance improvement, it makes no sense to submit it without an implementation that allows the performance to be measured.

The implementation is complete: runtime, compiler, reflect, GDB support, tests, fuzz tests, and benchmarks. It is available at https://github.com/vnmakarov/go (branch ixmap). The full set of changes can be found at vnmakarov/go@8c14de9...ixmap

Background

The current map implementation is based on the Swiss table design. Swiss table is a direct open-addressing hash table: it stores keys, values, and probing metadata in one array, divided into groups of 8 key/value pairs plus 8 control bytes. SIMD (or SWAR) is used to match control bytes within a group in parallel.

This design has a fundamental cache-efficiency problem: probing in a direct-addressing table fetches key/value data that may never match. The bigger the key and/or value, the worse the situation. Misses are especially expensive since every probed group pulls in key/value data that will never be used.

To compensate for the memory wasted on keys and values in unused slots, the Swiss table uses a high load factor (7/8 = 87.5%). Pessimistic estimates of average probes at this load factor for open-addressing tables with linear probing (used for the first two groups or first 16 slots) are approximately 32 probes for nonexistent keys and 4 for existing keys, respectively (see Knuth's "The Art of Computer Programming", volume 3). SIMD instructions help but do not fully solve the problem.

Design

IXMap addresses this by using indirect indexing with smaller load factor (2/3 = 66%). It separates control metadata (7-bit hash parts and small element indices) from element storage (key/value pairs). The metadata is placed in an array of groups. Each group contains only 8 h7 (7-bit hash) bytes and 8 uint16 indices — 24 bytes total, fixed regardless of key/value size. The probe loop touches only compact metadata. Actual keys/values are stored in a separate flat array and accessed only when an h7 match confirms a candidate.

Data Structures

IXMap (top-level map):

type IXMap struct {
    used     uint64          // element count (first field, known by compiler for len())
    seed     uintptr         // per-map hash seed
    htabs    []*ixHTab       // slice of all non-deleted hash tables
    dirPtr   unsafe.Pointer  // directory for extendible hashing
    maxDepth uint8           // current directory depth
    writing  uint8           // concurrent write detection
    htabMask uint32          // mask for directory index from hash
    nextuid  uint64          // uid for the next new htab
}

When htabMask == 0, the map has a single htab and dirPtr points directly to it. Otherwise, dirPtr points to an array of htabMask+1 htab pointers, indexed by (hash >> 15) & htabMask.

ixHTab (hash table):

type ixHTab struct {
    ind          uint           // index in IXMap.htabs slice
    depth        uint8          // depth in extendible hashing directory
    delMask      uint8          // deleted bits for small maps (<=8 entries)
    groupIndMask uint16          // (num_groups - 1), for masking group index
    elsSize      uint16          // maximum element capacity
    elsBound     uint16          // next free element index (high-water mark)
    els          unsafe.Pointer  // element storage: array of (key, value) slots
    deleted      unsafe.Pointer  // deletion bitmap: 1 bit per element slot
    entries      unsafe.Pointer  // group array: (8 h7 bytes + 8 uint16 indices) per group
    uid          uint64          // unique id of this htab, 0 for deleted htab
}

Entry groups — each group is 24 bytes:

Bytes  0-7:   8 h7 control bytes (7-bit hash fingerprint per slot)
Bytes  8-23:  8 uint16 element indices (pointing into els array)

An h7 byte encodes slot state: 0xc0 = empty, 0x80 = deleted (tombstone), 0x00-0x7f = occupied (upper 7 bits of hash). This encoding enables SWAR-based parallel matching of all 8 slots in a single uint64 operation.

Key Operations

Lookup: Compute hash; use upper bits to select htab from directory. Extract h7 (upper 7 bits). Compute initial group index from lower hash bits. Load group's 8 h7 bytes as uint64 and use SWAR to match all 8 against target h7 in parallel. For each match, read the uint16 index, load the element from els, compare keys. If no match and an empty slot exists in the group, key is absent. Otherwise advance to next group (linear probing).

Insert: Same probing as lookup. If key found, update value. If not found and a tombstone was seen during probing, reuse that slot. Otherwise allocate next element at elsBound. If elsBound == elsSize, rebuild or split.

Delete: Probe to find key. Mark h7 as deletedH7. Set bit in deletion bitmap. Clear element value for GC.

Iteration: Walk htabs in order. Within each htab, scan the els array sequentially, skipping deleted elements via the deletion bitmap. A random start offset is chosen per htab to satisfy Go's randomized iteration order guarantee. Htabs created after the iterator was initialized (tracked by nextuid) are skipped. If the current htab was deleted due to splitting or rebuilding, the iterator looks up each element in the current map to check that it is still present.

Growth Strategy

Rebuild with compaction: When an htab fills (elsBound == elsSize), a new htab is created to replace the given one. If the active elements occupy > 2/3 of the capacity, the size of all arrays is doubled. The active elements from the given table are inserted into the new table, resulting in contiguous elements with no deleted gaps. This preserves iterator correctness while improving memory efficiency.

Split (extendible hashing): When an htab reaches 2^15 entries, it splits into two new htabs. Elements are redistributed based on one additional bit of the hash prefix. The directory doubles if needed. Deleted htabs are marked with zero uid and are no longer present in the map's htabs slice; iterator consistency is maintained through the uid mechanism. Splits can cascade if a new htab is immediately above the load factor.

Small Map Optimization

Maps with hint <= 10 elements (16 entries) are stack-allocated when possible. The compiler allocates the IXMap, ixHTab, elements array, and entries array on the stack, avoiding heap allocation for short-lived small maps.

SWAR Matching

IXMap uses SWAR (SIMD Within A Register) for group matching:

func matchH7(group uint64, h7Val uintptr) uint64 {
    cmp := group ^ (swarLSB * uint64(h7Val))
    return (cmp - swarLSB) & ^cmp & swarMSB
}

This operates on 8 h7 bytes packed in a uint64 using portable bit manipulation. An AMD64 SIMD implementation was tested but showed no visible performance improvement, as the critical path in CPU cycles is practically the same. Still, it is easy to switch to SIMD by renaming match7 and a few other functions to names used by the current map implementation (ctrlGroupMatchH2, etc.).

Performance

Benchmarks were run using the new runtime/map_bench_test.go (the existing runtime/map_benchmark_test.go is currently broken). The suite covers insert, lookup, and delete for string, integer, pointer-value, large-value (128-byte struct), interface-value, large composite-key (string pairs), and very long string key types. Each operation is tested at four map sizes: Tiny (10), Small (100), Medium (10K), and Large (1M elements). Additional benchmarks cover iteration, random access, key miss, mixed operations (70% insert / 20% lookup / 10% delete), memory allocation patterns, and growth with and without preallocation.

Benchmarks were run using the run_map_comparison.sh script on five platforms: AMD Ryzen 9 9900X (linux/amd64), Intel Core Ultra 7 270K (linux/amd64 and linux/386), Apple M4 (linux/arm64), IBM POWER10 (linux/ppc64le), and IBM z16 (linux/s390x). Each benchmark was run 6 times.

Benchmark visualization graphs are in Appendix A; full benchstat data is in Appendix B.

Summary

IXMap is consistently faster across the majority of operations and map sizes, with improvements growing for larger maps. Benchstat geomean over all benchmarks and sizes: 28% faster (AMD Ryzen 9 9900X). Cross-platform results are consistent: 37% (Intel Core Ultra 7 270K), 38% (Apple M4), 23% (IBM POWER10), 27% (IBM z16 s390x), 33% (Intel Core Ultra 7 270K, linux/386).

• Insert: up to 76% faster, up to 39% less memory, up to 94% fewer allocations
• Lookup: up to 74% faster
• Delete: up to 80% faster
• Iteration: up to 61% faster (contiguous element storage improves cache locality)
• Memory: up to 39% less total allocation, with compaction reducing memory fragmentation from deletions
• Allocations: up to 94% fewer allocs (5 vs 33 at 10K elements; 258 vs 4097 at 1M elements)

The improvements are larger for bigger maps and bigger key/value types because IXMap's fixed 24-byte group size means probing cost does not scale with slot size.

Tradeoffs

IXMap advantages over Swiss table:

• Lower load factor (66.7% vs 87.5%) means less probing on average for a search.
• Lookup probing touches only 24-byte groups regardless of key/value size, giving better cache behavior especially for large keys/values or miss-heavy workloads.
• Larger per-htab capacity (2/3 * 32K vs 1024) means fewer directory entries and less splitting overhead for large maps.
• Contiguous element storage improves iteration cache locality.
• Compaction during rebuild eliminates memory fragmentation from deleted elements without always requiring capacity increases.

Swiss table advantages over IXMap:

• Higher load factor (87.5% vs 66.7%) means less metadata overhead per element in the entries/control structure.
• Inline key/value storage avoids an extra indirection on each confirmed match.
• Quadratic probing (only between groups) resists clustering more than linear probing.
• Smaller maximum table size (1024) means individual grow operations are faster.

Memory usage crossover:

The per-element metadata overhead in a full Swiss table is 1 + 1/7 * (S+1) bytes where S is the key/value pair size; for IXMap it is 4.5 bytes, a constant independent of S. IXMap uses less metadata memory when the key/value pair size exceeds ~23-24 bytes. For maps with string keys or values (16 bytes each on a 64-bit target), IXMap uses the same or less total memory.

Implementation

The implementation is behind GOEXPERIMENT=ixmap and touches the following packages:

• internal/runtime/maps: Core implementation
  • map_ixmap.go — data structures, get/put/delete/clear/clone/rebuild/split
  • iter_ixmap.go — iterator
  • runtime_ixmap.go — runtime API (mapaccess1/2, mapassign) with race/msan/asan
  • runtime_fast{32,64,str}_ixmap.go — fast paths for common key types
• internal/abi: map_ixmap.go, map_select_ixmap.go — IXMapType definition, type selection
• runtime: map_ixmap.go, map_fast{32,64,str}_ixmap.go, linkname_shim_ixmap.go — runtime wrappers, legacy iterator compat
• reflect: map_ixmap.go — full reflection API
• cmd/compile/internal/reflectdata: map_ixmap.go — compiler type layout generation
• cmd/compile/internal/walk: builtin.go — small map stack allocation (walkMakeIXMap)
• cmd/compile/internal/ssagen: ssa.go — SSA generation hooks
• internal/goexperiment: flags.go, exp_ixmap_{on,off}.go — experiment flag

Testing

• Unit tests: internal/runtime/maps/map_ixmap_test.go
• Fuzz tests: internal/runtime/maps/fuzz_ixmap_test.go
• Benchmark suite: runtime/map_bench_test.go (1500+ lines, covers different key/value types and map sizes)
• GDB pretty-printer support in runtime/runtime-gdb.py

IXMap has been successfully tested and Go is built with GOEXPERIMENT=ixmap on the following platforms: amd64/Linux, i386/Linux, arm64/Linux, arm64/Darwin, ppc64le/Linux, s390x/Linux.

Build and test

cd src
GOEXPERIMENT=ixmap ./make.bash
GOEXPERIMENT=ixmap ../bin/go test runtime/...

Benchmark comparison

# Build
cd src
GOEXPERIMENT=ixmap   ./make.bash

# Run benchmarks (Swiss table baseline)
GOEXPERIMENT=noixmap ../bin/go test -bench=. -benchmem -count=6 \
  runtime/map_bench_test.go > swiss.txt

# Run benchmarks (IXMap)
GOEXPERIMENT=ixmap ../bin/go test -bench=. -benchmem -count=6 \
  runtime/map_bench_test.go > ixmap.txt

# Compare
benchstat swiss.txt ixmap.txt

Prior art

IXMap is based on the indirect hash table library (ihtab), adapted for Go's runtime requirements: GC integration, concurrent access detection, reflection, and iterator semantics.

Appendix A: Benchmark Visualization

The benchstat tables in Appendix B contain a large amount of data. The following graphs visualize the performance improvements across all operations and map sizes for each platform (positive values indicate IXMap is faster). For each benchmark, the average of 6 runs was used.

AMD Ryzen 9 9900X (linux/amd64)

Intel Core Ultra 7 270K (linux/amd64)

Benchmarks were pinned to a performance core using taskset.

Intel Core Ultra 7 270K (linux/386)

Benchmarks were pinned to a performance core using taskset.

Apple M4 (linux/arm64)

IBM POWER10 (linux/ppc64le)

IBM z16 (linux/s390x)

Appendix B: Benchstat Results

As the issue field is constrainted by 64KB, there are no benchstat data here, but the data can be found in Appendix B of README.md at https://github.com/vnmakarov/go

[gabyhelp]

Related Issues

• runtime: use SwissTable #54766 (closed)
• runtime: enhance map cacheline efficiency #48687
• sync: replace Map implementation with HashTrieMap #70683 (closed)

Related Code Changes

• internal/runtime/maps: rewrite MemHash{32,64} using simd/archsimd intrinsics
• runtime: add toy specialized map implementation
• internal/runtime/maps: speed up small map lookups ~1.7x for unpredictable keys
• internal/runtime/maps/: devirtualize hashing for specialized maps
• runtime: exit early when scanning map buckets
• runtime: vectorized map bucket lookup
• expvar: improve Map.addKey for large number of keys

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[randall77]

My worry about this is that for large maps, we're guaranteeing two cache misses at minimum (on a map lookup hit). One for the group array lookup and one for the key/value. The current arrangement means we can often get both with a single cache miss.

[vnmakarov]

My worry about this is that for large maps, we're guaranteeing two cache misses at minimum (on a map lookup hit). One for the group array lookup and one for the key/value. The current arrangement means we can often get both with a single cache miss.

Benchmarks show that for large maps (e.g. 1M elements), ixmap works even better than for small maps.

The implementation is based on https://github.com/vnmakarov/ihtab. There is comparison with swiss table implementation (absl) which is practically the same as the current GO maps (excluding extendible table code parts). On perf data for 1M and 20M keys ihtab has 30-40% less L1 data cache misses and 10% less LLC misses.

Swiss tables because of very high load factor require significantly more probing although one probe has less memory accesses.

The rationale and design of ihtab is described in https://vnmakarov.github.io/data%20structures/c/c++/open-source/2026/06/23/two-indexed-hash-tables.html and this can be useful for better understanding ixmap.

[prattmic]

I haven't looked closely at this yet, but it is quite intriguing, thanks for opening this.

cc @golang/runtime

[prattmic]

Changing the map implementation doesn't require API changes, so I'm dropping from the proposal process.