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>

1 files changed, 69 insertions, 27 deletions

diff --git a/src/cmd/compile/internal/reflectdata/map.go b/src/cmd/compile/internal/reflectdata/map.go
index a7268bc849..38eada4522 100644
--- a/src/cmd/compile/internal/reflectdata/map.go
+++ b/src/cmd/compile/internal/reflectdata/map.go
@@ -13,6 +13,7 @@ import (
 	"cmd/internal/objabi"
 	"cmd/internal/src"
 	"internal/abi"
+	"internal/buildcfg"
 )
 
 // MapGroupType makes the map slot group type given the type of the map.
@@ -26,14 +27,6 @@ func MapGroupType(t *types.Type) *types.Type {
 	// a correct GC program for it.
 	//
 	// Make sure this stays in sync with internal/runtime/maps/group.go.
-	//
-	// type group struct {
-	//     ctrl uint64
-	//     slots [abi.MapGroupSlots]struct {
-	//         key  keyType
-	//         elem elemType
-	//     }
-	// }
 
 	keytype := t.Key()
 	elemtype := t.Elem()
@@ -46,19 +39,48 @@ func MapGroupType(t *types.Type) *types.Type {
 		elemtype = types.NewPtr(elemtype)
 	}
 
-	slotFields := []*types.Field{
-		makefield("key", keytype),
-		makefield("elem", elemtype),
-	}
-	slot := types.NewStruct(slotFields)
-	slot.SetNoalg(true)
+	var fields []*types.Field
+	if buildcfg.Experiment.MapSplitGroup {
+		// Split layout (KKKKVVVV):
+		// type group struct {
+		//     ctrl  uint64
+		//     keys  [abi.MapGroupSlots]keyType
+		//     elems [abi.MapGroupSlots]elemType
+		// }
+		keyArr := types.NewArray(keytype, abi.MapGroupSlots)
+		keyArr.SetNoalg(true)
 
-	slotArr := types.NewArray(slot, abi.MapGroupSlots)
-	slotArr.SetNoalg(true)
+		elemArr := types.NewArray(elemtype, abi.MapGroupSlots)
+		elemArr.SetNoalg(true)
 
-	fields := []*types.Field{
-		makefield("ctrl", types.Types[types.TUINT64]),
-		makefield("slots", slotArr),
+		fields = []*types.Field{
+			makefield("ctrl", types.Types[types.TUINT64]),
+			makefield("keys", keyArr),
+			makefield("elems", elemArr),
+		}
+	} else {
+		// Interleaved slot layout (KVKVKVKV):
+		// type group struct {
+		//     ctrl  uint64
+		//     slots [abi.MapGroupSlots]struct {
+		//         key  keyType
+		//         elem elemType
+		//     }
+		// }
+		slotFields := []*types.Field{
+			makefield("key", keytype),
+			makefield("elem", elemtype),
+		}
+		slot := types.NewStruct(slotFields)
+		slot.SetNoalg(true)
+
+		slotArr := types.NewArray(slot, abi.MapGroupSlots)
+		slotArr.SetNoalg(true)
+
+		fields = []*types.Field{
+			makefield("ctrl", types.Types[types.TUINT64]),
+			makefield("slots", slotArr),
+		}
 	}
 
 	group := types.NewStruct(fields)
@@ -269,13 +291,30 @@ func writeMapType(t *types.Type, lsym *obj.LSym, c rttype.Cursor) {
 	s3 := writeType(gtyp)
 	hasher := genhash(t.Key())
 
-	slotTyp := gtyp.Field(1).Type.Elem()
-	elemOff := slotTyp.Field(1).Offset
-	if types.AlgType(t.Key()) == types.AMEM && t.Key().Size() == 8 && elemOff != 8 {
-		base.Fatalf("runtime assumes elemOff for 8-byte keys is 8, got %d", elemOff)
-	}
-	if types.AlgType(t.Key()) == types.ASTRING && elemOff != int64(2*types.PtrSize) {
-		base.Fatalf("runtime assumes elemOff for string keys is %d, got %d", 2*types.PtrSize, elemOff)
+	var keysOff int64
+	var keyStride int64
+	var elemsOff int64
+	var elemStride int64
+	var elemOff int64
+	if buildcfg.Experiment.MapSplitGroup {
+		// Split layout: field 1 is keys array, field 2 is elems array.
+		keysOff = gtyp.Field(1).Offset
+		keyStride = gtyp.Field(1).Type.Elem().Size()
+		elemsOff = gtyp.Field(2).Offset
+		elemStride = gtyp.Field(2).Type.Elem().Size()
+	} else {
+		// Interleaved layout: field 1 is slots array.
+		// KeysOff = offset of slots array (first key).
+		// KeyStride = ElemStride = slot stride.
+		// ElemsOff = offset of slots + offset of elem within slot.
+		keysOff = gtyp.Field(1).Offset
+		slotTyp := gtyp.Field(1).Type.Elem()
+		slotSize := slotTyp.Size()
+		elemOffInSlot := slotTyp.Field(1).Offset
+		keyStride = slotSize
+		elemsOff = keysOff + elemOffInSlot
+		elemStride = slotSize
+		elemOff = slotTyp.Field(1).Offset
 	}
 
 	c.Field("Key").WritePtr(s1)
@@ -283,7 +322,10 @@ func writeMapType(t *types.Type, lsym *obj.LSym, c rttype.Cursor) {
 	c.Field("Group").WritePtr(s3)
 	c.Field("Hasher").WritePtr(hasher)
 	c.Field("GroupSize").WriteUintptr(uint64(gtyp.Size()))
-	c.Field("SlotSize").WriteUintptr(uint64(slotTyp.Size()))
+	c.Field("KeysOff").WriteUintptr(uint64(keysOff))
+	c.Field("KeyStride").WriteUintptr(uint64(keyStride))
+	c.Field("ElemsOff").WriteUintptr(uint64(elemsOff))
+	c.Field("ElemStride").WriteUintptr(uint64(elemStride))
 	c.Field("ElemOff").WriteUintptr(uint64(elemOff))
 	var flags uint32
 	if needkeyupdate(t.Key()) {