internal/runtime/maps: initial swiss table map implementation

Add a new package that will contain a new "Swiss Table"
(https://abseil.io/about/design/swisstables) map implementation, which
is intended to eventually replace the existing runtime map
implementation.

This implementation is based on the fabulous
github.com/cockroachdb/swiss package contributed by Peter Mattis.

This CL adds an hash map implementation. It supports all the core
operations, but does not have incremental growth.

For #54766.

Change-Id: I52cf371448c3817d471ddb1f5a78f3513565db41
Reviewed-on: https://go-review.googlesource.com/c/go/+/582415
Reviewed-by: Keith Randall <khr@google.com>
Reviewed-by: Keith Randall <khr@golang.org>
Auto-Submit: Michael Pratt <mpratt@google.com>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Michael Knyszek <mknyszek@google.com>

1 files changed, 447 insertions, 0 deletions

diff --git a/src/internal/runtime/maps/map_test.go b/src/internal/runtime/maps/map_test.go
new file mode 100644
index 0000000000..53b4a62071
--- /dev/null
+++ b/src/internal/runtime/maps/map_test.go
@@ -0,0 +1,447 @@
+// Copyright 2024 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package maps_test
+
+import (
+	"fmt"
+	"internal/runtime/maps"
+	"internal/runtime/maps/internal/abi"
+	"math"
+	"testing"
+	"unsafe"
+)
+
+func TestCtrlSize(t *testing.T) {
+	cs := unsafe.Sizeof(maps.CtrlGroup(0))
+	if cs != abi.SwissMapGroupSlots {
+		t.Errorf("ctrlGroup size got %d want abi.SwissMapGroupSlots %d", cs, abi.SwissMapGroupSlots)
+	}
+}
+
+func TestTablePut(t *testing.T) {
+	tab := maps.NewTestTable[uint32, uint64](8)
+
+	key := uint32(0)
+	elem := uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		elem += 1
+		tab.Put(unsafe.Pointer(&key), unsafe.Pointer(&elem))
+
+		if maps.DebugLog {
+			fmt.Printf("After put %d: %v\n", key, tab)
+		}
+	}
+
+	key = uint32(0)
+	elem = uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		elem += 1
+		got, ok := tab.Get(unsafe.Pointer(&key))
+		if !ok {
+			t.Errorf("Get(%d) got ok false want true", key)
+		}
+		gotElem := *(*uint64)(got)
+		if gotElem != elem {
+			t.Errorf("Get(%d) got elem %d want %d", key, gotElem, elem)
+		}
+	}
+}
+
+func TestTableDelete(t *testing.T) {
+	tab := maps.NewTestTable[uint32, uint64](32)
+
+	key := uint32(0)
+	elem := uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		elem += 1
+		tab.Put(unsafe.Pointer(&key), unsafe.Pointer(&elem))
+
+		if maps.DebugLog {
+			fmt.Printf("After put %d: %v\n", key, tab)
+		}
+	}
+
+	key = uint32(0)
+	elem = uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		tab.Delete(unsafe.Pointer(&key))
+	}
+
+	key = uint32(0)
+	elem = uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		elem += 1
+		_, ok := tab.Get(unsafe.Pointer(&key))
+		if ok {
+			t.Errorf("Get(%d) got ok true want false", key)
+		}
+	}
+}
+
+func TestTableClear(t *testing.T) {
+	tab := maps.NewTestTable[uint32, uint64](32)
+
+	key := uint32(0)
+	elem := uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		elem += 1
+		tab.Put(unsafe.Pointer(&key), unsafe.Pointer(&elem))
+
+		if maps.DebugLog {
+			fmt.Printf("After put %d: %v\n", key, tab)
+		}
+	}
+
+	tab.Clear()
+
+	if tab.Used() != 0 {
+		t.Errorf("Clear() used got %d want 0", tab.Used())
+	}
+
+	key = uint32(0)
+	elem = uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		elem += 1
+		_, ok := tab.Get(unsafe.Pointer(&key))
+		if ok {
+			t.Errorf("Get(%d) got ok true want false", key)
+		}
+	}
+}
+
+// +0.0 and -0.0 compare equal, but we must still must update the key slot when
+// overwriting.
+func TestTableKeyUpdate(t *testing.T) {
+	tab := maps.NewTestTable[float64, uint64](8)
+
+	zero := float64(0.0)
+	negZero := math.Copysign(zero, -1.0)
+	elem := uint64(0)
+
+	tab.Put(unsafe.Pointer(&zero), unsafe.Pointer(&elem))
+	if maps.DebugLog {
+		fmt.Printf("After put %f: %v\n", zero, tab)
+	}
+
+	elem = 1
+	tab.Put(unsafe.Pointer(&negZero), unsafe.Pointer(&elem))
+	if maps.DebugLog {
+		fmt.Printf("After put %f: %v\n", negZero, tab)
+	}
+
+	if tab.Used() != 1 {
+		t.Errorf("Used() used got %d want 1", tab.Used())
+	}
+
+	it := new(maps.Iter)
+	it.Init(tab.Type(), tab)
+	it.Next()
+	keyPtr, elemPtr := it.Key(), it.Elem()
+	if keyPtr == nil {
+		t.Fatal("it.Key() got nil want key")
+	}
+
+	key := *(*float64)(keyPtr)
+	elem = *(*uint64)(elemPtr)
+	if math.Copysign(1.0, key) > 0 {
+		t.Errorf("map key %f has positive sign", key)
+	}
+	if elem != 1 {
+		t.Errorf("map elem got %d want 1", elem)
+	}
+}
+
+func TestTableIteration(t *testing.T) {
+	tab := maps.NewTestTable[uint32, uint64](8)
+
+	key := uint32(0)
+	elem := uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		elem += 1
+		tab.Put(unsafe.Pointer(&key), unsafe.Pointer(&elem))
+
+		if maps.DebugLog {
+			fmt.Printf("After put %d: %v\n", key, tab)
+		}
+	}
+
+	got := make(map[uint32]uint64)
+
+	it := new(maps.Iter)
+	it.Init(tab.Type(), tab)
+	for {
+		it.Next()
+		keyPtr, elemPtr := it.Key(), it.Elem()
+		if keyPtr == nil {
+			break
+		}
+
+		key := *(*uint32)(keyPtr)
+		elem := *(*uint64)(elemPtr)
+		got[key] = elem
+	}
+
+	if len(got) != 31 {
+		t.Errorf("Iteration got %d entries, want 31: %+v", len(got), got)
+	}
+
+	key = uint32(0)
+	elem = uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		elem += 1
+		gotElem, ok := got[key]
+		if !ok {
+			t.Errorf("Iteration missing key %d", key)
+			continue
+		}
+		if gotElem != elem {
+			t.Errorf("Iteration key %d got elem %d want %d", key, gotElem, elem)
+		}
+	}
+}
+
+// Deleted keys shouldn't be visible in iteration.
+func TestTableIterationDelete(t *testing.T) {
+	tab := maps.NewTestTable[uint32, uint64](8)
+
+	key := uint32(0)
+	elem := uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		elem += 1
+		tab.Put(unsafe.Pointer(&key), unsafe.Pointer(&elem))
+
+		if maps.DebugLog {
+			fmt.Printf("After put %d: %v\n", key, tab)
+		}
+	}
+
+	got := make(map[uint32]uint64)
+	first := true
+	deletedKey := uint32(1)
+	it := new(maps.Iter)
+	it.Init(tab.Type(), tab)
+	for {
+		it.Next()
+		keyPtr, elemPtr := it.Key(), it.Elem()
+		if keyPtr == nil {
+			break
+		}
+
+		key := *(*uint32)(keyPtr)
+		elem := *(*uint64)(elemPtr)
+		got[key] = elem
+
+		if first {
+			first = false
+
+			// If the key we intended to delete was the one we just
+			// saw, pick another to delete.
+			if key == deletedKey {
+				deletedKey++
+			}
+			tab.Delete(unsafe.Pointer(&deletedKey))
+		}
+	}
+
+	if len(got) != 30 {
+		t.Errorf("Iteration got %d entries, want 30: %+v", len(got), got)
+	}
+
+	key = uint32(0)
+	elem = uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		elem += 1
+
+		wantOK := true
+		if key == deletedKey {
+			wantOK = false
+		}
+
+		gotElem, gotOK := got[key]
+		if gotOK != wantOK {
+			t.Errorf("Iteration key %d got ok %v want ok %v", key, gotOK, wantOK)
+			continue
+		}
+		if wantOK && gotElem != elem {
+			t.Errorf("Iteration key %d got elem %d want %d", key, gotElem, elem)
+		}
+	}
+}
+
+// Deleted keys shouldn't be visible in iteration even after a grow.
+func TestTableIterationGrowDelete(t *testing.T) {
+	tab := maps.NewTestTable[uint32, uint64](8)
+
+	key := uint32(0)
+	elem := uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		elem += 1
+		tab.Put(unsafe.Pointer(&key), unsafe.Pointer(&elem))
+
+		if maps.DebugLog {
+			fmt.Printf("After put %d: %v\n", key, tab)
+		}
+	}
+
+	got := make(map[uint32]uint64)
+	first := true
+	deletedKey := uint32(1)
+	it := new(maps.Iter)
+	it.Init(tab.Type(), tab)
+	for {
+		it.Next()
+		keyPtr, elemPtr := it.Key(), it.Elem()
+		if keyPtr == nil {
+			break
+		}
+
+		key := *(*uint32)(keyPtr)
+		elem := *(*uint64)(elemPtr)
+		got[key] = elem
+
+		if first {
+			first = false
+
+			// If the key we intended to delete was the one we just
+			// saw, pick another to delete.
+			if key == deletedKey {
+				deletedKey++
+			}
+
+			// Double the number of elements to force a grow.
+			key := uint32(32)
+			elem := uint64(256 + 32)
+
+			for i := 0; i < 31; i++ {
+				key += 1
+				elem += 1
+				tab.Put(unsafe.Pointer(&key), unsafe.Pointer(&elem))
+
+				if maps.DebugLog {
+					fmt.Printf("After put %d: %v\n", key, tab)
+				}
+			}
+
+			// Then delete from the grown map.
+			tab.Delete(unsafe.Pointer(&deletedKey))
+		}
+	}
+
+	// Don't check length: the number of new elements we'll see is
+	// unspecified.
+
+	// Check values only of the original pre-iteration entries.
+	key = uint32(0)
+	elem = uint64(256 + 0)
+
+	for i := 0; i < 31; i++ {
+		key += 1
+		elem += 1
+
+		wantOK := true
+		if key == deletedKey {
+			wantOK = false
+		}
+
+		gotElem, gotOK := got[key]
+		if gotOK != wantOK {
+			t.Errorf("Iteration key %d got ok %v want ok %v", key, gotOK, wantOK)
+			continue
+		}
+		if wantOK && gotElem != elem {
+			t.Errorf("Iteration key %d got elem %d want %d", key, gotElem, elem)
+		}
+	}
+}
+
+func TestAlignUpPow2(t *testing.T) {
+	tests := []struct {
+		in       uint64
+		want     uint64
+		overflow bool
+	}{
+		{
+			in:   0,
+			want: 0,
+		},
+		{
+			in:   3,
+			want: 4,
+		},
+		{
+			in:   4,
+			want: 4,
+		},
+		{
+			in:   1 << 63,
+			want: 1 << 63,
+		},
+		{
+			in:   (1 << 63) - 1,
+			want: 1 << 63,
+		},
+		{
+			in:       (1 << 63) + 1,
+			overflow: true,
+		},
+	}
+
+	for _, tc := range tests {
+		got, overflow := maps.AlignUpPow2(tc.in)
+		if got != tc.want {
+			t.Errorf("alignUpPow2(%d) got %d, want %d", tc.in, got, tc.want)
+		}
+		if overflow != tc.overflow {
+			t.Errorf("alignUpPow2(%d) got overflow %v, want %v", tc.in, overflow, tc.overflow)
+		}
+	}
+}
+
+// Verify that a table with zero-size slot is safe to use.
+func TestTableZeroSizeSlot(t *testing.T) {
+	tab := maps.NewTestTable[struct{}, struct{}](8)
+
+	key := struct{}{}
+	elem := struct{}{}
+
+	tab.Put(unsafe.Pointer(&key), unsafe.Pointer(&elem))
+
+	if maps.DebugLog {
+		fmt.Printf("After put %d: %v\n", key, tab)
+	}
+
+	got, ok := tab.Get(unsafe.Pointer(&key))
+	if !ok {
+		t.Errorf("Get(%d) got ok false want true", key)
+	}
+	gotElem := *(*struct{})(got)
+	if gotElem != elem {
+		t.Errorf("Get(%d) got elem %d want %d", key, gotElem, elem)
+	}
+}