Repository: puzpuzpuz/xsync
Pull request #76 (2022-10-31 16:58:42)

Optimize MapOf integer hash function
Benchmarks for `MapOf[int, int]` with 64 keys

Before:
```
BenchmarkIntegerMapOf_WarmUp/reads=100%-8         	170225940	         7.107 ns/op	       0 B/op	       0 allocs/op
BenchmarkIntegerMapOf_WarmUp/reads=99%-8          	147592124	         8.331 ns/op	       0 B/op	       0 allocs/op
BenchmarkIntegerMapOf_WarmUp/reads=90%-reads-8    	100000000	        11.09 ns/op	       1 B/op	       0 allocs/op
BenchmarkIntegerMapOf_WarmUp/reads=75%-reads-8    	78332457	        16.03 ns/op	       4 B/op	       0 allocs/op
```

After:
```
BenchmarkIntegerMapOf_WarmUp/reads=100%-8         	208831473	         5.325 ns/op	       0 B/op	       0 allocs/op
BenchmarkIntegerMapOf_WarmUp/reads=99%-8          	180287820	         6.516 ns/op	       0 B/op	       0 allocs/op
BenchmarkIntegerMapOf_WarmUp/reads=90%-reads-8    	127232131	         9.812 ns/op	       1 B/op	       0 allocs/op
BenchmarkIntegerMapOf_WarmUp/reads=75%-reads-8    	84348110	        13.95 ns/op	       4 B/op	       0 allocs/op
```


Patch:
diff --git a/map.go b/map.go
index b8ff875..5f4a972 100644
--- a/map.go
+++ b/map.go
@@ -172,11 +172,11 @@ func (m *Map) Load(key string) (value interface{}, ok bool) {
 				}
 			}
 		}
-		bucketPtr := atomic.LoadPointer(&b.next)
-		if bucketPtr == nil {
+		bptr := atomic.LoadPointer(&b.next)
+		if bptr == nil {
 			return
 		}
-		b = (*bucketPadded)(bucketPtr)
+		b = (*bucketPadded)(bptr)
 	}
 }
 
@@ -580,11 +580,11 @@ func (m *Map) Range(f func(key string, value interface{}) bool) {
 					return
 				}
 			}
-			bucketPtr := atomic.LoadPointer(&b.next)
-			if bucketPtr == nil {
+			bptr := atomic.LoadPointer(&b.next)
+			if bptr == nil {
 				break
 			}
-			b = (*bucketPadded)(bucketPtr)
+			b = (*bucketPadded)(bptr)
 		}
 	}
 }
@@ -703,7 +703,9 @@ func (table *mapTable) sumSize() int64 {
 }
 
 type mapStats struct {
-	TableLen     int
+	RootBuckets  int
+	TotalBuckets int
+	EmptyBuckets int
 	Capacity     int
 	Size         int // calculated number of entries
 	Counter      int // number of entries according to table counter
@@ -716,7 +718,9 @@ type mapStats struct {
 
 func (s *mapStats) Print() {
 	fmt.Println("---")
-	fmt.Printf("TableLen:     %d\n", s.TableLen)
+	fmt.Printf("RootBuckets:  %d\n", s.RootBuckets)
+	fmt.Printf("TotalBuckets: %d\n", s.TotalBuckets)
+	fmt.Printf("EmptyBuckets: %d\n", s.EmptyBuckets)
 	fmt.Printf("Capacity:     %d\n", s.Capacity)
 	fmt.Printf("Size:         %d\n", s.Size)
 	fmt.Printf("Counter:      %d\n", s.Counter)
@@ -736,30 +740,37 @@ func (m *Map) stats() mapStats {
 		MinEntries:   math.MaxInt32,
 	}
 	table := (*mapTable)(atomic.LoadPointer(&m.table))
-	stats.TableLen = len(table.buckets)
+	stats.RootBuckets = len(table.buckets)
 	stats.Counter = int(table.sumSize())
 	stats.CounterLen = len(table.size)
 	for i := range table.buckets {
-		numEntries := 0
+		nentries := 0
 		b := &table.buckets[i]
+		stats.TotalBuckets++
 		for {
+			nentriesLocal := 0
 			stats.Capacity += entriesPerMapBucket
 			for i := 0; i < entriesPerMapBucket; i++ {
 				if atomic.LoadPointer(&b.keys[i]) != nil {
 					stats.Size++
-					numEntries++
+					nentriesLocal++
 				}
 			}
+			nentries += nentriesLocal
+			if nentriesLocal == 0 {
+				stats.EmptyBuckets++
+			}
 			if b.next == nil {
 				break
 			}
 			b = (*bucketPadded)(b.next)
+			stats.TotalBuckets++
 		}
-		if numEntries < stats.MinEntries {
-			stats.MinEntries = numEntries
+		if nentries < stats.MinEntries {
+			stats.MinEntries = nentries
 		}
-		if numEntries > stats.MaxEntries {
-			stats.MaxEntries = numEntries
+		if nentries > stats.MaxEntries {
+			stats.MaxEntries = nentries
 		}
 	}
 	return stats
diff --git a/mapof.go b/mapof.go
index 63ce1eb..44932c9 100644
--- a/mapof.go
+++ b/mapof.go
@@ -52,7 +52,9 @@ type IntegerConstraint interface {
 
 // NewIntegerMapOf creates a new MapOf instance with integer typed keys.
 func NewIntegerMapOf[K IntegerConstraint, V any]() *MapOf[K, V] {
-	return NewTypedMapOf[K, V](hash64[K])
+	return NewTypedMapOf[K, V](func(s maphash.Seed, k K) uint64 {
+		return hashUint64(s, uint64(k))
+	})
 }
 
 // NewTypedMapOf creates a new MapOf instance with arbitrarily typed keys.
@@ -97,11 +99,11 @@ func (m *MapOf[K, V]) Load(key K) (value V, ok bool) {
 				}
 			}
 		}
-		bucketPtr := atomic.LoadPointer(&b.next)
-		if bucketPtr == nil {
+		bptr := atomic.LoadPointer(&b.next)
+		if bptr == nil {
 			return
 		}
-		b = (*bucketPadded)(bucketPtr)
+		b = (*bucketPadded)(bptr)
 	}
 }
 
@@ -470,11 +472,11 @@ func (m *MapOf[K, V]) Range(f func(key K, value V) bool) {
 					return
 				}
 			}
-			bucketPtr := atomic.LoadPointer(&b.next)
-			if bucketPtr == nil {
+			bptr := atomic.LoadPointer(&b.next)
+			if bptr == nil {
 				break
 			}
-			b = (*bucketPadded)(bucketPtr)
+			b = (*bucketPadded)(bptr)
 		}
 	}
 }
@@ -507,41 +509,38 @@ func (m *MapOf[K, V]) stats() mapStats {
 		MinEntries:   math.MaxInt32,
 	}
 	table := (*mapTable)(atomic.LoadPointer(&m.table))
-	stats.TableLen = len(table.buckets)
+	stats.RootBuckets = len(table.buckets)
 	stats.Counter = int(table.sumSize())
 	stats.CounterLen = len(table.size)
 	for i := range table.buckets {
-		numEntries := 0
+		nentries := 0
 		b := &table.buckets[i]
+		stats.TotalBuckets++
 		for {
+			nentriesLocal := 0
 			stats.Capacity += entriesPerMapBucket
 			for i := 0; i < entriesPerMapBucket; i++ {
 				if atomic.LoadPointer(&b.keys[i]) != nil {
 					stats.Size++
-					numEntries++
+					nentriesLocal++
 				}
 			}
+			nentries += nentriesLocal
+			if nentriesLocal == 0 {
+				stats.EmptyBuckets++
+			}
 			if b.next == nil {
 				break
 			}
 			b = (*bucketPadded)(b.next)
+			stats.TotalBuckets++
 		}
-		if numEntries < stats.MinEntries {
-			stats.MinEntries = numEntries
+		if nentries < stats.MinEntries {
+			stats.MinEntries = nentries
 		}
-		if numEntries > stats.MaxEntries {
-			stats.MaxEntries = numEntries
+		if nentries > stats.MaxEntries {
+			stats.MaxEntries = nentries
 		}
 	}
 	return stats
 }
-
-// hash64 calculates a hash of v with the given seed.
-func hash64[T IntegerConstraint](seed maphash.Seed, v T) uint64 {
-	n := uint64(v)
-	p := (*[8]byte)(unsafe.Pointer(&n))
-	var h maphash.Hash
-	h.SetSeed(seed)
-	h.Write((*p)[:])
-	return h.Sum64()
-}
diff --git a/util.go b/util.go
index 7a2b6be..4602415 100644
--- a/util.go
+++ b/util.go
@@ -3,6 +3,7 @@ package xsync
 import (
 	"hash/maphash"
 	"runtime"
+	"unsafe"
 	_ "unsafe"
 )
 
@@ -47,6 +48,18 @@ func parallelism() uint32 {
 	return numCores
 }
 
+// inthash64 is a hash function based on murmurhash3 64-bit finalizer.
+//
+//lint:ignore U1000 used in MapOf
+func hashUint64(seed maphash.Seed, v uint64) uint64 {
+	nseed := *(*uint64)(unsafe.Pointer(&seed))
+	return uint64(memhash64(unsafe.Pointer(&v), uintptr(nseed)))
+}
+
 //go:noescape
 //go:linkname fastrand runtime.fastrand
 func fastrand() uint32
+
+//go:noescape
+//go:linkname memhash64 runtime.memhash64
+func memhash64(p unsafe.Pointer, h uintptr) uintptr


Test patch:
diff --git a/map_test.go b/map_test.go
index 45c3090..b3693e3 100644
--- a/map_test.go
+++ b/map_test.go
@@ -537,12 +537,12 @@ func TestMapResize(t *testing.T) {
 	if stats.Size != numEntries {
 		t.Fatalf("size was too small: %d", stats.Size)
 	}
-	expectedCapacity := int(math.RoundToEven(MapLoadFactor+1)) * stats.TableLen * EntriesPerMapBucket
+	expectedCapacity := int(math.RoundToEven(MapLoadFactor+1)) * stats.RootBuckets * EntriesPerMapBucket
 	if stats.Capacity > expectedCapacity {
 		t.Fatalf("capacity was too large: %d, expected: %d", stats.Capacity, expectedCapacity)
 	}
-	if stats.TableLen <= MinMapTableLen {
-		t.Fatalf("table was too small: %d", stats.TableLen)
+	if stats.RootBuckets <= MinMapTableLen {
+		t.Fatalf("table was too small: %d", stats.RootBuckets)
 	}
 	if stats.TotalGrowths == 0 {
 		t.Fatalf("non-zero total growths expected: %d", stats.TotalGrowths)
@@ -560,12 +560,12 @@ func TestMapResize(t *testing.T) {
 	if stats.Size > 0 {
 		t.Fatalf("zero size was expected: %d", stats.Size)
 	}
-	expectedCapacity = stats.TableLen * EntriesPerMapBucket
+	expectedCapacity = stats.RootBuckets * EntriesPerMapBucket
 	if stats.Capacity != expectedCapacity {
 		t.Fatalf("capacity was too large: %d, expected: %d", stats.Capacity, expectedCapacity)
 	}
-	if stats.TableLen != MinMapTableLen {
-		t.Fatalf("table was too large: %d", stats.TableLen)
+	if stats.RootBuckets != MinMapTableLen {
+		t.Fatalf("table was too large: %d", stats.RootBuckets)
 	}
 	if stats.TotalShrinks == 0 {
 		t.Fatalf("non-zero total shrinks expected: %d", stats.TotalShrinks)
diff --git a/mapof_test.go b/mapof_test.go
index e6b5e8b..cd34da5 100644
--- a/mapof_test.go
+++ b/mapof_test.go
@@ -685,12 +685,12 @@ func TestMapOfResize(t *testing.T) {
 	if stats.Size != numEntries {
 		t.Fatalf("size was too small: %d", stats.Size)
 	}
-	expectedCapacity := int(math.RoundToEven(MapLoadFactor+1)) * stats.TableLen * EntriesPerMapBucket
+	expectedCapacity := int(math.RoundToEven(MapLoadFactor+1)) * stats.RootBuckets * EntriesPerMapBucket
 	if stats.Capacity > expectedCapacity {
 		t.Fatalf("capacity was too large: %d, expected: %d", stats.Capacity, expectedCapacity)
 	}
-	if stats.TableLen <= MinMapTableLen {
-		t.Fatalf("table was too small: %d", stats.TableLen)
+	if stats.RootBuckets <= MinMapTableLen {
+		t.Fatalf("table was too small: %d", stats.RootBuckets)
 	}
 	if stats.TotalGrowths == 0 {
 		t.Fatalf("non-zero total growths expected: %d", stats.TotalGrowths)
@@ -708,12 +708,12 @@ func TestMapOfResize(t *testing.T) {
 	if stats.Size > 0 {
 		t.Fatalf("zero size was expected: %d", stats.Size)
 	}
-	expectedCapacity = stats.TableLen * EntriesPerMapBucket
+	expectedCapacity = stats.RootBuckets * EntriesPerMapBucket
 	if stats.Capacity != expectedCapacity {
 		t.Fatalf("capacity was too large: %d, expected: %d", stats.Capacity, expectedCapacity)
 	}
-	if stats.TableLen != MinMapTableLen {
-		t.Fatalf("table was too large: %d", stats.TableLen)
+	if stats.RootBuckets != MinMapTableLen {
+		t.Fatalf("table was too large: %d", stats.RootBuckets)
 	}
 	if stats.TotalShrinks == 0 {
 		t.Fatalf("non-zero total shrinks expected: %d", stats.TotalShrinks)