Repository: puzpuzpuz/xsync
Pull request #134 (2024-06-29 18:29:58)

WIP better MapOf
Introduces meta memory and SWAR-based lookups similar to C++'s `absl::flat_hash_map` hash table (https://abseil.io/docs/cpp/guides/container).
    
Also, reduces `MapOf`'s memory overhead: each bucket now holds up to 5 entries instead of 3.

### Microbenchmarks

A few benchmark results were collected on a laptop with i7-1185G7 and 32GB RAM running Ubuntu 22.04.

Before:
```
BenchmarkMapOfInt_WarmUp/reads=100%-8         	303130814	         4.131 ns/op	 242101267 ops/s	       0 B/op	       0 allocs/op
BenchmarkMapOfInt_WarmUp/reads=99%-8          	232482326	         5.196 ns/op	 192442573 ops/s	       0 B/op	       0 allocs/op
BenchmarkMapOfInt_WarmUp/reads=90%-8          	180387648	         6.811 ns/op	 146829029 ops/s	       0 B/op	       0 allocs/op
BenchmarkMapOfInt_WarmUp/reads=75%-8          	129619245	         9.547 ns/op	 104748466 ops/s	       2 B/op	       0 allocs/op

BenchmarkMapOf_WarmUp/reads=100%-8         	196852258	         6.756 ns/op	 148014399 ops/s	       0 B/op	       0 allocs/op
BenchmarkMapOf_WarmUp/reads=99%-8          	190997551	         6.376 ns/op	 156831274 ops/s	       0 B/op	       0 allocs/op
BenchmarkMapOf_WarmUp/reads=90%-8          	152631080	         8.038 ns/op	 124410942 ops/s	       1 B/op	       0 allocs/op
BenchmarkMapOf_WarmUp/reads=75%-8          	100000000	        11.50 ns/op	  86919108 ops/s	       2 B/op	       0 allocs/op
```

After:
```
BenchmarkMapOfInt_WarmUp/reads=100%-8         	431616265	         2.747 ns/op	 364040402 ops/s	       0 B/op	       0 allocs/op
BenchmarkMapOfInt_WarmUp/reads=99%-8          	320536114	         3.772 ns/op	 265102717 ops/s	       0 B/op	       0 allocs/op
BenchmarkMapOfInt_WarmUp/reads=90%-8          	219056338	         5.281 ns/op	 189374821 ops/s	       0 B/op	       0 allocs/op
BenchmarkMapOfInt_WarmUp/reads=75%-8          	149422306	         7.418 ns/op	 134801273 ops/s	       1 B/op	       0 allocs/op

BenchmarkMapOf_WarmUp/reads=100%-8         	239793300	         4.923 ns/op	 203117147 ops/s	       0 B/op	       0 allocs/op
BenchmarkMapOf_WarmUp/reads=99%-8          	247627736	         4.855 ns/op	 205985869 ops/s	       0 B/op	       0 allocs/op
BenchmarkMapOf_WarmUp/reads=90%-8          	191962411	         6.405 ns/op	 156134268 ops/s	       1 B/op	       0 allocs/op
BenchmarkMapOf_WarmUp/reads=75%-8          	134295975	         9.007 ns/op	 111028357 ops/s	       3 B/op	       0 allocs/op
```


Patch:
diff --git a/BENCHMARKS.md b/BENCHMARKS.md
index af72721..aaa72fa 100644
--- a/BENCHMARKS.md
+++ b/BENCHMARKS.md
@@ -12,6 +12,8 @@ $ benchstat bench.txt | tee benchstat.txt
 
 The below sections contain some of the results. Refer to [this gist](https://gist.github.com/puzpuzpuz/e62e38e06feadecfdc823c0f941ece0b) for the complete output.
 
+Please note that `MapOf` got a number of optimizations since v2.3.1, so the current result is likely to be different.
+
 ### Counter vs. atomic int64
 
 ```
diff --git a/README.md b/README.md
index cc86342..68f7a69 100644
--- a/README.md
+++ b/README.md
@@ -66,7 +66,9 @@ m.Store("foo", "bar")
 v, ok := m.Load("foo")
 ```
 
-One important difference with `Map` is that `MapOf` supports arbitrary `comparable` key types:
+Apart from CLHT, `MapOf` borrows ideas from Java's `j.u.c.ConcurrentHashMap` (immutable K/V pair structs instead of atomic snapshots) and C++'s `absl::flat_hash_map` (meta memory and SWAR-based lookups). It also has more dense memory layout when compared with `Map`. Long story short, `MapOf` should be preferred over `Map` when possible.
+
+An important difference with `Map` is that `MapOf` supports arbitrary `comparable` key types:
 
 ```go
 type Point struct {
diff --git a/map.go b/map.go
index 13360fc..8e98c1e 100644
--- a/map.go
+++ b/map.go
@@ -19,7 +19,7 @@ const (
 )
 
 const (
-	// number of entries per bucket; 3 entries lead to size of 64B
+	// number of Map entries per bucket; 3 entries lead to size of 64B
 	// (one cache line) on 64-bit machines
 	entriesPerMapBucket = 3
 	// threshold fraction of table occupation to start a table shrinking
@@ -477,7 +477,7 @@ func (m *Map) doCompute(
 					unlockBucket(&rootb.topHashMutex)
 					return newValue, false
 				}
-				// Create and append the bucket.
+				// Create and append a bucket.
 				newb := new(bucketPadded)
 				newb.keys[0] = unsafe.Pointer(&key)
 				newb.values[0] = unsafe.Pointer(&newValue)
diff --git a/mapof.go b/mapof.go
index 13737b7..9b8737c 100644
--- a/mapof.go
+++ b/mapof.go
@@ -8,6 +8,16 @@ import (
 	"unsafe"
 )
 
+const (
+	// number of MapOf entries per bucket; 5 entries lead to size of 64B
+	// (one cache line) on 64-bit machines
+	entriesPerMapOfBucket        = 5
+	defaultMeta           uint64 = 0x8080808080808080
+	metaMask              uint64 = 0xffffffffff
+	defaultMetaMasked     uint64 = defaultMeta & metaMask
+	emptyMetaSlot         uint8  = 0x80
+)
+
 // MapOf is like a Go map[K]V but is safe for concurrent
 // use by multiple goroutines without additional locking or
 // coordination. It follows the interface of sync.Map with
@@ -24,6 +34,11 @@ import (
 // Also, Get operations involve no write to memory, as well as no
 // mutexes or any other sort of locks. Due to this design, in all
 // considered scenarios MapOf outperforms sync.Map.
+//
+// MapOf also borrows ideas from Java's j.u.c.ConcurrentHashMap
+// (immutable K/V pair structs instead of atomic snapshots)
+// and C++'s absl::flat_hash_map (meta memory and SWAR-based
+// lookups).
 type MapOf[K comparable, V any] struct {
 	totalGrowths int64
 	totalShrinks int64
@@ -46,7 +61,7 @@ type mapOfTable[K comparable, V any] struct {
 }
 
 // bucketOfPadded is a CL-sized map bucket holding up to
-// entriesPerMapBucket entries.
+// entriesPerMapOfBucket entries.
 type bucketOfPadded struct {
 	//lint:ignore U1000 ensure each bucket takes two cache lines on both 32 and 64-bit archs
 	pad [cacheLineSize - unsafe.Sizeof(bucketOf{})]byte
@@ -54,9 +69,9 @@ type bucketOfPadded struct {
 }
 
 type bucketOf struct {
-	hashes  [entriesPerMapBucket]uint64
-	entries [entriesPerMapBucket]unsafe.Pointer // *entryOf
-	next    unsafe.Pointer                      // *bucketOfPadded
+	meta    uint64
+	entries [entriesPerMapOfBucket]unsafe.Pointer // *entryOf
+	next    unsafe.Pointer                        // *bucketOfPadded
 	mu      sync.Mutex
 }
 
@@ -88,7 +103,7 @@ func newMapOf[K comparable, V any](
 	options ...func(*MapConfig),
 ) *MapOf[K, V] {
 	c := &MapConfig{
-		sizeHint: defaultMinMapTableLen * entriesPerMapBucket,
+		sizeHint: defaultMinMapTableLen * entriesPerMapOfBucket,
 	}
 	for _, o := range options {
 		o(c)
@@ -98,10 +113,10 @@ func newMapOf[K comparable, V any](
 	m.resizeCond = *sync.NewCond(&m.resizeMu)
 	m.hasher = hasher
 	var table *mapOfTable[K, V]
-	if c.sizeHint <= defaultMinMapTableLen*entriesPerMapBucket {
+	if c.sizeHint <= defaultMinMapTableLen*entriesPerMapOfBucket {
 		table = newMapOfTable[K, V](defaultMinMapTableLen)
 	} else {
-		tableLen := nextPowOf2(uint32(c.sizeHint / entriesPerMapBucket))
+		tableLen := nextPowOf2(uint32(c.sizeHint / entriesPerMapOfBucket))
 		table = newMapOfTable[K, V](int(tableLen))
 	}
 	m.minTableLen = len(table.buckets)
@@ -112,6 +127,9 @@ func newMapOf[K comparable, V any](
 
 func newMapOfTable[K comparable, V any](minTableLen int) *mapOfTable[K, V] {
 	buckets := make([]bucketOfPadded, minTableLen)
+	for i := range buckets {
+		buckets[i].meta = defaultMeta
+	}
 	counterLen := minTableLen >> 10
 	if counterLen < minMapCounterLen {
 		counterLen = minMapCounterLen
@@ -132,25 +150,24 @@ func newMapOfTable[K comparable, V any](minTableLen int) *mapOfTable[K, V] {
 // The ok result indicates whether value was found in the map.
 func (m *MapOf[K, V]) Load(key K) (value V, ok bool) {
 	table := (*mapOfTable[K, V])(atomic.LoadPointer(&m.table))
-	hash := shiftHash(m.hasher(key, table.seed))
-	bidx := uint64(len(table.buckets)-1) & hash
+	hash := m.hasher(key, table.seed)
+	h1 := h1(hash)
+	h2w := broadcast(h2(hash))
+	bidx := uint64(len(table.buckets)-1) & h1
 	b := &table.buckets[bidx]
 	for {
-		for i := 0; i < entriesPerMapBucket; i++ {
-			// We treat the hash code only as a hint, so there is no
-			// need to get an atomic snapshot.
-			h := atomic.LoadUint64(&b.hashes[i])
-			if h == uint64(0) || h != hash {
-				continue
-			}
-			eptr := atomic.LoadPointer(&b.entries[i])
-			if eptr == nil {
-				continue
-			}
-			e := (*entryOf[K, V])(eptr)
-			if e.key == key {
-				return e.value, true
+		metaw := atomic.LoadUint64(&b.meta)
+		markedw := markZeroBytes(metaw^h2w) & metaMask
+		for markedw != 0 {
+			idx := firstMarkedByteIndex(markedw)
+			eptr := atomic.LoadPointer(&b.entries[idx])
+			if eptr != nil {
+				e := (*entryOf[K, V])(eptr)
+				if e.key == key {
+					return e.value, true
+				}
 			}
+			markedw &= markedw - 1
 		}
 		bptr := atomic.LoadPointer(&b.next)
 		if bptr == nil {
@@ -282,14 +299,16 @@ func (m *MapOf[K, V]) doCompute(
 	for {
 	compute_attempt:
 		var (
-			emptyb       *bucketOfPadded
-			emptyidx     int
-			hintNonEmpty int
+			emptyb   *bucketOfPadded
+			emptyidx int
 		)
 		table := (*mapOfTable[K, V])(atomic.LoadPointer(&m.table))
 		tableLen := len(table.buckets)
-		hash := shiftHash(m.hasher(key, table.seed))
-		bidx := uint64(len(table.buckets)-1) & hash
+		hash := m.hasher(key, table.seed)
+		h1 := h1(hash)
+		h2 := h2(hash)
+		h2w := broadcast(h2)
+		bidx := uint64(len(table.buckets)-1) & h1
 		rootb := &table.buckets[bidx]
 		rootb.mu.Lock()
 		// The following two checks must go in reverse to what's
@@ -307,62 +326,62 @@ func (m *MapOf[K, V]) doCompute(
 		}
 		b := rootb
 		for {
-			for i := 0; i < entriesPerMapBucket; i++ {
-				h := atomic.LoadUint64(&b.hashes[i])
-				if h == uint64(0) {
-					if emptyb == nil {
-						emptyb = b
-						emptyidx = i
-					}
-					continue
-				}
-				if h != hash {
-					hintNonEmpty++
-					continue
-				}
-				e := (*entryOf[K, V])(b.entries[i])
-				if e.key == key {
-					if loadIfExists {
-						rootb.mu.Unlock()
-						return e.value, !computeOnly
-					}
-					// In-place update/delete.
-					// We get a copy of the value via an interface{} on each call,
-					// thus the live value pointers are unique. Otherwise atomic
-					// snapshot won't be correct in case of multiple Store calls
-					// using the same value.
-					oldv := e.value
-					newv, del := valueFn(oldv, true)
-					if del {
-						// Deletion.
-						// First we update the hash, then the entry.
-						atomic.StoreUint64(&b.hashes[i], uint64(0))
-						atomic.StorePointer(&b.entries[i], nil)
-						leftEmpty := false
-						if hintNonEmpty == 0 {
-							leftEmpty = isEmptyBucketOf(b)
+			metaw := b.meta
+			markedw := markZeroBytes(metaw^h2w) & metaMask
+			for markedw != 0 {
+				idx := firstMarkedByteIndex(markedw)
+				eptr := b.entries[idx]
+				if eptr != nil {
+					e := (*entryOf[K, V])(eptr)
+					if e.key == key {
+						if loadIfExists {
+							rootb.mu.Unlock()
+							return e.value, !computeOnly
 						}
+						// In-place update/delete.
+						// We get a copy of the value via an interface{} on each call,
+						// thus the live value pointers are unique. Otherwise atomic
+						// snapshot won't be correct in case of multiple Store calls
+						// using the same value.
+						oldv := e.value
+						newv, del := valueFn(oldv, true)
+						if del {
+							// Deletion.
+							// First we update the hash, then the entry.
+							newmetaw := setByte(metaw, emptyMetaSlot, idx)
+							atomic.StoreUint64(&b.meta, newmetaw)
+							atomic.StorePointer(&b.entries[idx], nil)
+							rootb.mu.Unlock()
+							table.addSize(bidx, -1)
+							// Might need to shrink the table if we left bucket empty.
+							if newmetaw == defaultMeta {
+								m.resize(table, mapShrinkHint)
+							}
+							return oldv, !computeOnly
+						}
+						newe := new(entryOf[K, V])
+						newe.key = key
+						newe.value = newv
+						atomic.StorePointer(&b.entries[idx], unsafe.Pointer(newe))
 						rootb.mu.Unlock()
-						table.addSize(bidx, -1)
-						// Might need to shrink the table.
-						if leftEmpty {
-							m.resize(table, mapShrinkHint)
+						if computeOnly {
+							// Compute expects the new value to be returned.
+							return newv, true
 						}
-						return oldv, !computeOnly
-					}
-					newe := new(entryOf[K, V])
-					newe.key = key
-					newe.value = newv
-					atomic.StorePointer(&b.entries[i], unsafe.Pointer(newe))
-					rootb.mu.Unlock()
-					if computeOnly {
-						// Compute expects the new value to be returned.
-						return newv, true
+						// LoadAndStore expects the old value to be returned.
+						return oldv, true
 					}
-					// LoadAndStore expects the old value to be returned.
-					return oldv, true
 				}
-				hintNonEmpty++
+				markedw &= markedw - 1
+			}
+			if emptyb == nil {
+				// Search for empty entries (up to 5 per bucket).
+				emptyw := metaw & defaultMetaMasked
+				if emptyw != 0 {
+					idx := firstMarkedByteIndex(emptyw)
+					emptyb = b
+					emptyidx = idx
+				}
 			}
 			if b.next == nil {
 				if emptyb != nil {
@@ -376,14 +395,14 @@ func (m *MapOf[K, V]) doCompute(
 					newe := new(entryOf[K, V])
 					newe.key = key
 					newe.value = newValue
-					// First we update the hash, then the entry.
-					atomic.StoreUint64(&emptyb.hashes[emptyidx], hash)
+					// First we update meta, then the entry.
+					atomic.StoreUint64(&emptyb.meta, setByte(emptyb.meta, h2, emptyidx))
 					atomic.StorePointer(&emptyb.entries[emptyidx], unsafe.Pointer(newe))
 					rootb.mu.Unlock()
 					table.addSize(bidx, 1)
 					return newValue, computeOnly
 				}
-				growThreshold := float64(tableLen) * entriesPerMapBucket * mapLoadFactor
+				growThreshold := float64(tableLen) * entriesPerMapOfBucket * mapLoadFactor
 				if table.sumSize() > int64(growThreshold) {
 					// Need to grow the table. Then go for another attempt.
 					rootb.mu.Unlock()
@@ -397,9 +416,9 @@ func (m *MapOf[K, V]) doCompute(
 					rootb.mu.Unlock()
 					return newValue, false
 				}
-				// Create and append the bucket.
+				// Create and append a bucket.
 				newb := new(bucketOfPadded)
-				newb.hashes[0] = hash
+				newb.meta = setByte(defaultMeta, h2, 0)
 				newe := new(entryOf[K, V])
 				newe.key = key
 				newe.value = newValue
@@ -437,7 +456,7 @@ func (m *MapOf[K, V]) resize(knownTable *mapOfTable[K, V], hint mapResizeHint) {
 	if hint == mapShrinkHint {
 		if m.growOnly ||
 			m.minTableLen == knownTableLen ||
-			knownTable.sumSize() > int64((knownTableLen*entriesPerMapBucket)/mapShrinkFraction) {
+			knownTable.sumSize() > int64((knownTableLen*entriesPerMapOfBucket)/mapShrinkFraction) {
 			return
 		}
 	}
@@ -456,7 +475,7 @@ func (m *MapOf[K, V]) resize(knownTable *mapOfTable[K, V], hint mapResizeHint) {
 		atomic.AddInt64(&m.totalGrowths, 1)
 		newTable = newMapOfTable[K, V](tableLen << 1)
 	case mapShrinkHint:
-		shrinkThreshold := int64((tableLen * entriesPerMapBucket) / mapShrinkFraction)
+		shrinkThreshold := int64((tableLen * entriesPerMapOfBucket) / mapShrinkFraction)
 		if tableLen > m.minTableLen && table.sumSize() <= shrinkThreshold {
 			// Shrink the table with factor of 2.
 			atomic.AddInt64(&m.totalShrinks, 1)
@@ -497,13 +516,13 @@ func copyBucketOf[K comparable, V any](
 	rootb := b
 	rootb.mu.Lock()
 	for {
-		for i := 0; i < entriesPerMapBucket; i++ {
+		for i := 0; i < entriesPerMapOfBucket; i++ {
 			if b.entries[i] != nil {
 				e := (*entryOf[K, V])(b.entries[i])
-				hash := shiftHash(hasher(e.key, destTable.seed))
-				bidx := uint64(len(destTable.buckets)-1) & hash
+				hash := hasher(e.key, destTable.seed)
+				bidx := uint64(len(destTable.buckets)-1) & h1(hash)
 				destb := &destTable.buckets[bidx]
-				appendToBucketOf(hash, b.entries[i], destb)
+				appendToBucketOf(h2(hash), b.entries[i], destb)
 				copied++
 			}
 		}
@@ -531,7 +550,7 @@ func copyBucketOf[K comparable, V any](
 func (m *MapOf[K, V]) Range(f func(key K, value V) bool) {
 	var zeroPtr unsafe.Pointer
 	// Pre-allocate array big enough to fit entries for most hash tables.
-	bentries := make([]unsafe.Pointer, 0, 16*entriesPerMapBucket)
+	bentries := make([]unsafe.Pointer, 0, 16*entriesPerMapOfBucket)
 	tablep := atomic.LoadPointer(&m.table)
 	table := *(*mapOfTable[K, V])(tablep)
 	for i := range table.buckets {
@@ -541,7 +560,7 @@ func (m *MapOf[K, V]) Range(f func(key K, value V) bool) {
 		// the intermediate slice.
 		rootb.mu.Lock()
 		for {
-			for i := 0; i < entriesPerMapBucket; i++ {
+			for i := 0; i < entriesPerMapOfBucket; i++ {
 				if b.entries[i] != nil {
 					bentries = append(bentries, b.entries[i])
 				}
@@ -578,18 +597,18 @@ func (m *MapOf[K, V]) Size() int {
 	return int(table.sumSize())
 }
 
-func appendToBucketOf(hash uint64, entryPtr unsafe.Pointer, b *bucketOfPadded) {
+func appendToBucketOf(h2 uint8, entryPtr unsafe.Pointer, b *bucketOfPadded) {
 	for {
-		for i := 0; i < entriesPerMapBucket; i++ {
+		for i := 0; i < entriesPerMapOfBucket; i++ {
 			if b.entries[i] == nil {
-				b.hashes[i] = hash
+				b.meta = setByte(b.meta, h2, i)
 				b.entries[i] = entryPtr
 				return
 			}
 		}
 		if b.next == nil {
 			newb := new(bucketOfPadded)
-			newb.hashes[0] = hash
+			newb.meta = setByte(defaultMeta, h2, 0)
 			newb.entries[0] = entryPtr
 			b.next = unsafe.Pointer(newb)
 			return
@@ -598,21 +617,6 @@ func appendToBucketOf(hash uint64, entryPtr unsafe.Pointer, b *bucketOfPadded) {
 	}
 }
 
-func isEmptyBucketOf(rootb *bucketOfPadded) bool {
-	b := rootb
-	for {
-		for i := 0; i < entriesPerMapBucket; i++ {
-			if b.entries[i] != nil {
-				return false
-			}
-		}
-		if b.next == nil {
-			return true
-		}
-		b = (*bucketOfPadded)(b.next)
-	}
-}
-
 func (table *mapOfTable[K, V]) addSize(bucketIdx uint64, delta int) {
 	cidx := uint64(len(table.size)-1) & bucketIdx
 	atomic.AddInt64(&table.size[cidx].c, int64(delta))
@@ -631,12 +635,12 @@ func (table *mapOfTable[K, V]) sumSize() int64 {
 	return sum
 }
 
-func shiftHash(h uint64) uint64 {
-	// uint64(0) is a reserved value which stands for an empty slot.
-	if h == uint64(0) {
-		return uint64(1)
-	}
-	return h
+func h1(h uint64) uint64 {
+	return h >> 7
+}
+
+func h2(h uint64) uint8 {
+	return uint8(h & 0x7f)
 }
 
 // Stats returns statistics for the MapOf. Just like other map
@@ -658,8 +662,8 @@ func (m *MapOf[K, V]) Stats() MapStats {
 		stats.TotalBuckets++
 		for {
 			nentriesLocal := 0
-			stats.Capacity += entriesPerMapBucket
-			for i := 0; i < entriesPerMapBucket; i++ {
+			stats.Capacity += entriesPerMapOfBucket
+			for i := 0; i < entriesPerMapOfBucket; i++ {
 				if atomic.LoadPointer(&b.entries[i]) != nil {
 					stats.Size++
 					nentriesLocal++
diff --git a/util.go b/util.go
index 7368912..7692708 100644
--- a/util.go
+++ b/util.go
@@ -1,6 +1,7 @@
 package xsync
 
 import (
+	"math/bits"
 	"runtime"
 	_ "unsafe"
 )
@@ -44,3 +45,22 @@ func parallelism() uint32 {
 //go:noescape
 //go:linkname runtime_fastrand runtime.fastrand
 func runtime_fastrand() uint32
+
+func broadcast(b uint8) uint64 {
+	return 0x101010101010101 * uint64(b)
+}
+
+func firstMarkedByteIndex(w uint64) int {
+	return bits.TrailingZeros64(w) >> 3
+}
+
+// SWAR byte search: may produce false positives, e.g. for 0x0100,
+// so make sure to double-check bytes found by this function.
+func markZeroBytes(w uint64) uint64 {
+	return ((w - 0x0101010101010101) & (^w) & 0x8080808080808080)
+}
+
+func setByte(w uint64, b uint8, idx int) uint64 {
+	shift := idx << 3
+	return (w &^ (0xff << shift)) | (uint64(b) << shift)
+}


Test patch:
diff --git a/export_test.go b/export_test.go
index e0abb64..728a06b 100644
--- a/export_test.go
+++ b/export_test.go
@@ -1,11 +1,13 @@
 package xsync
 
 const (
-	EntriesPerMapBucket   = entriesPerMapBucket
-	MapLoadFactor         = mapLoadFactor
-	DefaultMinMapTableLen = defaultMinMapTableLen
-	DefaultMinMapTableCap = defaultMinMapTableLen * entriesPerMapBucket
-	MaxMapCounterLen      = maxMapCounterLen
+	EntriesPerMapBucket     = entriesPerMapBucket
+	EntriesPerMapOfBucket   = entriesPerMapOfBucket
+	MapLoadFactor           = mapLoadFactor
+	DefaultMinMapTableLen   = defaultMinMapTableLen
+	DefaultMinMapTableCap   = defaultMinMapTableLen * entriesPerMapBucket
+	DefaultMinMapOfTableCap = defaultMinMapTableLen * entriesPerMapOfBucket
+	MaxMapCounterLen        = maxMapCounterLen
 )
 
 type (
@@ -45,6 +47,22 @@ func Fastrand() uint32 {
 	return runtime_fastrand()
 }
 
+func Broadcast(b uint8) uint64 {
+	return broadcast(b)
+}
+
+func FirstMarkedByteIndex(w uint64) int {
+	return firstMarkedByteIndex(w)
+}
+
+func MarkZeroBytes(w uint64) uint64 {
+	return markZeroBytes(w)
+}
+
+func SetByte(w uint64, b uint8, idx int) uint64 {
+	return setByte(w, b, idx)
+}
+
 func NextPowOf2(v uint32) uint32 {
 	return nextPowOf2(v)
 }
diff --git a/mapof_test.go b/mapof_test.go
index 69bd886..849841a 100644
--- a/mapof_test.go
+++ b/mapof_test.go
@@ -618,22 +618,22 @@ func assertMapOfCapacity[K comparable, V any](t *testing.T, m *MapOf[K, V], expe
 }
 
 func TestNewMapOfPresized(t *testing.T) {
-	assertMapOfCapacity(t, NewMapOf[string, string](), DefaultMinMapTableCap)
-	assertMapOfCapacity(t, NewMapOfPresized[string, string](0), DefaultMinMapTableCap)
-	assertMapOfCapacity(t, NewMapOf[string, string](WithPresize(0)), DefaultMinMapTableCap)
-	assertMapOfCapacity(t, NewMapOfPresized[string, string](-100), DefaultMinMapTableCap)
-	assertMapOfCapacity(t, NewMapOf[string, string](WithPresize(-100)), DefaultMinMapTableCap)
-	assertMapOfCapacity(t, NewMapOfPresized[string, string](500), 768)
-	assertMapOfCapacity(t, NewMapOf[string, string](WithPresize(500)), 768)
-	assertMapOfCapacity(t, NewMapOfPresized[int, int](1_000_000), 1_572_864)
-	assertMapOfCapacity(t, NewMapOf[int, int](WithPresize(1_000_000)), 1_572_864)
-	assertMapOfCapacity(t, NewMapOfPresized[point, point](100), 192)
-	assertMapOfCapacity(t, NewMapOf[point, point](WithPresize(100)), 192)
+	assertMapOfCapacity(t, NewMapOf[string, string](), DefaultMinMapOfTableCap)
+	assertMapOfCapacity(t, NewMapOfPresized[string, string](0), DefaultMinMapOfTableCap)
+	assertMapOfCapacity(t, NewMapOf[string, string](WithPresize(0)), DefaultMinMapOfTableCap)
+	assertMapOfCapacity(t, NewMapOfPresized[string, string](-100), DefaultMinMapOfTableCap)
+	assertMapOfCapacity(t, NewMapOf[string, string](WithPresize(-100)), DefaultMinMapOfTableCap)
+	assertMapOfCapacity(t, NewMapOfPresized[string, string](500), 640)
+	assertMapOfCapacity(t, NewMapOf[string, string](WithPresize(500)), 640)
+	assertMapOfCapacity(t, NewMapOfPresized[int, int](1_000_000), 1_310_720)
+	assertMapOfCapacity(t, NewMapOf[int, int](WithPresize(1_000_000)), 1_310_720)
+	assertMapOfCapacity(t, NewMapOfPresized[point, point](100), 160)
+	assertMapOfCapacity(t, NewMapOf[point, point](WithPresize(100)), 160)
 }
 
 func TestNewMapOfPresized_DoesNotShrinkBelowMinTableLen(t *testing.T) {
 	const minTableLen = 1024
-	const numEntries = minTableLen * EntriesPerMapBucket
+	const numEntries = minTableLen * EntriesPerMapOfBucket
 	m := NewMapOf[int, int](WithPresize(numEntries))
 	for i := 0; i < numEntries; i++ {
 		m.Store(i, i)
@@ -656,7 +656,7 @@ func TestNewMapOfPresized_DoesNotShrinkBelowMinTableLen(t *testing.T) {
 
 func TestNewMapOfGrowOnly_OnlyShrinksOnClear(t *testing.T) {
 	const minTableLen = 128
-	const numEntries = minTableLen * EntriesPerMapBucket
+	const numEntries = minTableLen * EntriesPerMapOfBucket
 	m := NewMapOf[int, int](WithPresize(numEntries), WithGrowOnly())
 
 	stats := m.Stats()
@@ -697,7 +697,7 @@ 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.RootBuckets * EntriesPerMapBucket
+	expectedCapacity := int(math.RoundToEven(MapLoadFactor+1)) * stats.RootBuckets * EntriesPerMapOfBucket
 	if stats.Capacity > expectedCapacity {
 		t.Fatalf("capacity was too large: %d, expected: %d", stats.Capacity, expectedCapacity)
 	}
@@ -721,7 +721,7 @@ func TestMapOfResize(t *testing.T) {
 	if stats.Size > 0 {
 		t.Fatalf("zero size was expected: %d", stats.Size)
 	}
-	expectedCapacity = stats.RootBuckets * EntriesPerMapBucket
+	expectedCapacity = stats.RootBuckets * EntriesPerMapOfBucket
 	if stats.Capacity != expectedCapacity {
 		t.Fatalf("capacity was too large: %d, expected: %d", stats.Capacity, expectedCapacity)
 	}
@@ -803,7 +803,7 @@ func parallelRandTypedResizer(t *testing.T, m *MapOf[string, int], numIters, num
 
 func TestMapOfParallelResize(t *testing.T) {
 	const numIters = 1_000
-	const numEntries = 2 * EntriesPerMapBucket * DefaultMinMapTableLen
+	const numEntries = 2 * EntriesPerMapOfBucket * DefaultMinMapTableLen
 	m := NewMapOf[string, int]()
 	cdone := make(chan bool)
 	go parallelRandTypedResizer(t, m, numIters, numEntries, cdone)
@@ -1140,7 +1140,7 @@ func TestMapOfStats(t *testing.T) {
 	if stats.EmptyBuckets != stats.RootBuckets {
 		t.Fatalf("unexpected number of empty buckets: %d", stats.EmptyBuckets)
 	}
-	if stats.Capacity != EntriesPerMapBucket*DefaultMinMapTableLen {
+	if stats.Capacity != EntriesPerMapOfBucket*DefaultMinMapTableLen {
 		t.Fatalf("unexpected capacity: %d", stats.Capacity)
 	}
 	if stats.Size != 0 {
@@ -1153,7 +1153,7 @@ func TestMapOfStats(t *testing.T) {
 		t.Fatalf("unexpected counter length: %d", stats.CounterLen)
 	}
 
-	for i := 0; i < 100; i++ {
+	for i := 0; i < 200; i++ {
 		m.Store(i, i)
 	}
 
@@ -1167,13 +1167,13 @@ func TestMapOfStats(t *testing.T) {
 	if stats.EmptyBuckets >= stats.RootBuckets {
 		t.Fatalf("unexpected number of empty buckets: %d", stats.EmptyBuckets)
 	}
-	if stats.Capacity < 2*EntriesPerMapBucket*DefaultMinMapTableLen {
+	if stats.Capacity < 2*EntriesPerMapOfBucket*DefaultMinMapTableLen {
 		t.Fatalf("unexpected capacity: %d", stats.Capacity)
 	}
-	if stats.Size != 100 {
+	if stats.Size != 200 {
 		t.Fatalf("unexpected size: %d", stats.Size)
 	}
-	if stats.Counter != 100 {
+	if stats.Counter != 200 {
 		t.Fatalf("unexpected counter: %d", stats.Counter)
 	}
 	if stats.CounterLen != 8 {
diff --git a/util_test.go b/util_test.go
index 8a07f00..3f7af94 100644
--- a/util_test.go
+++ b/util_test.go
@@ -2,6 +2,7 @@ package xsync_test
 
 import (
 	"math/rand"
+	"strconv"
 	"testing"
 
 	. "github.com/puzpuzpuz/xsync/v3"
@@ -38,6 +39,235 @@ func TestFastrand(t *testing.T) {
 	}
 }
 
+func TestBroadcast(t *testing.T) {
+	testCases := []struct {
+		input    uint8
+		expected uint64
+	}{
+		{
+			input:    0,
+			expected: 0,
+		},
+		{
+			input:    1,
+			expected: 0x0101010101010101,
+		},
+		{
+			input:    2,
+			expected: 0x0202020202020202,
+		},
+		{
+			input:    42,
+			expected: 0x2a2a2a2a2a2a2a2a,
+		},
+		{
+			input:    127,
+			expected: 0x7f7f7f7f7f7f7f7f,
+		},
+		{
+			input:    255,
+			expected: 0xffffffffffffffff,
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(strconv.Itoa(int(tc.input)), func(t *testing.T) {
+			if Broadcast(tc.input) != tc.expected {
+				t.Errorf("unexpected result: %x", Broadcast(tc.input))
+			}
+		})
+	}
+}
+
+func TestFirstMarkedByteIndex(t *testing.T) {
+	testCases := []struct {
+		input    uint64
+		expected int
+	}{
+		{
+			input:    0,
+			expected: 8,
+		},
+		{
+			input:    0x8080808080808080,
+			expected: 0,
+		},
+		{
+			input:    0x0000000000000080,
+			expected: 0,
+		},
+		{
+			input:    0x0000000000008000,
+			expected: 1,
+		},
+		{
+			input:    0x0000000000800000,
+			expected: 2,
+		},
+		{
+			input:    0x0000000080000000,
+			expected: 3,
+		},
+		{
+			input:    0x0000008000000000,
+			expected: 4,
+		},
+		{
+			input:    0x0000800000000000,
+			expected: 5,
+		},
+		{
+			input:    0x0080000000000000,
+			expected: 6,
+		},
+		{
+			input:    0x8000000000000000,
+			expected: 7,
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(strconv.Itoa(int(tc.input)), func(t *testing.T) {
+			if FirstMarkedByteIndex(tc.input) != tc.expected {
+				t.Errorf("unexpected result: %x", FirstMarkedByteIndex(tc.input))
+			}
+		})
+	}
+}
+
+func TestMarkZeroBytes(t *testing.T) {
+	testCases := []struct {
+		input    uint64
+		expected uint64
+	}{
+		{
+			input:    0xffffffffffffffff,
+			expected: 0,
+		},
+		{
+			input:    0,
+			expected: 0x8080808080808080,
+		},
+		{
+			input:    1,
+			expected: 0x8080808080808000,
+		},
+		{
+			input:    1 << 9,
+			expected: 0x8080808080800080,
+		},
+		{
+			input:    1 << 17,
+			expected: 0x8080808080008080,
+		},
+		{
+			input:    1 << 25,
+			expected: 0x8080808000808080,
+		},
+		{
+			input:    1 << 33,
+			expected: 0x8080800080808080,
+		},
+		{
+			input:    1 << 41,
+			expected: 0x8080008080808080,
+		},
+		{
+			input:    1 << 49,
+			expected: 0x8000808080808080,
+		},
+		{
+			input:    1 << 57,
+			expected: 0x0080808080808080,
+		},
+		// false positive
+		{
+			input:    0x0100,
+			expected: 0x8080808080808080,
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(strconv.Itoa(int(tc.input)), func(t *testing.T) {
+			if MarkZeroBytes(tc.input) != tc.expected {
+				t.Errorf("unexpected result: %x", MarkZeroBytes(tc.input))
+			}
+		})
+	}
+}
+
+func TestSetByte(t *testing.T) {
+	testCases := []struct {
+		word     uint64
+		b        uint8
+		idx      int
+		expected uint64
+	}{
+		{
+			word:     0xffffffffffffffff,
+			b:        0,
+			idx:      0,
+			expected: 0xffffffffffffff00,
+		},
+		{
+			word:     0xffffffffffffffff,
+			b:        1,
+			idx:      1,
+			expected: 0xffffffffffff01ff,
+		},
+		{
+			word:     0xffffffffffffffff,
+			b:        2,
+			idx:      2,
+			expected: 0xffffffffff02ffff,
+		},
+		{
+			word:     0xffffffffffffffff,
+			b:        3,
+			idx:      3,
+			expected: 0xffffffff03ffffff,
+		},
+		{
+			word:     0xffffffffffffffff,
+			b:        4,
+			idx:      4,
+			expected: 0xffffff04ffffffff,
+		},
+		{
+			word:     0xffffffffffffffff,
+			b:        5,
+			idx:      5,
+			expected: 0xffff05ffffffffff,
+		},
+		{
+			word:     0xffffffffffffffff,
+			b:        6,
+			idx:      6,
+			expected: 0xff06ffffffffffff,
+		},
+		{
+			word:     0xffffffffffffffff,
+			b:        7,
+			idx:      7,
+			expected: 0x07ffffffffffffff,
+		},
+		{
+			word:     0,
+			b:        0xff,
+			idx:      7,
+			expected: 0xff00000000000000,
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(strconv.Itoa(int(tc.word)), func(t *testing.T) {
+			if SetByte(tc.word, tc.b, tc.idx) != tc.expected {
+				t.Errorf("unexpected result: %x", SetByte(tc.word, tc.b, tc.idx))
+			}
+		})
+	}
+}
+
 func BenchmarkFastrand(b *testing.B) {
 	for i := 0; i < b.N; i++ {
 		_ = Fastrand()