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>

2 files changed, 59 insertions, 19 deletions

diff --git a/src/reflect/export_test.go b/src/reflect/export_test.go
index fc209fdfba..51b57c780c 100644
--- a/src/reflect/export_test.go
+++ b/src/reflect/export_test.go
@@ -154,6 +154,5 @@ var InternalIsZero = isZero
 var IsRegularMemory = isRegularMemory
 
 func MapGroupOf(x, y Type) Type {
-	grp, _ := groupAndSlotOf(x, y)
-	return grp
+	return groupOf(x, y)
 }
diff --git a/src/reflect/map.go b/src/reflect/map.go
index 9d25b1818c..c67c0668a1 100644
--- a/src/reflect/map.go
+++ b/src/reflect/map.go
@@ -6,6 +6,7 @@ package reflect
 
 import (
 	"internal/abi"
+	"internal/goexperiment"
 	"internal/race"
 	"internal/runtime/maps"
 	"internal/runtime/sys"
@@ -50,7 +51,7 @@ func MapOf(key, elem Type) Type {
 		}
 	}
 
-	group, slot := groupAndSlotOf(key, elem)
+	group := groupOf(key, elem)
 
 	// Make a map type.
 	// Note: flag values must match those used in the TMAP case
@@ -67,8 +68,25 @@ func MapOf(key, elem Type) Type {
 		return typehash(ktyp, p, seed)
 	}
 	mt.GroupSize = mt.Group.Size()
-	mt.SlotSize = slot.Size()
-	mt.ElemOff = slot.Field(1).Offset
+	if goexperiment.MapSplitGroup {
+		// Split layout: field 1 is keys array, field 2 is elems array.
+		mt.KeysOff = group.Field(1).Offset
+		mt.KeyStride = group.Field(1).Type.Elem().Size()
+		mt.ElemsOff = group.Field(2).Offset
+		mt.ElemStride = group.Field(2).Type.Elem().Size()
+		mt.ElemOff = 0
+	} else {
+		// Interleaved layout: field 1 is slots array.
+		// KeyStride = ElemStride = slot stride.
+		// ElemsOff = slots offset + elem offset within slot.
+		slot := group.Field(1).Type.Elem()
+		slotSize := slot.Size()
+		mt.KeysOff = group.Field(1).Offset
+		mt.KeyStride = slotSize
+		mt.ElemsOff = group.Field(1).Offset + slot.Field(1).Offset
+		mt.ElemStride = slotSize
+		mt.ElemOff = slot.Field(1).Offset
+	}
 	mt.Flags = 0
 	if needKeyUpdate(ktyp) {
 		mt.Flags |= abi.MapNeedKeyUpdate
@@ -88,15 +106,7 @@ func MapOf(key, elem Type) Type {
 	return ti.(Type)
 }
 
-func groupAndSlotOf(ktyp, etyp Type) (Type, Type) {
-	// type group struct {
-	//     ctrl uint64
-	//     slots [abi.MapGroupSlots]struct {
-	//         key  keyType
-	//         elem elemType
-	//     }
-	// }
-
+func groupOf(ktyp, etyp Type) Type {
 	if ktyp.Size() > abi.MapMaxKeyBytes {
 		ktyp = PointerTo(ktyp)
 	}
@@ -104,7 +114,39 @@ func groupAndSlotOf(ktyp, etyp Type) (Type, Type) {
 		etyp = PointerTo(etyp)
 	}
 
-	fields := []StructField{
+	if goexperiment.MapSplitGroup {
+		// Split layout (KKKKVVVV):
+		// type group struct {
+		//     ctrl  uint64
+		//     keys  [abi.MapGroupSlots]keyType
+		//     elems [abi.MapGroupSlots]elemType
+		// }
+		fields := []StructField{
+			{
+				Name: "Ctrl",
+				Type: TypeFor[uint64](),
+			},
+			{
+				Name: "Keys",
+				Type: ArrayOf(abi.MapGroupSlots, ktyp),
+			},
+			{
+				Name: "Elems",
+				Type: ArrayOf(abi.MapGroupSlots, etyp),
+			},
+		}
+		return StructOf(fields)
+	}
+
+	// Interleaved slot layout (KVKVKVKV):
+	// type group struct {
+	//     ctrl  uint64
+	//     slots [abi.MapGroupSlots]struct {
+	//         key  keyType
+	//         elem elemType
+	//     }
+	// }
+	slotFields := []StructField{
 		{
 			Name: "Key",
 			Type: ktyp,
@@ -114,9 +156,9 @@ func groupAndSlotOf(ktyp, etyp Type) (Type, Type) {
 			Type: etyp,
 		},
 	}
-	slot := StructOf(fields)
+	slot := StructOf(slotFields)
 
-	fields = []StructField{
+	fields := []StructField{
 		{
 			Name: "Ctrl",
 			Type: TypeFor[uint64](),
@@ -126,8 +168,7 @@ func groupAndSlotOf(ktyp, etyp Type) (Type, Type) {
 			Type: ArrayOf(abi.MapGroupSlots, slot),
 		},
 	}
-	group := StructOf(fields)
-	return group, slot
+	return StructOf(fields)
 }
 
 var stringType = rtypeOf("")