[go] maps: add Grow to reserve capacity for an existing map
8 views
Skip to first unread message
Liz Fong-Jones (Gerrit)
Aug 22, 2026, 5:41:07 AMAug 22
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Liz Fong-Jones has uploaded the change for review![]( "Open in Gerrit")
Commit message
maps: add Grow to reserve capacity for an existing map
Add maps.Grow(m, n), which resizes m in place to hold n additional
entries without growing again in the average case, as if m had been
created with make(M, len(m)+n). This lets callers presize a
destination map before a bulk Copy, avoiding the doubling-growth cost
discussed in #56182 (e.g. maps.Copy(dst, src) after maps.Grow(dst,
len(src))).
The runtime piece (Map.Grow, in internal/runtime/maps) reuses the
existing directory/table sizing math from NewMap (factored out as
mapCapacityFor) and the existing uncheckedPutSlot rehoming used by
table.grow/split, generalized to walk the whole map's directory
rather than a single table. It never shrinks a map, and is a no-op
if the map's current capacity already covers the requested hint.
This is a strawman implementation for discussion, posted to gather
feedback on the API and approach rather than as a final proposal.
Updates #56182
Change-Id: If97bec83aa42fafbdb9ae92a833a6928b8e26120
Change diff
diff --git a/src/internal/runtime/maps/map.go b/src/internal/runtime/maps/map.go
index 0ee5e09..0c35893 100644
--- a/src/internal/runtime/maps/map.go
+++ b/src/internal/runtime/maps/map.go
@@ -307,30 +307,11 @@
// Full size map.
- // Set initial capacity to hold hint entries without growing in the
- // average case.
- targetCapacity := (hint * abi.MapGroupSlots) / maxAvgGroupLoad
- if targetCapacity < hint { // overflow
+ dirSize, targetCapacity, ok := mapCapacityFor(mt, hint, maxAlloc)
+ if !ok {
return m // return an empty map.
}
- dirSize := (uint64(targetCapacity) + maxTableCapacity - 1) / maxTableCapacity
- dirSize, overflow := alignUpPow2(dirSize)
- if overflow || dirSize > uint64(math.MaxUintptr) {
- return m // return an empty map.
- }
-
- // Reject hints that are obviously too large.
- groups, overflow := math.MulUintptr(uintptr(dirSize), maxTableCapacity)
- if overflow {
- return m // return an empty map.
- } else {
- mem, overflow := math.MulUintptr(groups, mt.GroupSize)
- if overflow || mem > maxAlloc {
- return m // return an empty map.
- }
- }
-
m.globalDepth = uint8(sys.TrailingZeros64(dirSize))
m.globalShift = depthToShift(m.globalDepth)
@@ -347,6 +328,38 @@
return m
}
+// mapCapacityFor computes the directory size and total target slot
+// capacity needed to hold hint entries at the standard load factor.
+// Shared sizing logic for NewMap and Map.Grow; callers must have already
+// handled hint <= abi.MapGroupSlots. ok is false if hint is too large.
+func mapCapacityFor(mt *abi.MapType, hint uintptr, maxAlloc uintptr) (dirSize uint64, targetCapacity uintptr, ok bool) {
+ // Set initial capacity to hold hint entries without growing in the
+ // average case.
+ targetCapacity = (hint * abi.MapGroupSlots) / maxAvgGroupLoad
+ if targetCapacity < hint { // overflow
+ return 0, 0, false
+ }
+
+ dirSize = (uint64(targetCapacity) + maxTableCapacity - 1) / maxTableCapacity
+ var overflow bool
+ dirSize, overflow = alignUpPow2(dirSize)
+ if overflow || dirSize > uint64(math.MaxUintptr) {
+ return 0, 0, false
+ }
+
+ // Reject hints that are obviously too large.
+ groups, overflow := math.MulUintptr(uintptr(dirSize), maxTableCapacity)
+ if overflow {
+ return 0, 0, false
+ }
+ mem, overflow := math.MulUintptr(groups, mt.GroupSize)
+ if overflow || mem > maxAlloc {
+ return 0, 0, false
+ }
+
+ return dirSize, targetCapacity, true
+}
+
func NewEmptyMap() *Map {
m := new(Map)
m.seed = uintptr(rand())
@@ -354,6 +367,133 @@
return m
}
+// totalCapacity returns m's total slot count, summed across distinct
+// tables in the directory. A small map reports abi.MapGroupSlots.
+func (m *Map) totalCapacity() uint64 {
+ if m.dirLen == 0 {
+ return abi.MapGroupSlots
+ }
+
+ var total uint64
+ var lastTab *table
+ for i := range m.dirLen {
+ t := m.directoryAt(uintptr(i))
+ if t == lastTab {
+ continue
+ }
+ lastTab = t
+ total += uint64(t.capacity)
+ }
+ return total
+}
+
+// Grow ensures m can hold at least n additional entries without growing
+// again, as if allocated via NewMap(typ, m.Used()+n, ...). Never shrinks
+// m. maxAlloc should be runtime.maxAlloc.
+func (m *Map) Grow(typ *abi.MapType, n uintptr, maxAlloc uintptr) {
+ if m.writing != 0 {
+ fatal("concurrent map writes")
+ }
+
+ if n == 0 {
+ return
+ }
+
+ used := uintptr(m.Used())
+ hint := used + n
+ if hint < used { // overflow
+ hint = math.MaxUintptr
+ }
+
+ if hint <= abi.MapGroupSlots {
+ return // small map already has room; see NewMap.
+ }
+
+ dirSize, targetCapacity, ok := mapCapacityFor(typ, hint, maxAlloc)
+ if !ok {
+ return // hint too large to size for; leave m alone.
+ }
+
+ if m.totalCapacity() >= uint64(targetCapacity) {
+ return // already enough room.
+ }
+
+ m.writing ^= 1 // toggle, see comment on writing
+
+ m.growTo(typ, dirSize, targetCapacity)
+
+ if m.writing == 0 {
+ fatal("concurrent map writes")
+ }
+ m.writing ^= 1
+}
+
+// growTo replaces m's storage with a fresh directory of dirSize tables
+// totaling targetCapacity slots, and moves every entry into it. Callers
+// must size dirSize/targetCapacity via mapCapacityFor.
+func (m *Map) growTo(typ *abi.MapType, dirSize uint64, targetCapacity uintptr) {
+ newGlobalDepth := uint8(sys.TrailingZeros64(dirSize))
+ newGlobalShift := depthToShift(newGlobalDepth)
+
+ newDir := make([]*table, dirSize)
+ for i := range newDir {
+ newDir[i] = newTable(typ, uint64(targetCapacity)/dirSize, i, newGlobalDepth)
+ }
+
+ putGroup := func(g groupReference) {
+ for j := uintptr(0); j < abi.MapGroupSlots; j++ {
+ if (g.ctrls().get(j) & ctrlEmpty) == ctrlEmpty {
+ // Empty or deleted.
+ continue
+ }
+
+ key := g.key(typ, j)
+ if typ.IndirectKey() {
+ key = *((*unsafe.Pointer)(key))
+ }
+
+ elem := g.elem(typ, j)
+ if typ.IndirectElem() {
+ elem = *((*unsafe.Pointer)(elem))
+ }
+
+ hash := typ.Hasher(key, m.seed)
+ idx := uintptr(0)
+ if dirSize > 1 {
+ idx = hash >> (newGlobalShift & 63)
+ }
+ newDir[idx].uncheckedPutSlot(typ, hash, key, elem)
+ }
+ }
+
+ switch {
+ case m.dirPtr == nil:
+ // Empty small map; nothing to move.
+ case m.dirLen == 0:
+ // Small map: a single group.
+ putGroup(groupReference{data: m.dirPtr})
+ default:
+ var lastTab *table
+ for i := range m.dirLen {
+ t := m.directoryAt(uintptr(i))
+ if t == lastTab {
+ continue
+ }
+ lastTab = t
+
+ for gi := uint64(0); gi <= t.groups.lengthMask; gi++ {
+ putGroup(t.groups.group(typ, gi))
+ }
+ }
+ }
+
+ m.dirPtr = unsafe.Pointer(&newDir[0])
+ m.dirLen = len(newDir)
+ m.globalDepth = newGlobalDepth
+ m.globalShift = newGlobalShift
+ m.tombstonePossible = false // tables were rebuilt fresh, no tombstones
+}
+
func (m *Map) directoryIndex(hash uintptr) uintptr {
if m.dirLen == 1 {
return 0
diff --git a/src/internal/runtime/maps/map_test.go b/src/internal/runtime/maps/map_test.go
index 2e52e1c..68e8422 100644
--- a/src/internal/runtime/maps/map_test.go
+++ b/src/internal/runtime/maps/map_test.go
@@ -998,3 +998,104 @@
}
}
}
+
+func TestMapGrow(t *testing.T) {
+ const maxAllocTest = uintptr(1) << 30
+
+ t.Run("zero is a no-op", func(t *testing.T) {
+ m, typ := maps.NewTestMap[uint32, uint64](0)
+ m.Grow(typ, 0, maxAllocTest)
+ if m.Used() != 0 {
+ t.Fatalf("Used() got %d want 0", m.Used())
+ }
+ if m.TableCount() != 0 {
+ t.Fatalf("TableCount() got %d want 0", m.TableCount())
+ }
+ })
+
+ t.Run("small map stays small below GroupSlots", func(t *testing.T) {
+ m, typ := maps.NewTestMap[uint32, uint64](0)
+ m.Grow(typ, abi.MapGroupSlots, maxAllocTest)
+ if m.TableCount() != 0 {
+ t.Fatalf("expected map to remain small, got TableCount() = %d", m.TableCount())
+ }
+ })
+
+ t.Run("preserves entries in a small map", func(t *testing.T) {
+ m, typ := maps.NewTestMap[uint32, uint64](0)
+
+ const n = 5
+ for i := uint32(0); i < n; i++ {
+ key, elem := i, uint64(i)+1000
+ m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
+ }
+
+ m.Grow(typ, 5000, maxAllocTest)
+
+ if m.Used() != n {
+ t.Fatalf("Used() got %d want %d", m.Used(), n)
+ }
+ for i := uint32(0); i < n; i++ {
+ key := i
+ got, ok := m.Get(typ, unsafe.Pointer(&key))
+ if !ok {
+ t.Fatalf("Get(%d) got ok false want true", key)
+ }
+ want := uint64(i) + 1000
+ if gotElem := *(*uint64)(got); gotElem != want {
+ t.Fatalf("Get(%d) got elem %d want %d", key, gotElem, want)
+ }
+ }
+ })
+
+ t.Run("preserves entries across a directory with splits", func(t *testing.T) {
+ m, typ := maps.NewTestMap[uint32, uint64](0)
+
+ const n = 3000
+ for i := uint32(0); i < n; i++ {
+ key, elem := i, uint64(i)
+ m.Put(typ, unsafe.Pointer(&key), unsafe.Pointer(&elem))
+ }
+ if m.TableCount() <= 1 {
+ t.Fatalf("expected map to have split into multiple tables before Grow, got TableCount() = %d", m.TableCount())
+ }
+
+ m.Grow(typ, 5000, maxAllocTest)
+
+ if m.Used() != n {
+ t.Fatalf("Used() got %d want %d", m.Used(), n)
+ }
+ for i := uint32(0); i < n; i++ {
+ key := i
+ got, ok := m.Get(typ, unsafe.Pointer(&key))
+ if !ok {
+ t.Fatalf("Get(%d) got ok false want true", key)
+ }
+ if gotElem := *(*uint64)(got); gotElem != uint64(i) {
+ t.Fatalf("Get(%d) got elem %d want %d", key, gotElem, i)
+ }
+ }
+ })
+
+ t.Run("never shrinks and is idempotent", func(t *testing.T) {
+ m, typ := maps.NewTestMap[uint32, uint64](0)
+
+ m.Grow(typ, 2000, maxAllocTest)
+ grown := m.GroupCount()
+ if grown == 0 {
+ t.Fatal("expected Grow to allocate storage")
+ }
+
+ m.Grow(typ, 0, maxAllocTest)
+ if got := m.GroupCount(); got != grown {
+ t.Fatalf("Grow(0) changed GroupCount(): got %d want %d", got, grown)
+ }
+
+ // Requesting room for far fewer entries than are already
+ // available must not shrink or reallocate.
+ m.Grow(typ, 10, maxAllocTest)
+ if got := m.GroupCount(); got != grown {
+ t.Fatalf("Grow(10) with capacity already available changed GroupCount(): got %d want %d", got, grown)
+ }
+ })
+}
diff --git a/src/maps/maps.go b/src/maps/maps.go
index b712dd3..4c04119 100644
--- a/src/maps/maps.go
+++ b/src/maps/maps.go
@@ -65,6 +65,22 @@
}
}
+// grow is implemented in the runtime package.
+//
+//go:linkname grow maps.grow
+func grow(m any, n int)
+
+// Grow ensures m can hold at least n more entries without growing again,
+// as if created with make(M, len(m)+n). Never shrinks m.
+//
+// Grow panics if n is negative, or if m is nil.
+func Grow[M ~map[K]V, K comparable, V any](m M, n int) {
+ if n < 0 {
+ panic("maps: cannot grow by a negative count")
+ }
+ grow(m, n)
+}
+
// DeleteFunc deletes any key/value pairs from m for which del returns true.
func DeleteFunc[M ~map[K]V, K comparable, V any](m M, del func(K, V) bool) {
for k, v := range m {
diff --git a/src/maps/maps_test.go b/src/maps/maps_test.go
index c8ee3cd..8827507 100644
--- a/src/maps/maps_test.go
+++ b/src/maps/maps_test.go
@@ -240,3 +240,55 @@
}
}
}
+
+func TestGrow(t *testing.T) {
+ m := map[int]int{1: 2, 2: 4}
+ Grow(m, 1000)
+
+ if !Equal(m, map[int]int{1: 2, 2: 4}) {
+ t.Errorf("Grow changed the contents of m: got %v", m)
+ }
+
+ for i := 0; i < 1000; i++ {
+ m[i] = i
+ }
+ if len(m) != 1000 {
+ t.Errorf("len(m) after inserts got %d want 1000", len(m))
+ }
+ for i := 0; i < 1000; i++ {
+ if got := m[i]; got != i {
+ t.Errorf("m[%d] got %d want %d", i, got, i)
+ }
+ }
+}
+
+func TestGrowZero(t *testing.T) {
+ m := map[int]int{1: 2}
+ Grow(m, 0)
+ if !Equal(m, map[int]int{1: 2}) {
+ t.Errorf("Grow(m, 0) changed the contents of m: got %v", m)
+ }
+
+ // Growing a nil map by zero must not panic.
+ var nilMap map[int]int
+ Grow(nilMap, 0)
+}
+
+func TestGrowNegative(t *testing.T) {
+ defer func() {
+ if recover() == nil {
+ t.Error("Grow(m, -1) did not panic")
+ }
+ }()
+ Grow(map[int]int{}, -1)
+}
+
+func TestGrowNil(t *testing.T) {
+ defer func() {
+ if recover() == nil {
+ t.Error("Grow(nil, 1) did not panic")
+ }
+ }()
+ var m map[int]int
+ Grow(m, 1)
+}
diff --git a/src/runtime/map.go b/src/runtime/map.go
index bd91ec9..d87a967 100644
--- a/src/runtime/map.go
+++ b/src/runtime/map.go
@@ -317,3 +317,20 @@
e.data = (unsafe.Pointer)(map_)
return m
}
+
+// mapgrow for implementing maps.Grow. n must be non-negative; maps.Grow
+// rejects negative counts before calling here.
+//
+//go:linkname mapgrow maps.grow
+func mapgrow(m any, n int) {
+ if n == 0 {
+ return
+ }
+ e := efaceOf(&m)
+ typ := (*abi.MapType)(unsafe.Pointer(e._type))
+ map_ := (*maps.Map)(e.data)
+ if map_ == nil {
+ panic(maps_errNilAssign)
+ }
+ map_.Grow(typ, uintptr(n), maxAlloc)
+}
Change information
Files:
- M src/internal/runtime/maps/map.go
- M src/internal/runtime/maps/map_test.go
- M src/maps/maps.go
- M src/maps/maps_test.go
- M src/runtime/map.go
Change size: L
Delta: 5 files changed, 347 insertions(+), 21 deletions(-)
Related details
Attention set is empty
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Liz Fong-Jones (Gerrit)
Aug 22, 2026, 6:07:32 AMAug 22
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Ian Lance Taylor, Keith Randall and Michael Pratt
Liz Fong-Jones uploaded new patchset![]( "Open in Gerrit")
Liz Fong-Jones uploaded patch set #2 to this change.
Related details
Attention is currently required from:
- Ian Lance Taylor
- Keith Randall
- Michael Pratt
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Liz Fong-Jones (Gerrit)
Aug 22, 2026, 6:13:17 AMAug 22
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Ian Lance Taylor, Keith Randall and Michael Pratt
Liz Fong-Jones uploaded new patchset![]( "Open in Gerrit")
Liz Fong-Jones uploaded patch set #3 to this change.
Related details
Attention is currently required from:
- Ian Lance Taylor
- Keith Randall
- Michael Pratt
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Liz Fong-Jones (Gerrit)
Aug 22, 2026, 6:16:11 AMAug 22
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Ian Lance Taylor, Keith Randall and Michael Pratt
Liz Fong-Jones uploaded new patchset![]( "Open in Gerrit")
Liz Fong-Jones uploaded patch set #4 to this change.
Related details
Attention is currently required from:
- Ian Lance Taylor
- Keith Randall
- Michael Pratt
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Liz Fong-Jones (Gerrit)
Aug 22, 2026, 6:16:43 AMAug 22
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Ian Lance Taylor, Keith Randall and Michael Pratt
Liz Fong-Jones uploaded new patchset![]( "Open in Gerrit")
Liz Fong-Jones uploaded patch set #5 to this change.
Related details
Attention is currently required from:
- Ian Lance Taylor
- Keith Randall
- Michael Pratt
Submit Requirements:
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Ian Lance Taylor (Gerrit)
Aug 22, 2026, 12:38:33 PMAug 22
to Liz Fong-Jones, goph...@pubsubhelper.golang.org, Ian Lance Taylor, Keith Randall, Michael Pratt, Gopher Robot, golang-co...@googlegroups.com
Attention needed from Keith Randall, Liz Fong-Jones and Michael Pratt
Ian Lance Taylor voted and added 1 comment![]( "Open in Gerrit")
Attention is currently required from:
- Keith Randall
- Liz Fong-Jones
- Michael Pratt
Submit Requirements:
Code-Review
No-Holds
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Liz Fong-Jones (Gerrit)
Sep 22, 2026, 10:10:32 PMSep 22
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Liz Fong-Jones and Michael Pratt
Liz Fong-Jones uploaded new patchset![]( "Open in Gerrit")
Attention is currently required from:
- Liz Fong-Jones
- Michael Pratt
Submit Requirements:
Code-Review
No-Holds
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Liz Fong-Jones (Gerrit)
Sep 22, 2026, 10:20:25 PMSep 22
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Liz Fong-Jones and Michael Pratt
Liz Fong-Jones uploaded new patchset![]( "Open in Gerrit")
Liz Fong-Jones uploaded patch set #7 to this change.
Related details
Attention is currently required from:
- Liz Fong-Jones
- Michael Pratt
Submit Requirements:
Code-Review
No-Holds
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Liz Fong-Jones (Gerrit)
Sep 22, 2026, 10:22:08 PMSep 22
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Liz Fong-Jones and Michael Pratt
Liz Fong-Jones uploaded new patchset![]( "Open in Gerrit")
Liz Fong-Jones uploaded patch set #8 to this change.
Related details
Attention is currently required from:
- Liz Fong-Jones
- Michael Pratt
Submit Requirements:
Code-Review
No-Holds
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Liz Fong-Jones (Gerrit)
Sep 22, 2026, 10:22:39 PMSep 22
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Liz Fong-Jones and Michael Pratt
Liz Fong-Jones uploaded new patchset![]( "Open in Gerrit")
Liz Fong-Jones uploaded patch set #9 to this change.
Related details
Attention is currently required from:
- Liz Fong-Jones
- Michael Pratt
Submit Requirements:
Code-Review
No-Holds
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Liz Fong-Jones (Gerrit)
Sep 25, 2026, 3:21:32 PMSep 25
to goph...@pubsubhelper.golang.org, golang-co...@googlegroups.com
Attention needed from Liz Fong-Jones and Michael Pratt
Liz Fong-Jones uploaded new patchset![]( "Open in Gerrit")
Liz Fong-Jones uploaded patch set #10 to this change.
Related details
Attention is currently required from:
- Liz Fong-Jones
- Michael Pratt
Submit Requirements:
Code-Review
No-Holds
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Reply all
Reply to author
Forward
0 new messages