From 0733682e5ff4cd294f5eccb31cbe87a543147bc6 Mon Sep 17 00:00:00 2001 From: Michael Pratt Date: Mon, 22 Apr 2024 15:48:57 -0400 Subject: 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 Reviewed-by: Keith Randall Auto-Submit: Michael Pratt LUCI-TryBot-Result: Go LUCI Reviewed-by: Michael Knyszek --- src/internal/runtime/maps/table_debug.go | 128 +++++++++++++++++++++++++++++++ 1 file changed, 128 insertions(+) create mode 100644 src/internal/runtime/maps/table_debug.go (limited to 'src/internal/runtime/maps/table_debug.go') diff --git a/src/internal/runtime/maps/table_debug.go b/src/internal/runtime/maps/table_debug.go new file mode 100644 index 0000000000..7170fb68fe --- /dev/null +++ b/src/internal/runtime/maps/table_debug.go @@ -0,0 +1,128 @@ +// 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 implements Go's builtin map type. +package maps + +import ( + sabi "internal/runtime/maps/internal/abi" + "unsafe" +) + +const debugLog = false + +func (t *table) checkInvariants() { + if !debugLog { + return + } + + // For every non-empty slot, verify we can retrieve the key using Get. + // Count the number of used and deleted slots. + var used uint64 + var deleted uint64 + var empty uint64 + for i := uint64(0); i <= t.groups.lengthMask; i++ { + g := t.groups.group(i) + for j := uint32(0); j < sabi.SwissMapGroupSlots; j++ { + c := g.ctrls().get(j) + switch { + case c == ctrlDeleted: + deleted++ + case c == ctrlEmpty: + empty++ + default: + used++ + + key := g.key(j) + + // Can't lookup keys that don't compare equal + // to themselves (e.g., NaN). + if !t.typ.Key.Equal(key, key) { + continue + } + + if _, ok := t.Get(key); !ok { + hash := t.typ.Hasher(key, t.seed) + print("invariant failed: slot(", i, "/", j, "): key ") + dump(key, t.typ.Key.Size_) + print(" not found [hash=", hash, ", h2=", h2(hash), " h1=", h1(hash), "]\n") + t.Print() + panic("invariant failed: slot: key not found") + } + } + } + } + + if used != t.used { + print("invariant failed: found ", used, " used slots, but used count is ", t.used, "\n") + t.Print() + panic("invariant failed: found mismatched used slot count") + } + + growthLeft := (t.capacity*maxAvgGroupLoad)/sabi.SwissMapGroupSlots - t.used - deleted + if growthLeft != t.growthLeft { + print("invariant failed: found ", t.growthLeft, " growthLeft, but expected ", growthLeft, "\n") + t.Print() + panic("invariant failed: found mismatched growthLeft") + } + if deleted != t.tombstones() { + print("invariant failed: found ", deleted, " tombstones, but expected ", t.tombstones(), "\n") + t.Print() + panic("invariant failed: found mismatched tombstones") + } + + if empty == 0 { + print("invariant failed: found no empty slots (violates probe invariant)\n") + t.Print() + panic("invariant failed: found no empty slots (violates probe invariant)") + } +} + +func (t *table) Print() { + print(`table{ + seed: `, t.seed, ` + capacity: `, t.capacity, ` + used: `, t.used, ` + growthLeft: `, t.growthLeft, ` + groups: +`) + + for i := uint64(0); i <= t.groups.lengthMask; i++ { + print("\t\tgroup ", i, "\n") + + g := t.groups.group(i) + ctrls := g.ctrls() + for j := uint32(0); j < sabi.SwissMapGroupSlots; j++ { + print("\t\t\tslot ", j, "\n") + + c := ctrls.get(j) + print("\t\t\t\tctrl ", c) + switch c { + case ctrlEmpty: + print(" (empty)\n") + case ctrlDeleted: + print(" (deleted)\n") + default: + print("\n") + } + + print("\t\t\t\tkey ") + dump(g.key(j), t.typ.Key.Size_) + println("") + print("\t\t\t\telem ") + dump(g.elem(j), t.typ.Elem.Size_) + println("") + } + } +} + +// TODO(prattmic): not in hex because print doesn't have a way to print in hex +// outside the runtime. +func dump(ptr unsafe.Pointer, size uintptr) { + for size > 0 { + print(*(*byte)(ptr), " ") + ptr = unsafe.Pointer(uintptr(ptr) + 1) + size-- + } +} -- cgit v1.3