Add //pkg/sync:generic_atomicptrmap.

AtomicPtrMap is a generic concurrent map from arbitrary keys to arbitrary
pointer values.

Benchmarks:
name                                                            time/op
StoreDelete/RWMutexMap-12                                        335ns ± 1%
StoreDelete/SyncMap-12                                           705ns ± 3%
StoreDelete/AtomicPtrMap-12                                      287ns ± 4%
StoreDelete/AtomicPtrMapSharded-12                               289ns ± 1%
LoadOrStoreDelete/RWMutexMap-12                                  342ns ± 2%
LoadOrStoreDelete/SyncMap-12                                     662ns ± 2%
LoadOrStoreDelete/AtomicPtrMap-12                                290ns ± 7%
LoadOrStoreDelete/AtomicPtrMapSharded-12                         293ns ± 2%
LookupPositive/RWMutexMap-12                                     101ns ±26%
LookupPositive/SyncMap-12                                        202ns ± 2%
LookupPositive/AtomicPtrMap-12                                  71.1ns ± 2%
LookupPositive/AtomicPtrMapSharded-12                           73.2ns ± 1%
LookupNegative/RWMutexMap-12                                     119ns ± 1%
LookupNegative/SyncMap-12                                        154ns ± 1%
LookupNegative/AtomicPtrMap-12                                  84.7ns ± 3%
LookupNegative/AtomicPtrMapSharded-12                           86.8ns ± 1%
Concurrent/FixedKeys_1PercentWrites_RWMutexMap-12               1.32µs ± 2%
Concurrent/FixedKeys_1PercentWrites_SyncMap-12                  52.7ns ±10%
Concurrent/FixedKeys_1PercentWrites_AtomicPtrMap-12             31.8ns ±20%
Concurrent/FixedKeys_1PercentWrites_AtomicPtrMapSharded-12      24.0ns ±15%
Concurrent/FixedKeys_10PercentWrites_RWMutexMap-12               860ns ± 3%
Concurrent/FixedKeys_10PercentWrites_SyncMap-12                 68.8ns ±20%
Concurrent/FixedKeys_10PercentWrites_AtomicPtrMap-12            98.6ns ± 7%
Concurrent/FixedKeys_10PercentWrites_AtomicPtrMapSharded-12     42.0ns ±25%
Concurrent/FixedKeys_50PercentWrites_RWMutexMap-12              1.17µs ± 3%
Concurrent/FixedKeys_50PercentWrites_SyncMap-12                  136ns ±34%
Concurrent/FixedKeys_50PercentWrites_AtomicPtrMap-12             286ns ± 3%
Concurrent/FixedKeys_50PercentWrites_AtomicPtrMapSharded-12      115ns ±35%
Concurrent/ChangingKeys_1PercentWrites_RWMutexMap-12            1.27µs ± 2%
Concurrent/ChangingKeys_1PercentWrites_SyncMap-12               5.01µs ± 3%
Concurrent/ChangingKeys_1PercentWrites_AtomicPtrMap-12          38.1ns ± 3%
Concurrent/ChangingKeys_1PercentWrites_AtomicPtrMapSharded-12   22.6ns ± 2%
Concurrent/ChangingKeys_10PercentWrites_RWMutexMap-12           1.08µs ± 2%
Concurrent/ChangingKeys_10PercentWrites_SyncMap-12              5.97µs ± 1%
Concurrent/ChangingKeys_10PercentWrites_AtomicPtrMap-12          390ns ± 2%
Concurrent/ChangingKeys_10PercentWrites_AtomicPtrMapSharded-12  93.6ns ± 1%
Concurrent/ChangingKeys_50PercentWrites_RWMutexMap-12           1.77µs ± 2%
Concurrent/ChangingKeys_50PercentWrites_SyncMap-12              8.07µs ± 2%
Concurrent/ChangingKeys_50PercentWrites_AtomicPtrMap-12         1.61µs ± 2%
Concurrent/ChangingKeys_50PercentWrites_AtomicPtrMapSharded-12   386ns ± 1%

Updates #231

PiperOrigin-RevId: 346614776

1 files changed, 53 insertions, 0 deletions

diff --git a/pkg/sync/runtime_unsafe.go b/pkg/sync/runtime_unsafe.go
index 7ad6a4434..e925e2e5b 100644
--- a/pkg/sync/runtime_unsafe.go
+++ b/pkg/sync/runtime_unsafe.go
@@ -11,6 +11,8 @@
 package sync
 
 import (
+	"fmt"
+	"reflect"
 	"unsafe"
 )
 
@@ -61,6 +63,57 @@ const (
 	TraceEvGoBlockSelect byte = 24
 )
 
+// Rand32 returns a non-cryptographically-secure random uint32.
+func Rand32() uint32 {
+	return fastrand()
+}
+
+// Rand64 returns a non-cryptographically-secure random uint64.
+func Rand64() uint64 {
+	return uint64(fastrand())<<32 | uint64(fastrand())
+}
+
+//go:linkname fastrand runtime.fastrand
+func fastrand() uint32
+
+// RandUintptr returns a non-cryptographically-secure random uintptr.
+func RandUintptr() uintptr {
+	if unsafe.Sizeof(uintptr(0)) == 4 {
+		return uintptr(Rand32())
+	}
+	return uintptr(Rand64())
+}
+
+// MapKeyHasher returns a hash function for pointers of m's key type.
+//
+// Preconditions: m must be a map.
+func MapKeyHasher(m interface{}) func(unsafe.Pointer, uintptr) uintptr {
+	if rtyp := reflect.TypeOf(m); rtyp.Kind() != reflect.Map {
+		panic(fmt.Sprintf("sync.MapKeyHasher: m is %v, not map", rtyp))
+	}
+	mtyp := *(**maptype)(unsafe.Pointer(&m))
+	return mtyp.hasher
+}
+
+type maptype struct {
+	size       uintptr
+	ptrdata    uintptr
+	hash       uint32
+	tflag      uint8
+	align      uint8
+	fieldAlign uint8
+	kind       uint8
+	equal      func(unsafe.Pointer, unsafe.Pointer) bool
+	gcdata     *byte
+	str        int32
+	ptrToThis  int32
+	key        unsafe.Pointer
+	elem       unsafe.Pointer
+	bucket     unsafe.Pointer
+	hasher     func(unsafe.Pointer, uintptr) uintptr
+	// more fields
+}
+
 // These functions are only used within the sync package.
 
 //go:linkname semacquire sync.runtime_Semacquire