Repository: puzpuzpuz/xsync
Pull request #9 (2021-08-14 02:01:15)

feature: added support for every builtin concrete type with faster memory hash.
Map has now support for all builtin concrete types.


Patch:
diff --git a/map.go b/map.go
index 6d606de..108a114 100644
--- a/map.go
+++ b/map.go
@@ -79,11 +79,11 @@ func NewMap() *Map {
 // Load returns the value stored in the map for a key, or nil if no
 // 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 := fnv32(key)
+func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
+	hash := memhashMap(key)
 	tablep := atomic.LoadPointer(&m.table)
 	table := *(*[]bucket)(tablep)
-	b := &table[uint32(len(table)-1)&hash]
+	b := &table[uint64(len(table)-1)&hash]
 	for {
 		for i := 0; i < entriesPerMapBucket; i++ {
 			// Start atomic snapshot.
@@ -114,18 +114,18 @@ func (m *Map) Load(key string) (value interface{}, ok bool) {
 }
 
 // Store sets the value for a key.
-func (m *Map) Store(key string, value interface{}) {
+func (m *Map) Store(key interface{}, value interface{}) {
 	m.doStore(key, value, false)
 }
 
 // LoadOrStore returns the existing value for the key if present.
 // Otherwise, it stores and returns the given value.
 // The loaded result is true if the value was loaded, false if stored.
-func (m *Map) LoadOrStore(key string, value interface{}) (actual interface{}, loaded bool) {
+func (m *Map) LoadOrStore(key interface{}, value interface{}) (actual interface{}, loaded bool) {
 	return m.doStore(key, value, true)
 }
 
-func (m *Map) doStore(key string, value interface{}, loadIfExists bool) (actual interface{}, loaded bool) {
+func (m *Map) doStore(key interface{}, value interface{}, loadIfExists bool) (actual interface{}, loaded bool) {
 	if value == nil {
 		value = nilVal
 	}
@@ -136,13 +136,13 @@ func (m *Map) doStore(key string, value interface{}, loadIfExists bool) (actual
 		}
 	}
 	// Write path.
-	hash := fnv32(key)
+	hash := memhashMap(key)
 	for {
 	store_attempt:
 		var emptykp, emptyvp *unsafe.Pointer
 		tablep := atomic.LoadPointer(&m.table)
 		table := *(*[]bucket)(tablep)
-		rootb := &table[uint32(len(table)-1)&hash]
+		rootb := &table[uint64(len(table)-1)&hash]
 		b := rootb
 		chainLen := 0
 		rootb.mu.Lock()
@@ -238,8 +238,10 @@ func (m *Map) resize(tablePtr unsafe.Pointer) {
 	}
 	// Publish the new table and wake up all waiters.
 	atomic.StorePointer(&m.table, unsafe.Pointer(&newTable))
+	m.resizeMu.Lock()
 	atomic.StoreUint64(&m.resizing, 0)
 	m.resizeCond.Broadcast()
+	m.resizeMu.Unlock()
 }
 
 func copyBucket(b *bucket, table []bucket) {
@@ -249,8 +251,8 @@ func copyBucket(b *bucket, table []bucket) {
 		for i := 0; i < entriesPerMapBucket; i++ {
 			if b.keys[i] != nil {
 				k := derefKey(b.keys[i])
-				hash := fnv32(k)
-				destb := &table[uint32(len(table)-1)&hash]
+				hash := memhashMap(k)
+				destb := &table[uint64(len(table)-1)&hash]
 				appendToBucket(destb, b.keys[i], b.values[i])
 			}
 		}
@@ -285,12 +287,12 @@ func appendToBucket(b *bucket, keyPtr, valPtr unsafe.Pointer) {
 // LoadAndDelete deletes the value for a key, returning the previous
 // value if any. The loaded result reports whether the key was
 // present.
-func (m *Map) LoadAndDelete(key string) (value interface{}, loaded bool) {
-	hash := fnv32(key)
+func (m *Map) LoadAndDelete(key interface{}) (value interface{}, loaded bool) {
+	hash := memhashMap(key)
 	for {
 		tablep := atomic.LoadPointer(&m.table)
 		table := *(*[]bucket)(tablep)
-		rootb := &table[uint32(len(table)-1)&hash]
+		rootb := &table[uint64(len(table)-1)&hash]
 		b := rootb
 		rootb.mu.Lock()
 		if m.newerTableExists(tablep) {
@@ -330,7 +332,7 @@ func (m *Map) LoadAndDelete(key string) (value interface{}, loaded bool) {
 }
 
 // Delete deletes the value for a key.
-func (m *Map) Delete(key string) {
+func (m *Map) Delete(key interface{}) {
 	m.LoadAndDelete(key)
 }
 
@@ -346,7 +348,7 @@ func (m *Map) Delete(key string) {
 // It is safe to modify the map while iterating it. However, the
 // concurrent modification rule apply, i.e. the changes may be not
 // reflected in the subsequently iterated entries.
-func (m *Map) Range(f func(key string, value interface{}) bool) {
+func (m *Map) Range(f func(key interface{}, value interface{}) bool) {
 	tablep := atomic.LoadPointer(&m.table)
 	table := *(*[]bucket)(tablep)
 	bentries := make([]rangeEntry, 0, entriesPerMapBucket*(resizeMapThreshold+1))
@@ -393,8 +395,8 @@ func copyRangeEntries(bentries *[]rangeEntry, b *bucket) {
 	}
 }
 
-func derefKey(keyPtr unsafe.Pointer) string {
-	return *(*string)(keyPtr)
+func derefKey(keyPtr unsafe.Pointer) interface{} {
+	return *(*interface{})(keyPtr)
 }
 
 func derefValue(valuePtr unsafe.Pointer) interface{} {
diff --git a/util.go b/util.go
index 69164d2..0f45c31 100644
--- a/util.go
+++ b/util.go
@@ -1,13 +1,16 @@
 package xsync
 
+import (
+	"reflect"
+	"unsafe"
+)
+
 const (
 	// used in paddings to prevent false sharing;
 	// 64B are used instead of 128B as a compromise between
 	// memory footprint and performance; 128B usage may give ~30%
 	// improvement on NUMA machines
 	cacheLineSize = 64
-	fnv32Offset   = uint32(2166136261)
-	fnv32Prime    = uint32(16777619)
 )
 
 // murmurhash3 64-bit finalizer
@@ -18,13 +21,53 @@ func hash64(x uintptr) uint32 {
 	return uint32(x)
 }
 
-// FNV-1a 32-bit hash
-func fnv32(key string) uint32 {
-	hash := fnv32Offset
-	keyLength := len(key)
-	for i := 0; i < keyLength; i++ {
-		hash ^= uint32(key[i])
-		hash *= fnv32Prime
+//go:noescape
+//go:linkname memhash runtime.memhash
+func memhash(p unsafe.Pointer, h, s uintptr) uintptr
+
+func memhashMap(msg interface{}) uint64 {
+	switch val := msg.(type) {
+	case string:
+		strhv := *(*reflect.StringHeader)(unsafe.Pointer(&val))
+
+		return uint64(memhash(unsafe.Pointer(strhv.Data), 0, uintptr(strhv.Len)))
+	case []byte:
+		strhv := *(*reflect.SliceHeader)(unsafe.Pointer(&val))
+
+		return uint64(memhash(unsafe.Pointer(strhv.Data), 0, uintptr(strhv.Len)))
+	case int:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case uint:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case uintptr:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case int8:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case uint8:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case int16:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case uint16:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case int32:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case uint32:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case int64:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case uint64:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case float64:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case float32:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case bool:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case complex128:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
+	case complex64:
+		return uint64(memhash(unsafe.Pointer(&val), 0, unsafe.Sizeof(val)))
 	}
-	return hash
+
+	return uint64(memhash(unsafe.Pointer(&msg), 0, unsafe.Sizeof(msg)))
 }


Test patch:
diff --git a/map_test.go b/map_test.go
index fd47c4e..308f87d 100644
--- a/map_test.go
+++ b/map_test.go
@@ -86,8 +86,8 @@ func TestMapRange(t *testing.T) {
 		m.Store(strconv.Itoa(i), i)
 	}
 	iters := 0
-	met := make(map[string]int)
-	m.Range(func(key string, value interface{}) bool {
+	met := make(map[interface{}]int)
+	m.Range(func(key interface{}, value interface{}) bool {
 		if key != strconv.Itoa(value.(int)) {
 			t.Errorf("got unexpected key/value for iteration %d: %v/%v", iters, key, value)
 			return false
@@ -112,7 +112,7 @@ func TestMapRange_FalseReturned(t *testing.T) {
 		m.Store(strconv.Itoa(i), i)
 	}
 	iters := 0
-	m.Range(func(key string, value interface{}) bool {
+	m.Range(func(key interface{}, value interface{}) bool {
 		iters++
 		return iters != 13
 	})
@@ -127,7 +127,7 @@ func TestMapRange_NestedDelete(t *testing.T) {
 	for i := 0; i < numEntries; i++ {
 		m.Store(strconv.Itoa(i), i)
 	}
-	m.Range(func(key string, value interface{}) bool {
+	m.Range(func(key interface{}, value interface{}) bool {
 		m.Delete(key)
 		return true
 	})
@@ -147,7 +147,7 @@ func TestMapSerialStore(t *testing.T) {
 	for i := 0; i < numEntries; i++ {
 		v, ok := m.Load(strconv.Itoa(i))
 		if !ok {
-			t.Errorf("value not found for %d", i)
+			t.Errorf("value not found for %d %v", i, v)
 		}
 		if v == nil {
 			t.Errorf("nil value found for %d", i)
@@ -192,8 +192,8 @@ func TestMapSerialStoreThenLoadAndDelete(t *testing.T) {
 		m.Store(strconv.Itoa(i), i)
 	}
 	for i := 0; i < numEntries; i++ {
-		if _, loaded := m.LoadAndDelete(strconv.Itoa(i)); !loaded {
-			t.Errorf("value was not found for %d", i)
+		if v, loaded := m.LoadAndDelete(strconv.Itoa(i)); !loaded {
+			t.Errorf("value was not found for %d %v", i, v)
 		}
 		if _, ok := m.Load(strconv.Itoa(i)); ok {
 			t.Errorf("value was not expected for %d", i)
@@ -208,7 +208,7 @@ func parallelSeqStorer(t *testing.T, m *Map, storeEach, numIters, numEntries int
 			// Due to atomic snapshots we must see a "<j>"/j pair.
 			v, ok := m.Load(strconv.Itoa(j))
 			if !ok {
-				t.Errorf("value was not found for %d", j)
+				t.Errorf("value was not found for %d %v", j, v)
 				break
 			}
 			if vi, ok := v.(int); !ok || vi != j {
@@ -237,7 +237,7 @@ func TestMapParallelStores(t *testing.T) {
 	for i := 0; i < numEntries; i++ {
 		v, ok := m.Load(strconv.Itoa(i))
 		if !ok {
-			t.Fatalf("value not found for %d", i)
+			t.Fatalf("value not found for %d %v", i, v)
 		}
 		if v == nil {
 			t.Fatalf("nil value found for %d", i)
@@ -404,7 +404,7 @@ func BenchmarkMapRange(b *testing.B) {
 	b.RunParallel(func(pb *testing.PB) {
 		foo := 0
 		for pb.Next() {
-			m.Range(func(key string, value interface{}) bool {
+			m.Range(func(key interface{}, value interface{}) bool {
 				foo++
 				return true
 			})