runtime: map with 8 elements unnecessarily grows on existing key update

[just-hesen]

Go version

go version go1.26.2 windows/amd64

Output of go env in your module/workspace:

set AR=ar
set CC=gcc
set CGO_CFLAGS=-O2 -g
set CGO_CPPFLAGS=
set CGO_CXXFLAGS=-O2 -g
set CGO_ENABLED=1
set CGO_FFLAGS=-O2 -g
set CGO_LDFLAGS=-O2 -g
set CXX=g++
set GCCGO=gccgo
set GO111MODULE=on
set GOAMD64=v1
set GOARCH=amd64
set GOAUTH=netrc
set GOBIN=
set GOCACHE=C:\Users\Hesen\AppData\Local\go-build
set GOCACHEPROG=
set GODEBUG=
set GOENV=C:\Users\Hesen\AppData\Roaming\go\env
set GOEXE=.exe
set GOEXPERIMENT=
set GOFIPS140=off
set GOFLAGS=
set GOGCCFLAGS=-m64 -mthreads -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=C:\Users\Hesen\AppData\Local\Temp\go-build684478256=/tmp/go-build -gno-record-gcc-switches
set GOHOSTARCH=amd64
set GOHOSTOS=windows
set GOINSECURE=
set GOMOD=F:\0myFile\OneDrive\0sync\mygo\go.mod
set GOMODCACHE=C:\Users\Hesen\go\pkg\mod
set GONOPROXY=
set GONOSUMDB=
set GOOS=windows
set GOPATH=C:\Users\Hesen\go
set GOPRIVATE=
set GOPROXY=https://goproxy.cn,direct
set GOROOT=D:\Program Files\Go
set GOSUMDB=sum.golang.org
set GOTELEMETRY=local
set GOTELEMETRYDIR=C:\Users\Hesen\AppData\Roaming\go\telemetry
set GOTMPDIR=
set GOTOOLCHAIN=auto
set GOTOOLDIR=D:\Program Files\Go\pkg\tool\windows_amd64
set GOVCS=
set GOVERSION=go1.26.2
set GOWORK=
set PKG_CONFIG=pkg-config

What did you do?

Summary

When a small map (with m.dirLen == 0) contains exactly 8 elements (m.used == abi.MapGroupSlots), any subsequent assignment triggers an immediate growth to a table via m.growToTable(typ), regardless of whether the key already exists in the map. This leads to unnecessary O(N) evacuation and memory allocation for an O(1) in-place update.

Description

In Go 1.26's Swiss Table implementation (specifically in internal/runtime/maps/runtime.go), the growth check in runtime_mapassign (and its variants in runtime_fast*.go) is performed before checking if the key is already present:

if m.dirLen == 0 {
    if m.used < abi.MapGroupSlots {
        // ... logical path for small map insertion/update
        return elem
    }

    // Can't fit another entry, grow to full size map.
    m.growToTable(typ)
}

This behavior causes an unnecessary growth when updating an existing key in a full small map, which should instead be an in-place update.

Root Cause

The growth check is performed before checking if the key already exists, which means even for updates to existing keys, the map will grow if it's at capacity. This is inefficient because updates don't require additional space.

I found a TODO (@prattmic) in internal/runtime/maps/map.go which indicates that this limitation was previously recognized but not yet addressed:

// TODO(prattmic): If this is an update to an existing key then
// we actually don't need to grow.
m.growToTable(typ)

Benchmarks

I conducted benchmarks on go version go1.26.2 windows/amd64 to measure the performance impact of this issue.

Test Scenarios

1. UpdateExisting: Updating an existing key in a full small map (currently triggers growth)
2. InsertWithGrow: Inserting a 9th key (rightfully triggers growth)
3. InsertWithoutGrow: Deleting a key then inserting it (avoids growth)

Benchmark Results

I modified the local Go map implementation to fix this issue and then conducted performance tests for comparison.

Running on windows/amd64, AMD Ryzen 7 9700X:

Test Case	Before (sec/op)	After (sec/op)	Delta
UpdateExisting	496.80n ± 13%	75.73n ± 1%	-84.76%
InsertWithGrow	496.7n ± 1%	515.1n ± 1%	+3.70%
InsertWithoutGrow	71.79n ± 1%	71.92n ± 1%	~

Test Case	Before (B/op)	After (B/op)	Delta
UpdateExisting	328.0	0.0	-100.00%
InsertWithGrow	328.0	328.0	~
InsertWithoutGrow	0.0	0.0	~

Full Benchstat Output

goos: windows
goarch: amd64
pkg: mygo/test
cpu: AMD Ryzen 7 9700X 8-Core Processor
                                    │   .\old.txt   │              .\new.txt              │
                                    │    sec/op     │   sec/op     vs base                │
SmallMapUpdate/UpdateExisting-16      496.80n ± 13%   75.73n ± 1%  -84.76% (p=0.000 n=10)
SmallMapUpdate/InsertWithGrow-16       496.7n ±  1%   515.1n ± 1%   +3.70% (p=0.000 n=10)
SmallMapUpdate/InsertWithoutGrow-16    71.79n ±  1%   71.92n ± 1%        ~ (p=0.183 n=10)
geomean                                260.7n         141.0n       -45.90%

                                    │  .\old.txt   │                .\new.txt                │
                                    │     B/op     │    B/op     vs base                     │
SmallMapUpdate/UpdateExisting-16      328.0 ± 0%       0.0 ± 0%  -100.00% (p=0.000 n=10)
SmallMapUpdate/InsertWithGrow-16      328.0 ± 0%     328.0 ± 0%         ~ (p=1.000 n=10) ¹
SmallMapUpdate/InsertWithoutGrow-16   0.000 ± 0%     0.000 ± 0%         ~ (p=1.000 n=10) ¹
geomean                                          ²               ?                       ² ³
¹ all samples are equal
² summaries must be >0 to compute geomean
³ ratios must be >0 to compute geomean

                                    │  .\old.txt   │                .\new.txt                │
                                    │  allocs/op   │ allocs/op   vs base                     │
SmallMapUpdate/UpdateExisting-16      3.000 ± 0%     0.000 ± 0%  -100.00% (p=0.000 n=10)
SmallMapUpdate/InsertWithGrow-16      3.000 ± 0%     3.000 ± 0%         ~ (p=1.000 n=10) ¹
SmallMapUpdate/InsertWithoutGrow-16   0.000 ± 0%     0.000 ± 0%         ~ (p=1.000 n=10) ¹
geomean                                          ²               ?                       ² ³
¹ all samples are equal
² summaries must be >0 to compute geomean
³ ratios must be >0 to compute geomean

The data shows that after the fix, updating an existing element in a full small map no longer triggers allocations and is significantly faster, matching the performance of a standard in-place update.

Proposed Fix

I have implemented a fix that modifies the m.dirLen == 0 path to first probe the existing slots for a key match before calling m.growToTable. This ensures that:

• Updates remain in-place without growth.
• Insertions still trigger growth once the group is truly full.

The fix has been applied to the following files:

• internal/runtime/maps/runtime.go
• internal/runtime/maps/map.go
• internal/runtime/maps/runtime_fast32.go
• internal/runtime/maps/runtime_fast64.go
• internal/runtime/maps/runtime_faststr.go
• internal/runtime/maps/map_test.go (added a test function)

CL Ready

I have the CL ready and would like to submit it for review. The fix is minimal and focused, only changing the necessary code to address the issue while maintaining compatibility with existing code.

What did you see happen?

As described above, a full small map (with 8 elements) triggers unexpected growth behavior when performing an update operation.

What did you expect to see?

As described above, a full small map should not trigger growth when updating an existing element; growth should only occur when writing a new element.

[gabyhelp]

Related Issues

• internal/runtime/maps: hash copy of key instead of key itself makes map run slowly #76083
• runtime: performance regression for small Swiss Table map access for non-specialized keys #70849 (closed)
• runtime: map's loadFactor is actually 6, not 6.5 #63438 (closed)
• runtime: map clear in go 1.25 performance pitfalls #75097 (closed)

Related Code Changes

• internal/runtime/maps: speed up small map lookups ~1.7x for unpredictable keys
• runtime: evacuate maps more aggressively
• runtime: evacuate old map buckets more consistently
• runtime: add toy specialized map implementation
• expvar: improve Map.addKey for large number of keys
• cmd/compile, runtime: introduce GetOrPut map operations

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

[dmitshur]

Thanks for filing an issue for this. If you have a fix in mind, would you like to send a CL? https://go.dev/doc/contribute.

CC @golang/runtime.

[gopherbot]

Change https://go.dev/cl/770303 mentions this issue: runtime/maps: only grow small full maps when inserting new keys

[just-hesen]

I've submitted another version. In this version, I optimized the performance of inserting a new key into a full small map by using the uncheckedPutSlotForAssign* functions, and re-ran the performance benchmarks.

The latest results are as follows:

goos: windows
goarch: amd64
pkg: mygo/test
cpu: AMD Ryzen 7 9700X 8-Core Processor
                                    │  .\old5.txt  │             .\new5.txt              │
                                    │    sec/op    │   sec/op     vs base                │
SmallMapUpdate/UpdateExisting-16      481.45n ± 1%   68.45n ± 1%  -85.78% (p=0.000 n=10)
SmallMapUpdate/InsertWithGrow-16       501.7n ± 4%   470.6n ± 3%   -6.20% (p=0.002 n=10)
SmallMapUpdate/InsertWithoutGrow-16    67.72n ± 2%   67.13n ± 1%        ~ (p=0.469 n=10)
geomean                                253.8n        129.3n       -49.06%

                                    │  .\old5.txt  │               .\new5.txt                │
                                    │     B/op     │    B/op     vs base                     │
SmallMapUpdate/UpdateExisting-16      328.0 ± 0%       0.0 ± 0%  -100.00% (p=0.000 n=10)
SmallMapUpdate/InsertWithGrow-16      328.0 ± 0%     328.0 ± 0%         ~ (p=1.000 n=10) ¹
SmallMapUpdate/InsertWithoutGrow-16   0.000 ± 0%     0.000 ± 0%         ~ (p=1.000 n=10) ¹
geomean                                          ²               ?                       ² ³
¹ all samples are equal
² summaries must be >0 to compute geomean
³ ratios must be >0 to compute geomean

                                    │  .\old5.txt  │               .\new5.txt                │
                                    │  allocs/op   │ allocs/op   vs base                     │
SmallMapUpdate/UpdateExisting-16      3.000 ± 0%     0.000 ± 0%  -100.00% (p=0.000 n=10)
SmallMapUpdate/InsertWithGrow-16      3.000 ± 0%     3.000 ± 0%         ~ (p=1.000 n=10) ¹
SmallMapUpdate/InsertWithoutGrow-16   0.000 ± 0%     0.000 ± 0%         ~ (p=1.000 n=10) ¹
geomean                                          ²               ?                       ² ³
¹ all samples are equal
² summaries must be >0 to compute geomean
³ ratios must be >0 to compute geomean

The data shows that, compared to the previous version, inserting a new key into a full small map now also yields positive gains.

The benchmark code is as follows:

func BenchmarkSmallMapUpdate(b *testing.B) {
	b.Run("UpdateExisting", func(b *testing.B) {
		for n := 0; n < b.N; n++ {
			b.StopTimer()
			m := make(map[int]int, keySize)
			for i := 1; i <= keySize; i++ {
				m[i] = i
			}
			b.StartTimer()

			// Update an existing element
			m[keySize] = 999

			globalMap = m
		}
	})

	b.Run("InsertWithGrow", func(b *testing.B) {
		for n := 0; n < b.N; n++ {
			b.StopTimer()
			m := make(map[int]int, keySize)
			for i := 1; i <= keySize; i++ {
				m[i] = i
			}
			b.StartTimer()

			// insert a new element, trigger growth
			m[keySize+1] = 999

			globalMap = m
		}
	})

	b.Run("InsertWithoutGrow", func(b *testing.B) {
		for n := 0; n < b.N; n++ {
			b.StopTimer()
			m := make(map[int]int, keySize)
			for i := 1; i <= keySize-1; i++ {
				m[i] = i
			}
			b.StartTimer()

			// insert a new element, without trigger growth
			m[keySize] = 999

			globalMap = m
		}
	})
}