Repository: puzpuzpuz/xsync
Pull request #56 (2022-10-25 10:09:25)

Use hash/maphash instead of go:linkname hacks
This PR has two commits. The first is using maphash only as an implementation detail, without any API changes. The second commit makes the usage of `maphash` part of the API, which would simplify implementing good hash functions for custom types.

Merovius: There's some tradeoffs for the API. It would still be possible to just ignore the seed in a hash function, which would lead to a bad hash. If you want to actually prevent that, you could have the API hasher take an `io.Writer` and construct the seeded `*maphash.Hash` yourself. OTOH that might make the `*maphash.Hash` escape. Alternatively, you could still do the mixing as with `NewTypedMapOf`.

I thought to just leave that up to the user - if they ignore the seed, they will get a badly performing map, which seems on them. And this way, we don't pay for the extra hash if its not needed.

Also, I'm not sure that the example code doesn't escape the `*maphash.Hash` - `binary.Write` might not be inlineable. It would always be possible to do your own version of that as a user.
Merovius: PTAL.

One thing I realized is that it would be preferable to choose a new seed when resizing. Doing that would require more time than I'm willing to spend right now. But it won't cause any problems that where not already worse before, so that should be fine for now.
puzpuzpuz: If you're referring to https://github.com/golang/go/issues/25237, then the fix implemented in `src/runtime/map.go` is questionable. It only updates the seed when the map size goes down to zero. Also, changing the seed on resize is pretty straightforward - it's enough to store it in the `mapTable`. It's certainly not a must-have and I can do that in a separate PR.
puzpuzpuz: Thanks for the contribution!

Patch:
diff --git a/map.go b/map.go
index 8c5a9d9..40fc53f 100644
--- a/map.go
+++ b/map.go
@@ -2,6 +2,7 @@ package xsync
 
 import (
 	"fmt"
+	"hash/maphash"
 	"math"
 	"runtime"
 	"sync"
@@ -69,6 +70,7 @@ type Map struct {
 	resizeMu     sync.Mutex     // only used along with resizeCond
 	resizeCond   sync.Cond      // used to wake up resize waiters (concurrent modifications)
 	table        unsafe.Pointer // *mapTable
+	seed         maphash.Seed
 }
 
 type mapTable struct {
@@ -113,7 +115,9 @@ type rangeEntry struct {
 
 // NewMap creates a new Map instance.
 func NewMap() *Map {
-	m := &Map{}
+	m := &Map{
+		seed: maphash.MakeSeed(),
+	}
 	m.resizeCond = *sync.NewCond(&m.resizeMu)
 	table := newMapTable(minMapTableLen)
 	atomic.StorePointer(&m.table, unsafe.Pointer(table))
@@ -140,7 +144,7 @@ func newMapTable(size int) *mapTable {
 // value is present.
 // The ok result indicates whether value was found in the map.
 func (m *Map) Load(key string) (value interface{}, ok bool) {
-	hash := StrHash64(key)
+	hash := hashString(m.seed, key)
 	table := (*mapTable)(atomic.LoadPointer(&m.table))
 	bidx := bucketIdx(table, hash)
 	b := &table.buckets[bidx]
@@ -228,7 +232,7 @@ func (m *Map) doStore(key string, valueFn func() interface{}, loadIfExists bool)
 		}
 	}
 	// Write path.
-	hash := StrHash64(key)
+	hash := hashString(m.seed, key)
 	for {
 	store_attempt:
 		var (
@@ -378,7 +382,7 @@ func (m *Map) resize(table *mapTable, hint mapResizeHint) {
 		panic(fmt.Sprintf("unexpected resize hint: %d", hint))
 	}
 	for i := 0; i < tableLen; i++ {
-		copied := copyBucket(&table.buckets[i], newTable)
+		copied := copyBucket(&table.buckets[i], m.seed, newTable)
 		newTable.addSizePlain(uint64(i), copied)
 	}
 	// Publish the new table and wake up all waiters.
@@ -389,14 +393,14 @@ func (m *Map) resize(table *mapTable, hint mapResizeHint) {
 	m.resizeMu.Unlock()
 }
 
-func copyBucket(b *bucketPadded, destTable *mapTable) (copied int) {
+func copyBucket(b *bucketPadded, seed maphash.Seed, destTable *mapTable) (copied int) {
 	rootb := b
 	lockBucket(&rootb.topHashMutex)
 	for {
 		for i := 0; i < entriesPerMapBucket; i++ {
 			if b.keys[i] != nil {
 				k := derefKey(b.keys[i])
-				hash := StrHash64(k)
+				hash := hashString(seed, k)
 				bidx := bucketIdx(destTable, hash)
 				destb := &destTable.buckets[bidx]
 				appendToBucket(hash, b.keys[i], b.values[i], destb)
@@ -437,7 +441,7 @@ func appendToBucket(hash uint64, keyPtr, valPtr unsafe.Pointer, b *bucketPadded)
 // value if any. The loaded result reports whether the key was
 // present.
 func (m *Map) LoadAndDelete(key string) (value interface{}, loaded bool) {
-	hash := StrHash64(key)
+	hash := hashString(m.seed, key)
 	for {
 		hintNonEmpty := 0
 		table := (*mapTable)(atomic.LoadPointer(&m.table))
diff --git a/mapof.go b/mapof.go
index d9bf35f..57d5fa4 100644
--- a/mapof.go
+++ b/mapof.go
@@ -5,6 +5,7 @@ package xsync
 
 import (
 	"fmt"
+	"hash/maphash"
 	"math"
 	"sync"
 	"sync/atomic"
@@ -37,14 +38,13 @@ type MapOf[K comparable, V any] struct {
 	resizeMu     sync.Mutex     // only used along with resizeCond
 	resizeCond   sync.Cond      // used to wake up resize waiters (concurrent modifications)
 	table        unsafe.Pointer // *mapTable
-	hasher       func(K) uint64
+	seed         maphash.Seed
+	hasher       func(maphash.Seed, K) uint64
 }
 
 // NewMapOf creates a new MapOf instance with string keys
 func NewMapOf[V any]() *MapOf[string, V] {
-	return NewTypedMapOf[string, V](func(k string) uint64 {
-		return StrHash64(k)
-	})
+	return NewTypedMapOf[string, V](hashString)
 }
 
 // IntegerConstraint represents any integer type.
@@ -56,22 +56,18 @@ 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](func(k K) uint64 {
-		return uint64(k)
-	})
+	return NewTypedMapOf[K, V](hash64[K])
 }
 
 // NewTypedMapOf creates a new MapOf instance with arbitrarily typed keys.
-// Keys are hashed to uint64 using the hasher function. Note that StrHash64
-// function might be handy when writing the hasher function for structs with
-// string fields.
-func NewTypedMapOf[K comparable, V any](hasher func(K) uint64) *MapOf[K, V] {
+// Keys are hashed to uint64 using the hasher function. It is strongly
+// recommended to use the hash/maphash package to implement hasher. See the
+// example for how to do that.
+func NewTypedMapOf[K comparable, V any](hasher func(maphash.Seed, K) uint64) *MapOf[K, V] {
 	m := &MapOf[K, V]{}
 	m.resizeCond = *sync.NewCond(&m.resizeMu)
-	m.hasher = func(k K) uint64 {
-		// Apply finalizer to mitigate poor quality hash functions.
-		return mixhash64(hasher(k))
-	}
+	m.seed = maphash.MakeSeed()
+	m.hasher = hasher
 	table := newMapTable(minMapTableLen)
 	atomic.StorePointer(&m.table, unsafe.Pointer(table))
 	return m
@@ -81,7 +77,7 @@ func NewTypedMapOf[K comparable, V any](hasher func(K) uint64) *MapOf[K, V] {
 // value is present.
 // The ok result indicates whether value was found in the map.
 func (m *MapOf[K, V]) Load(key K) (value V, ok bool) {
-	hash := m.hasher(key)
+	hash := m.hasher(m.seed, key)
 	table := (*mapTable)(atomic.LoadPointer(&m.table))
 	bidx := bucketIdx(table, hash)
 	b := &table.buckets[bidx]
@@ -169,7 +165,7 @@ func (m *MapOf[K, V]) doStore(key K, valueFn func() V, loadIfExists bool) (V, bo
 		}
 	}
 	// Write path.
-	hash := m.hasher(key)
+	hash := m.hasher(m.seed, key)
 	for {
 	store_attempt:
 		var (
@@ -322,7 +318,7 @@ func (m *MapOf[K, V]) resize(table *mapTable, hint mapResizeHint) {
 		panic(fmt.Sprintf("unexpected resize hint: %d", hint))
 	}
 	for i := 0; i < tableLen; i++ {
-		copied := copyBucketOf(&table.buckets[i], newTable, m.hasher)
+		copied := copyBucketOf(&table.buckets[i], newTable, m.seed, m.hasher)
 		newTable.addSizePlain(uint64(i), copied)
 	}
 	// Publish the new table and wake up all waiters.
@@ -333,13 +329,13 @@ func (m *MapOf[K, V]) resize(table *mapTable, hint mapResizeHint) {
 	m.resizeMu.Unlock()
 }
 
-func copyBucketOf[K comparable](b *bucketPadded, destTable *mapTable, hasher func(K) uint64) (copied int) {
+func copyBucketOf[K comparable](b *bucketPadded, destTable *mapTable, seed maphash.Seed, hasher func(maphash.Seed, K) uint64) (copied int) {
 	rootb := b
 	lockBucket(&rootb.topHashMutex)
 	for {
 		for i := 0; i < entriesPerMapBucket; i++ {
 			if b.keys[i] != nil {
-				hash := hasher(derefTypedKey[K](b.keys[i]))
+				hash := hasher(seed, derefTypedKey[K](b.keys[i]))
 				bidx := bucketIdx(destTable, hash)
 				destb := &destTable.buckets[bidx]
 				appendToBucket(hash, b.keys[i], b.values[i], destb)
@@ -358,7 +354,7 @@ func copyBucketOf[K comparable](b *bucketPadded, destTable *mapTable, hasher fun
 // value if any. The loaded result reports whether the key was
 // present.
 func (m *MapOf[K, V]) LoadAndDelete(key K) (value V, loaded bool) {
-	hash := m.hasher(key)
+	hash := m.hasher(m.seed, key)
 	for {
 		hintNonEmpty := 0
 		table := (*mapTable)(atomic.LoadPointer(&m.table))
@@ -505,3 +501,13 @@ func (m *MapOf[K, V]) stats() mapStats {
 	}
 	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 64e3c9e..1e35d9f 100644
--- a/util.go
+++ b/util.go
@@ -1,8 +1,7 @@
 package xsync
 
 import (
-	"reflect"
-	"unsafe"
+	"hash/maphash"
 )
 
 // test-only assert()-like flag
@@ -16,12 +15,6 @@ const (
 	cacheLineSize = 64
 )
 
-var (
-	s1          = uint64(fastrand())
-	s2          = uint64(fastrand())
-	maphashSeed = uintptr(s1<<32 + s2)
-)
-
 // murmurhash3 64-bit finalizer
 func mixhash64ptr(v uintptr) uint64 {
 	x := uint64(v)
@@ -41,23 +34,10 @@ func mixhash64(v uint64) uint64 {
 	return v
 }
 
-// StrHash64 is the built-in string hash function.
-// It might be handy when writing a hasher function for NewTypedMapOf.
-//
-// Returned hash codes are is local to a single process and cannot
-// be recreated in a different process.
-func StrHash64(s string) uint64 {
-	if s == "" {
-		return uint64(maphashSeed)
-	}
-	strh := (*reflect.StringHeader)(unsafe.Pointer(&s))
-	return uint64(memhash(unsafe.Pointer(strh.Data), maphashSeed, uintptr(strh.Len)))
+// hashString calculates a hash of s with the given seed.
+func hashString(seed maphash.Seed, s string) uint64 {
+	var h maphash.Hash
+	h.SetSeed(seed)
+	h.WriteString(s)
+	return h.Sum64()
 }
-
-//go:noescape
-//go:linkname memhash runtime.memhash
-func memhash(p unsafe.Pointer, h, s uintptr) uintptr
-
-//go:noescape
-//go:linkname fastrand runtime.fastrand
-func fastrand() uint32


Test patch:
diff --git a/example_test.go b/example_test.go
new file mode 100644
index 0000000..a9d5457
--- /dev/null
+++ b/example_test.go
@@ -0,0 +1,32 @@
+package xsync_test
+
+import (
+	"encoding/binary"
+	"hash/maphash"
+	"time"
+
+	"github.com/puzpuzpuz/xsync"
+)
+
+func ExampleNewTypedMapOf() {
+	type Person struct {
+		GivenName   string
+		FamilyName  string
+		YearOfBirth int
+	}
+	age := xsync.NewTypedMapOf[Person, int](func(seed maphash.Seed, p Person) uint64 {
+		var h maphash.Hash
+		h.SetSeed(seed)
+		// We write field numbers, to make sure that "foo", "bar" and "foob", "ar" hash differently.
+		h.WriteByte(0)
+		h.WriteString(p.GivenName)
+		h.WriteByte(1)
+		h.WriteString(p.FamilyName)
+		h.WriteByte(2)
+		binary.Write(&h, binary.LittleEndian, p.YearOfBirth)
+		return h.Sum64()
+	})
+	Y := time.Now().Year()
+	age.Store(Person{"Ada", "Lovelace", 1815}, Y-1815)
+	age.Store(Person{"Charles", "Babbage", 1791}, Y-1791)
+}
diff --git a/mapof_test.go b/mapof_test.go
index 23f35ab..062b289 100644
--- a/mapof_test.go
+++ b/mapof_test.go
@@ -4,6 +4,8 @@
 package xsync_test
 
 import (
+	"encoding/binary"
+	"hash/maphash"
 	"math"
 	"math/rand"
 	"strconv"
@@ -285,8 +287,11 @@ func TestTypedMapOfSerialStore_StructKeys_IntValues(t *testing.T) {
 		y int
 	}
 	const numEntries = 128
-	m := NewTypedMapOf[foo, int](func(f foo) uint64 {
-		return uint64(31*f.x + f.y)
+	m := NewTypedMapOf[foo, int](func(seed maphash.Seed, f foo) uint64 {
+		var h maphash.Hash
+		h.SetSeed(seed)
+		binary.Write(&h, binary.LittleEndian, f)
+		return h.Sum64()
 	})
 	for i := 0; i < numEntries; i++ {
 		m.Store(foo{i, -i}, i)
@@ -308,8 +313,11 @@ func TestTypedMapOfSerialStore_StructKeys_StructValues(t *testing.T) {
 		y int
 	}
 	const numEntries = 128
-	m := NewTypedMapOf[foo, foo](func(f foo) uint64 {
-		return uint64(31*f.x + f.y)
+	m := NewTypedMapOf[foo, foo](func(seed maphash.Seed, f foo) uint64 {
+		var h maphash.Hash
+		h.SetSeed(seed)
+		binary.Write(&h, binary.LittleEndian, f)
+		return h.Sum64()
 	})
 	for i := 0; i < numEntries; i++ {
 		m.Store(foo{i, -i}, foo{-i, i})
@@ -330,7 +338,7 @@ func TestTypedMapOfSerialStore_StructKeys_StructValues(t *testing.T) {
 
 func TestTypedMapOfSerialStore_HashCodeCollisions(t *testing.T) {
 	const numEntries = 1000
-	m := NewTypedMapOf[int, int](func(i int) uint64 {
+	m := NewTypedMapOf[int, int](func(_ maphash.Seed, i int) uint64 {
 		// We intentionally use an awful hash function here to make sure
 		// that the map copes with key collisions.
 		return 42
@@ -423,8 +431,11 @@ func TestTypedMapOfSerialStoreThenDelete(t *testing.T) {
 		y int
 	}
 	const numEntries = 1000
-	m := NewTypedMapOf[foo, string](func(f foo) uint64 {
-		return uint64(31*f.x + f.y)
+	m := NewTypedMapOf[foo, string](func(seed maphash.Seed, f foo) uint64 {
+		var h maphash.Hash
+		h.SetSeed(seed)
+		binary.Write(&h, binary.LittleEndian, f)
+		return h.Sum64()
 	})
 	for i := 0; i < numEntries; i++ {
 		m.Store(foo{i, 42}, strconv.Itoa(i))
@@ -475,8 +486,11 @@ func TestTypedMapOfSerialStoreThenLoadAndDelete(t *testing.T) {
 		y int
 	}
 	const numEntries = 1000
-	m := NewTypedMapOf[foo, int](func(f foo) uint64 {
-		return uint64(31*f.x + f.y)
+	m := NewTypedMapOf[foo, int](func(seed maphash.Seed, f foo) uint64 {
+		var h maphash.Hash
+		h.SetSeed(seed)
+		binary.Write(&h, binary.LittleEndian, f)
+		return h.Sum64()
 	})
 	for i := 0; i < numEntries; i++ {
 		m.Store(foo{42, i}, i)