internal/runtime/maps: small maps point directly to a group

If the map contains 8 or fewer entries, it is wasteful to have a
directory that points to a table that points to a group.

Add a special case that replaces the directory with a direct pointer to
a group.

We could theoretically do similar for single table maps (no directory,
just point directly to a table), but that is left for later.

For #54766.

Cq-Include-Trybots: luci.golang.try:gotip-linux-amd64-longtest-swissmap
Change-Id: I6fc04dfc11c31dadfe5b5d6481b4c4abd43d48ed
Reviewed-on: https://go-review.googlesource.com/c/go/+/611188
Reviewed-by: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Auto-Submit: Michael Pratt <mpratt@google.com>
Reviewed-by: Keith Randall <khr@google.com>

1 files changed, 34 insertions, 7 deletions

diff --git a/src/internal/runtime/maps/export_test.go b/src/internal/runtime/maps/export_test.go
index 8f62739665..15c112e737 100644
--- a/src/internal/runtime/maps/export_test.go
+++ b/src/internal/runtime/maps/export_test.go
@@ -24,25 +24,47 @@ func NewTestMap[K comparable, V any](length uint64) (*Map, *abi.SwissMapType) {
 }
 
 func (m *Map) TableCount() int {
-	return len(m.directory)
+	if m.dirLen <= 0 {
+		return 0
+	}
+	return m.dirLen
 }
 
 // Total group count, summed across all tables.
 func (m *Map) GroupCount() uint64 {
+	if m.dirLen <= 0 {
+		if m.dirPtr == nil {
+			return 0
+		}
+		return 1
+	}
+
 	var n uint64
-	for _, t := range m.directory {
+	var lastTab *table
+	for i := range m.dirLen {
+		t := m.directoryAt(uintptr(i))
+		if t == lastTab {
+			continue
+		}
+		lastTab = t
 		n += t.groups.lengthMask + 1
 	}
 	return n
 }
 
-// Return a key from a group containing no empty slots, or nil if there are no
-// full groups.
+// Return a key from a group containing no empty slots.
 //
-// Also returns nil if a group is full but contains entirely deleted slots.
+// Returns nil if there are no full groups.
+// Returns nil if a group is full but contains entirely deleted slots.
+// Returns nil if the map is small.
 func (m *Map) KeyFromFullGroup() unsafe.Pointer {
+	if m.dirLen <= 0 {
+		return nil
+	}
+
 	var lastTab *table
-	for _, t := range m.directory {
+	for i := range m.dirLen {
+		t := m.directoryAt(uintptr(i))
 		if t == lastTab {
 			continue
 		}
@@ -68,10 +90,15 @@ func (m *Map) KeyFromFullGroup() unsafe.Pointer {
 	return nil
 }
 
+// Returns nil if the map is small.
 func (m *Map) TableFor(key unsafe.Pointer) *table {
+	if m.dirLen <= 0 {
+		return nil
+	}
+
 	hash := m.typ.Hasher(key, m.seed)
 	idx := m.directoryIndex(hash)
-	return m.directory[idx]
+	return m.directoryAt(idx)
 }
 
 func (t *table) GrowthLeft() uint64 {