internal/runtime/maps: add GOEXPERIMENT=mapsplitgroup for KKKKVVVV slot order

Map groups are currently:

type group struct {
    ctrl  uint64
    slots [8]slot
}

type slot struct {
    key  K
    elem E
}

If the element type is struct{}, the slot will be padded so that the
address of the elem is unique rather than pointing outside the alloc.
This has the effect of map[K]struct{} wasting space due to the extra
byte and padding, making it no better than map[K]bool.

This CL changes the group layout to instead place keys and elems
together, as they used to be before swiss maps:

type group struct {
    ctrl  uint64
    keys  [8]K
    elems [8]V
}

This is an alternative to CL 701976, which I suspect will have better
performance. Keys placed together should lead to better cache behavior,
at the cost of more expensive elem lookups, since the elems are not a
fixed offset from their keys.

This change is locked behind GOEXPERIMENT=mapsplitgroup.

Updates #70835
Updates #71368

Change-Id: Ide8d1406ae4ab636f86edc40e0640cc80653197c
Reviewed-on: https://go-review.googlesource.com/c/go/+/711560
Reviewed-by: Michael Pratt <mpratt@google.com>
Auto-Submit: Michael Pratt <mpratt@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Dmitri Shuralyov <dmitshur@google.com>

6 files changed, 109 insertions, 38 deletions

diff --git a/src/internal/runtime/maps/group.go b/src/internal/runtime/maps/group.go
index a56d32aca0..8f6c38790f 100644
--- a/src/internal/runtime/maps/group.go
+++ b/src/internal/runtime/maps/group.go
@@ -242,25 +242,29 @@ func ctrlGroupMatchFull(g ctrlGroup) bitset {
 // control word.
 type groupReference struct {
 	// data points to the group, which is described by typ.Group and has
-	// layout:
+	// layout depending on GOEXPERIMENT=mapsplitgroup:
 	//
+	// With mapsplitgroup (split arrays):
 	// type group struct {
 	// 	ctrls ctrlGroup
-	// 	slots [abi.MapGroupSlots]slot
+	// 	keys  [abi.MapGroupSlots]typ.Key
+	// 	elems [abi.MapGroupSlots]typ.Elem
 	// }
 	//
-	// type slot struct {
-	// 	key  typ.Key
-	// 	elem typ.Elem
+	// Without (interleaved slots):
+	// type group struct {
+	// 	ctrls ctrlGroup
+	// 	slots [abi.MapGroupSlots]struct {
+	// 		key  typ.Key
+	// 		elem typ.Elem
+	// 	}
 	// }
+	//
+	// In both cases, key(i) and elem(i) use the same formula via
+	// typ.KeysOff/KeyStride and typ.ElemsOff/ElemStride.
 	data unsafe.Pointer // data *typ.Group
 }
 
-const (
-	ctrlGroupsSize   = unsafe.Sizeof(ctrlGroup(0))
-	groupSlotsOffset = ctrlGroupsSize
-)
-
 // alignUp rounds n up to a multiple of a. a must be a power of 2.
 func alignUp(n, a uintptr) uintptr {
 	return (n + a - 1) &^ (a - 1)
@@ -287,14 +291,14 @@ func (g *groupReference) ctrls() *ctrlGroup {
 
 // key returns a pointer to the key at index i.
 func (g *groupReference) key(typ *abi.MapType, i uintptr) unsafe.Pointer {
-	offset := groupSlotsOffset + i*typ.SlotSize
+	offset := typ.KeysOff + i*typ.KeyStride
 
 	return unsafe.Pointer(uintptr(g.data) + offset)
 }
 
 // elem returns a pointer to the element at index i.
 func (g *groupReference) elem(typ *abi.MapType, i uintptr) unsafe.Pointer {
-	offset := groupSlotsOffset + i*typ.SlotSize + typ.ElemOff
+	offset := typ.ElemsOff + i*typ.ElemStride
 
 	return unsafe.Pointer(uintptr(g.data) + offset)
 }
diff --git a/src/internal/runtime/maps/runtime.go b/src/internal/runtime/maps/runtime.go
index 2c395d5c33..bd3ba6acc8 100644
--- a/src/internal/runtime/maps/runtime.go
+++ b/src/internal/runtime/maps/runtime.go
@@ -7,6 +7,7 @@ package maps
 import (
 	"internal/abi"
 	"internal/asan"
+	"internal/goexperiment"
 	"internal/msan"
 	"internal/race"
 	"internal/runtime/sys"
@@ -124,7 +125,12 @@ func runtime_mapaccess2(typ *abi.MapType, m *Map, key unsafe.Pointer) (unsafe.Po
 				slotKey = *((*unsafe.Pointer)(slotKey))
 			}
 			if typ.Key.Equal(key, slotKey) {
-				slotElem := unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
+				var slotElem unsafe.Pointer
+				if goexperiment.MapSplitGroup {
+					slotElem = g.elem(typ, i)
+				} else {
+					slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
+				}
 				if typ.IndirectElem() {
 					slotElem = *((*unsafe.Pointer)(slotElem))
 				}
@@ -223,7 +229,11 @@ outer:
 						typedmemmove(typ.Key, slotKey, key)
 					}
 
-					slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
+					if goexperiment.MapSplitGroup {
+						slotElem = g.elem(typ, i)
+					} else {
+						slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
+					}
 					if typ.IndirectElem() {
 						slotElem = *((*unsafe.Pointer)(slotElem))
 					}
@@ -265,7 +275,11 @@ outer:
 					}
 					typedmemmove(typ.Key, slotKey, key)
 
-					slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
+					if goexperiment.MapSplitGroup {
+						slotElem = g.elem(typ, i)
+					} else {
+						slotElem = unsafe.Pointer(uintptr(slotKeyOrig) + typ.ElemOff)
+					}
 					if typ.IndirectElem() {
 						emem := newobject(typ.Elem)
 						*(*unsafe.Pointer)(slotElem) = emem
diff --git a/src/internal/runtime/maps/runtime_fast32.go b/src/internal/runtime/maps/runtime_fast32.go
index da157c941d..dc3bd3fbd5 100644
--- a/src/internal/runtime/maps/runtime_fast32.go
+++ b/src/internal/runtime/maps/runtime_fast32.go
@@ -6,6 +6,7 @@ package maps
 
 import (
 	"internal/abi"
+	"internal/goexperiment"
 	"internal/race"
 	"internal/runtime/sys"
 	"unsafe"
@@ -40,14 +41,24 @@ func runtime_mapaccess2_fast32(typ *abi.MapType, m *Map, key uint32) (unsafe.Poi
 		}
 		full := g.ctrls().matchFull()
 		slotKey := g.key(typ, 0)
-		slotSize := typ.SlotSize
+		var keyStride uintptr
+		if goexperiment.MapSplitGroup {
+			keyStride = 4 // keys are contiguous in split layout
+		} else {
+			keyStride = typ.KeyStride // == SlotSize in interleaved layout
+		}
+		var i uintptr
 		for full != 0 {
 			if key == *(*uint32)(slotKey) && full.lowestSet() {
-				slotElem := unsafe.Pointer(uintptr(slotKey) + typ.ElemOff)
-				return slotElem, true
+				if goexperiment.MapSplitGroup {
+					return g.elem(typ, i), true
+				} else {
+					return unsafe.Pointer(uintptr(slotKey) + typ.ElemOff), true
+				}
 			}
-			slotKey = unsafe.Pointer(uintptr(slotKey) + slotSize)
+			slotKey = unsafe.Pointer(uintptr(slotKey) + keyStride)
 			full = full.shiftOutLowest()
+			i++
 		}
 		return unsafe.Pointer(&zeroVal[0]), false
 	}
@@ -83,8 +94,11 @@ func runtime_mapaccess2_fast32(typ *abi.MapType, m *Map, key uint32) (unsafe.Poi
 
 			slotKey := g.key(typ, i)
 			if key == *(*uint32)(slotKey) {
-				slotElem := unsafe.Pointer(uintptr(slotKey) + typ.ElemOff)
-				return slotElem, true
+				if goexperiment.MapSplitGroup {
+					return g.elem(typ, i), true
+				} else {
+					return unsafe.Pointer(uintptr(slotKey) + typ.ElemOff), true
+				}
 			}
 			match = match.removeFirst()
 		}
diff --git a/src/internal/runtime/maps/runtime_fast64.go b/src/internal/runtime/maps/runtime_fast64.go
index 6241d4ac6a..dac89eea81 100644
--- a/src/internal/runtime/maps/runtime_fast64.go
+++ b/src/internal/runtime/maps/runtime_fast64.go
@@ -6,6 +6,7 @@ package maps
 
 import (
 	"internal/abi"
+	"internal/goexperiment"
 	"internal/race"
 	"internal/runtime/sys"
 	"unsafe"
@@ -40,14 +41,24 @@ func runtime_mapaccess2_fast64(typ *abi.MapType, m *Map, key uint64) (unsafe.Poi
 		}
 		full := g.ctrls().matchFull()
 		slotKey := g.key(typ, 0)
-		slotSize := typ.SlotSize
+		var keyStride uintptr
+		if goexperiment.MapSplitGroup {
+			keyStride = 8 // keys are contiguous in split layout
+		} else {
+			keyStride = typ.KeyStride // == SlotSize in interleaved layout
+		}
+		var i uintptr
 		for full != 0 {
 			if key == *(*uint64)(slotKey) && full.lowestSet() {
-				slotElem := unsafe.Pointer(uintptr(slotKey) + 8)
-				return slotElem, true
+				if goexperiment.MapSplitGroup {
+					return g.elem(typ, i), true
+				} else {
+					return unsafe.Pointer(uintptr(slotKey) + 8), true
+				}
 			}
-			slotKey = unsafe.Pointer(uintptr(slotKey) + slotSize)
+			slotKey = unsafe.Pointer(uintptr(slotKey) + keyStride)
 			full = full.shiftOutLowest()
+			i++
 		}
 		return unsafe.Pointer(&zeroVal[0]), false
 	}
@@ -75,8 +86,11 @@ func runtime_mapaccess2_fast64(typ *abi.MapType, m *Map, key uint64) (unsafe.Poi
 
 			slotKey := g.key(typ, i)
 			if key == *(*uint64)(slotKey) {
-				slotElem := unsafe.Pointer(uintptr(slotKey) + 8)
-				return slotElem, true
+				if goexperiment.MapSplitGroup {
+					return g.elem(typ, i), true
+				} else {
+					return unsafe.Pointer(uintptr(slotKey) + 8), true
+				}
 			}
 			match = match.removeFirst()
 		}
diff --git a/src/internal/runtime/maps/runtime_faststr.go b/src/internal/runtime/maps/runtime_faststr.go
index 7778bd1881..a96f9feb04 100644
--- a/src/internal/runtime/maps/runtime_faststr.go
+++ b/src/internal/runtime/maps/runtime_faststr.go
@@ -7,6 +7,7 @@ package maps
 import (
 	"internal/abi"
 	"internal/goarch"
+	"internal/goexperiment"
 	"internal/race"
 	"internal/runtime/sys"
 	"unsafe"
@@ -19,7 +20,12 @@ func (m *Map) getWithoutKeySmallFastStr(typ *abi.MapType, key string) unsafe.Poi
 
 	ctrls := *g.ctrls()
 	slotKey := g.key(typ, 0)
-	slotSize := typ.SlotSize
+	var keyStride uintptr
+	if goexperiment.MapSplitGroup {
+		keyStride = 2 * goarch.PtrSize // keys are contiguous in split layout
+	} else {
+		keyStride = typ.KeyStride // == SlotSize in interleaved layout
+	}
 
 	// The 64 threshold was chosen based on performance of BenchmarkMapStringKeysEight,
 	// where there are 8 keys to check, all of which don't quick-match the lookup key.
@@ -37,7 +43,7 @@ func (m *Map) getWithoutKeySmallFastStr(typ *abi.MapType, key string) unsafe.Poi
 				}
 				j = i
 			}
-			slotKey = unsafe.Pointer(uintptr(slotKey) + slotSize)
+			slotKey = unsafe.Pointer(uintptr(slotKey) + keyStride)
 			ctrls >>= 8
 		}
 		if j == abi.MapGroupSlots {
@@ -47,7 +53,11 @@ func (m *Map) getWithoutKeySmallFastStr(typ *abi.MapType, key string) unsafe.Poi
 		// There's exactly one slot that passed the quick test. Do the single expensive comparison.
 		slotKey = g.key(typ, uintptr(j))
 		if key == *(*string)(slotKey) {
-			return unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize)
+			if goexperiment.MapSplitGroup {
+				return g.elem(typ, uintptr(j))
+			} else {
+				return unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize)
+			}
 		}
 		return nil
 	}
@@ -63,11 +73,15 @@ dohash:
 	ctrls = *g.ctrls()
 	slotKey = g.key(typ, 0)
 
-	for range abi.MapGroupSlots {
+	for i := range uintptr(abi.MapGroupSlots) {
 		if uint8(ctrls) == h2 && key == *(*string)(slotKey) {
-			return unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize)
+			if goexperiment.MapSplitGroup {
+				return g.elem(typ, i)
+			} else {
+				return unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize)
+			}
 		}
-		slotKey = unsafe.Pointer(uintptr(slotKey) + slotSize)
+		slotKey = unsafe.Pointer(uintptr(slotKey) + keyStride)
 		ctrls >>= 8
 	}
 	return nil
@@ -154,8 +168,11 @@ func runtime_mapaccess2_faststr(typ *abi.MapType, m *Map, key string) (unsafe.Po
 
 			slotKey := g.key(typ, i)
 			if key == *(*string)(slotKey) {
-				slotElem := unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize)
-				return slotElem, true
+				if goexperiment.MapSplitGroup {
+					return g.elem(typ, i), true
+				} else {
+					return unsafe.Pointer(uintptr(slotKey) + 2*goarch.PtrSize), true
+				}
 			}
 			match = match.removeFirst()
 		}
diff --git a/src/internal/runtime/maps/table.go b/src/internal/runtime/maps/table.go
index 977f3091ad..7ef47df37f 100644
--- a/src/internal/runtime/maps/table.go
+++ b/src/internal/runtime/maps/table.go
@@ -6,6 +6,7 @@ package maps
 
 import (
 	"internal/abi"
+	"internal/goexperiment"
 	"internal/runtime/math"
 	"unsafe"
 )
@@ -615,9 +616,16 @@ func (t *table) Clear(typ *abi.MapType) {
 	//  4) But if a group is really large, do the test anyway, as
 	//     clearing is expensive.
 	fullTest := uint64(t.used)*4 <= t.groups.lengthMask // less than ~0.25 entries per group -> >3/4 empty groups
-	if typ.SlotSize > 32 {
-		// For large slots, it is always worth doing the test first.
-		fullTest = true
+	if goexperiment.MapSplitGroup {
+		if (typ.KeyStride + typ.ElemStride) > 32 {
+			// For large slots, it is always worth doing the test first.
+			fullTest = true
+		}
+	} else {
+		if typ.KeyStride > 32 { // KeyStride == SlotSize in interleaved layout
+			// For large slots, it is always worth doing the test first.
+			fullTest = true
+		}
 	}
 	if fullTest {
 		for i := uint64(0); i <= t.groups.lengthMask; i++ {