Repository: puzpuzpuz/xsync
Pull request #1 (2021-08-10 16:08:43)

Add CLHT based Map
* Adds concurrent map data structure

The code is rough on edges, I didn't do any performance analysis, and the implementation may contain some bugs, but this Map looks promising to me. Hopefully, this or something similar lands into Golang standard library.

The Map follows the interface of sync.Map. One important difference with sync.Map is that only string keys are supported. That's because Golang standard library does not expose the built-in hash functions for `interface{}` values.

### Algorithm

Map uses a modified version of Cache-Line Hash Table (CLHT) data structure: https://github.com/LPD-EPFL/CLHT

CLHT is built around idea to organize the hash table in cache-line-sized buckets, so that on all modern CPUs update operations complete with at most one cache-line transfer. Also, Get operations involve no write to memory, as well as no mutexes or any other sort of locks.

I won't go into all details of the original algorithm, but if you're familiar with Java's ConcurrentHashMap, it's somewhat similar, yet organizes the table into a CPU-friendly way. On 64-bit builds the bucket layout looks like the following:
```
| bucket mutex	| keys array		| values array		| pointer to next bucket  |
| 8 bytes	| 24 bytes (3 pointers)	| 24 bytes (3 pointers)	| 8 bytes		  |
|<-					one cache line (64 bytes)			->|
```

Refer to the this paper to learn more: https://infoscience.epfl.ch/record/203822

`xsync.Map` has a number of modifications of the original algorithm. The most noticeable one is in the atomic snapshot logic in Get operation. Original CLHT only supported LoadOrStore semantics for updates which is somewhat restricting. `xsync.Map` supports in-place updates (Store) at the cost of Get operation being no longer wait-free. Still, Get involves no writes to memory, just like CLHT.

Another change done to keep the atomic snapshot working is that nil values are not supported. Moreover, in order to preserve value uniqueness requirement of CLHT, `*interface{}` values are used. In Go implicit `interface{}` structs are copied on each map method call, so they serve as a layer of indirection for the end values. Thanks to that, live pointers to these `interface{}` are unique.

Another modification is that resize threshold handling and the resize code are less complex than in the CLHT library, but they should do a similar job.

In general, I'm under impression that the algorith fits nicely into Golang due to flexible control over memory layout of structs, as well as the presence of garbage collection.

### Benchmarks

Benchmark results on my laptop (Ubuntu 20.04 64-bit,Go 1.16.5):
```bash
$ go test -bench=BenchmarkMap
goos: linux
goarch: amd64
pkg: github.com/puzpuzpuz/xsync
cpu: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
BenchmarkMap_NoWarmUp/99%-reads-8 	21405294	        59.62 ns/op
BenchmarkMap_NoWarmUp/90%-reads-8 	17293938	        81.48 ns/op
BenchmarkMap_NoWarmUp/75%-reads-8 	13856626	        95.53 ns/op
BenchmarkMap_NoWarmUp/50%-reads-8 	10800532	       103.8 ns/op
BenchmarkMap_NoWarmUp/0%-reads-8  	 9110863	       127.9 ns/op
BenchmarkMapStandard_NoWarmUp/99%-reads-8         	 4560795	       309.4 ns/op
BenchmarkMapStandard_NoWarmUp/90%-reads-8         	 2951302	       479.0 ns/op
BenchmarkMapStandard_NoWarmUp/75%-reads-8         	 2381186	       532.7 ns/op
BenchmarkMapStandard_NoWarmUp/50%-reads-8         	 2127937	       544.7 ns/op
BenchmarkMapStandard_NoWarmUp/0%-reads-8          	 2024616	       649.8 ns/op
BenchmarkMap_WarmUp/99%-reads-8                   	15460330	        93.33 ns/op
BenchmarkMap_WarmUp/90%-reads-8                   	15723570	        91.53 ns/op
BenchmarkMap_WarmUp/75%-reads-8                   	15416617	        95.58 ns/op
BenchmarkMap_WarmUp/50%-reads-8                   	15156489	       100.8 ns/op
BenchmarkMap_WarmUp/0%-reads-8                    	13341295	       115.5 ns/op
BenchmarkMapStandard_WarmUp/99%-reads-8           	 3817617	       279.9 ns/op
BenchmarkMapStandard_WarmUp/90%-reads-8           	 3008394	       332.8 ns/op
BenchmarkMapStandard_WarmUp/75%-reads-8           	 2909413	       362.6 ns/op
BenchmarkMapStandard_WarmUp/50%-reads-8           	 2304517	       480.2 ns/op
BenchmarkMapStandard_WarmUp/0%-reads-8            	 2163741	       568.8 ns/op
BenchmarkMapRange-8                               	     145	   8451893 ns/op
BenchmarkMapRangeStandard-8                       	      75	  16368760 ns/op
PASS
ok  	github.com/puzpuzpuz/xsync	85.686s
```

`BenchmarkMapStandard*` scenarios stand for `sync.Map`. So, far `xsync.Map` is faster than the built-in map in all scenarios, as well as in some very artificial ones I run manually and didn't include.


Patch:
diff --git a/BENCHMARKS.md b/BENCHMARKS.md
index 5f88619..2daeda8 100644
--- a/BENCHMARKS.md
+++ b/BENCHMARKS.md
@@ -9,50 +9,50 @@ To limit the number of used CPU cores append `-cpu=<number>` argument to the abo
 
 This document contains some benchmark results obtained on a cloud VM.
 
-### RBMutex vs. sync.RWMutex
+### Counter vs. atomic int64
 
 The following results were obtained on a GCP e2-highcpu-32 VM with 32 vCPUs (Intel Haswell), 32 GB memory, Ubuntu 20.04, Go 1.16.5.
 
 <figure>
-  <img src="./images/rb-mutex-read-only-no-work-chart.svg" alt="Reader locks only, no work in the critical section" />
-  <figcaption>Reader locks only, no work in the critical section</figcaption>
+  <img src="./images/counter-chart.svg" alt="Concurrent incs/decs, a value read on each 10,000 modification" />
+  <figcaption>Concurrent incs/decs, a value read on each 10,000 modification</figcaption>
 </figure>
 
-<br/><br/>
+### MPMCQueue vs. Go channels
+
+The following results were obtained on a GCP e2-highcpu-32 VM with 32 vCPUs (Intel Haswell), 32 GB memory, Ubuntu 20.04, Go 1.16.5.
 
 <figure>
-  <img src="./images/rb-mutex-read-only-work-chart.svg" alt="Reader locks only, a loop spin in the critical section" />
-  <figcaption>Reader locks only, some work in the critical section</figcaption>
+  <img src="./images/mpmcqueue-no-work-chart.svg" alt="Concurrent producers and consumers (1:1), queue/channel size 1,000, no work" />
+  <figcaption>Concurrent producers and consumers (1:1), queue/channel size 1,000, no work</figcaption>
 </figure>
 
 <br/><br/>
 
 <figure>
-  <img src="./images/rb-mutex-write-10000-chart.svg" alt="Writer locks on each 10,000 iteration, both no work and a loop spin in the critical section" />
-  <figcaption>Writer locks on each 10,000 iteration, both no work and some work in the critical section</figcaption>
+  <img src="./images/mpmcqueue-work-chart.svg" alt="Concurrent producers and consumers (1:1), queue/channel size 1,000, some work" />
+  <figcaption>Concurrent producers and consumers (1:1), queue/channel size 1,000, some work</figcaption>
 </figure>
 
-### MPMCQueue vs. Go channels
+### RBMutex vs. sync.RWMutex
 
 The following results were obtained on a GCP e2-highcpu-32 VM with 32 vCPUs (Intel Haswell), 32 GB memory, Ubuntu 20.04, Go 1.16.5.
 
 <figure>
-  <img src="./images/mpmcqueue-no-work-chart.svg" alt="Concurrent producers and consumers (1:1), queue/channel size 1,000, no work" />
-  <figcaption>Concurrent producers and consumers (1:1), queue/channel size 1,000, no work</figcaption>
+  <img src="./images/rb-mutex-read-only-no-work-chart.svg" alt="Reader locks only, no work in the critical section" />
+  <figcaption>Reader locks only, no work in the critical section</figcaption>
 </figure>
 
 <br/><br/>
 
 <figure>
-  <img src="./images/mpmcqueue-work-chart.svg" alt="Concurrent producers and consumers (1:1), queue/channel size 1,000, some work" />
-  <figcaption>Concurrent producers and consumers (1:1), queue/channel size 1,000, some work</figcaption>
+  <img src="./images/rb-mutex-read-only-work-chart.svg" alt="Reader locks only, a loop spin in the critical section" />
+  <figcaption>Reader locks only, some work in the critical section</figcaption>
 </figure>
 
-### Counter vs. atomic int64
-
-The following results were obtained on a GCP e2-highcpu-32 VM with 32 vCPUs (Intel Haswell), 32 GB memory, Ubuntu 20.04, Go 1.16.5.
+<br/><br/>
 
 <figure>
-  <img src="./images/counter-chart.svg" alt="Concurrent incs/decs, a value read on each 10,000 modification" />
-  <figcaption>Concurrent incs/decs, a value read on each 10,000 modification</figcaption>
+  <img src="./images/rb-mutex-write-10000-chart.svg" alt="Writer locks on each 10,000 iteration, both no work and a loop spin in the critical section" />
+  <figcaption>Writer locks on each 10,000 iteration, both no work and some work in the critical section</figcaption>
 </figure>
diff --git a/README.md b/README.md
index 571f584..e584c04 100644
--- a/README.md
+++ b/README.md
@@ -4,28 +4,40 @@ Concurrent data structures for Go. An extension for the standard `sync` package.
 
 This library should be considered experimental, so make sure to run benchmarks for your use cases before starting to use it in your application.
 
-## RBMutex
+### Benchmarks
 
-A `RBMutex` is a reader biased reader/writer mutual exclusion lock. The lock can be held by an many readers or a single writer.
+Benchmark results may be found [here](BENCHMARKS.md).
+
+## Counter
+
+A `Counter` is a striped int64 counter inspired by the j.u.c.a.LongAdder class from Java standard library.
 
 ```go
-var m RBMutex
-// reader lock calls return a token
-t := m.RLock()
-// the token must be later used to unlock the mutex
-m.RUnlock(t)
-// writer locks are the same as in sync.RWMutex
-m.Lock()
-m.Unlock()
+var c Counter
+// increment and decrement the counter
+c.Inc()
+c.Dec()
+// read the current value 
+v := c.Value()
 ```
 
-`RBMutex` is based on the BRAVO (Biased Locking for Reader-Writer Locks) algorithm: https://arxiv.org/pdf/1810.01553.pdf
+Works better in comparison with a single atomically updated int64 counter in high contention scenarios.
 
-The idea of the algorithm is to build on top of an existing reader-writer mutex and introduce a fast path for readers. On the fast path, reader lock attempts are sharded over an internal array based on the reader identity (a token in case of Golang). This means that readers do not contend over a single atomic counter like it's done in, say, `sync.RWMutex` allowing for better scalability in terms of cores.
+## Map
 
-Hence, by the design `RBMutex` is a specialized mutex for scenarios, such as caches, where the vast majority of locks are acquired by readers and write lock acquire attempts are infrequent. In such scenarios, `RBMutex` should perform better than the `sync.RWMutex` on large multicore machines.
+A `Map` is like a concurrent hash table based map. It follows the interface of sync.Map.
 
-`RBMutex` extends `sync.RWMutex` internally and uses it as the "reader bias disabled" fallback, so the same semantics apply. The only noticeable difference is in the reader tokens returned from the `RLock`/`RUnlock` methods.
+```go
+m := NewMap()
+m.Store("foo", "bar")
+v, ok := m.Load("foo")
+```
+
+`Map` uses a modified version of Cache-Line Hash Table (CLHT) data structure: https://github.com/LPD-EPFL/CLHT
+
+CLHT is built around idea to organize the hash table in cache-line-sized buckets, so that on all modern CPUs update operations complete with at most one cache-line transfer. 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 Map outperforms sync.Map.
+
+One important difference with sync.Map is that only string keys are supported. That's because Golang standard library does not expose the built-in hash functions for `interface{}` values. Another difference with sync.Map is that nil values are not supported. Use Delete operation or a special "nil" value to overcome this restriction.
 
 ## MPMCQueue
 
@@ -51,24 +63,28 @@ In essence, `MPMCQueue` is a specialized queue for scenarios where there are mul
 
 To get the optimal performance, you may want to set the queue size to be large enough, say, an order of magnitude greater than the number of producers/consumers, to allow producers and consumers to progress with their queue operations in parallel most of the time.
 
-## Counter
+## RBMutex
 
-A `Counter` is a striped int64 counter inspired by the j.u.c.a.LongAdder class from Java standard library.
+A `RBMutex` is a reader biased reader/writer mutual exclusion lock. The lock can be held by an many readers or a single writer.
 
 ```go
-var c Counter
-// increment and decrement the counter
-c.Inc()
-c.Dec()
-// read the current value 
-v := c.Value()
+var m RBMutex
+// reader lock calls return a token
+t := m.RLock()
+// the token must be later used to unlock the mutex
+m.RUnlock(t)
+// writer locks are the same as in sync.RWMutex
+m.Lock()
+m.Unlock()
 ```
 
-Works better in comparison with a single atomically updated int64 counter in high contention scenarios.
+`RBMutex` is based on the BRAVO (Biased Locking for Reader-Writer Locks) algorithm: https://arxiv.org/pdf/1810.01553.pdf
 
-### Benchmarks
+The idea of the algorithm is to build on top of an existing reader-writer mutex and introduce a fast path for readers. On the fast path, reader lock attempts are sharded over an internal array based on the reader identity (a token in case of Golang). This means that readers do not contend over a single atomic counter like it's done in, say, `sync.RWMutex` allowing for better scalability in terms of cores.
 
-Benchmark results may be found [here](BENCHMARKS.md).
+Hence, by the design `RBMutex` is a specialized mutex for scenarios, such as caches, where the vast majority of locks are acquired by readers and write lock acquire attempts are infrequent. In such scenarios, `RBMutex` should perform better than the `sync.RWMutex` on large multicore machines.
+
+`RBMutex` extends `sync.RWMutex` internally and uses it as the "reader bias disabled" fallback, so the same semantics apply. The only noticeable difference is in the reader tokens returned from the `RLock`/`RUnlock` methods.
 
 ## License
 
diff --git a/map.go b/map.go
new file mode 100644
index 0000000..3772bd5
--- /dev/null
+++ b/map.go
@@ -0,0 +1,394 @@
+package xsync
+
+import (
+	"sync"
+	"sync/atomic"
+	"unsafe"
+)
+
+const (
+	// number of entries per bucket; 3 entries lead to size of 64B
+	// (cache line) on 64-bit machines
+	entriesPerMapBucket = 3
+	// max number of linked buckets (chain size) to trigger a table
+	// resize during insertion; thus, each chain holds up to
+	// resizeMapThreshold+1 buckets
+	resizeMapThreshold = 2
+	// initial table size, i.e. number of buckets; thus, initial
+	// capacity can be calculated as entriesPerMapBucket*initialMapTableLen
+	initialMapTableLen = 32
+)
+
+// Map is like a Go map[string]interface{} but is safe for concurrent
+// use by multiple goroutines without additional locking or
+// coordination. It follows the interface of sync.Map.
+//
+// A Map must not be copied after first use.
+//
+// Map uses a modified version of Cache-Line Hash Table (CLHT)
+// data structure: https://github.com/LPD-EPFL/CLHT
+//
+// CLHT is built around idea to organize the hash table in
+// cache-line-sized buckets, so that on all modern CPUs update
+// operations complete with at most one cache-line transfer.
+// 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 Map outperforms sync.Map.
+//
+// One important difference with sync.Map is that only string keys
+// are supported. That's because Golang standard library does not
+// expose the built-in hash functions for interface{} values. Another
+// difference with sync.Map is that nil values are not supported. Use
+// Delete operation or a special "nil" value to overcome this
+// restriction.
+//
+// Also note that, unlike in sync.Map, the underlying hash table used
+// by Map never shrinks and only grows on demand. However, this
+// should not be an issue in many cases since updates happen in-place
+// leaving no tombstone entries.
+type Map struct {
+	table      unsafe.Pointer // []bucket
+	resizing   uint64         // resize in progress flag; updated atomically
+	resizeMu   sync.Mutex     // only used along with resizeCond
+	resizeCond sync.Cond      // used for resize waiters (concurrent modifications)
+}
+
+type bucket struct {
+	mu     sync.Mutex
+	keys   [entriesPerMapBucket]unsafe.Pointer
+	values [entriesPerMapBucket]unsafe.Pointer
+	next   unsafe.Pointer // *bucket
+}
+
+type rangeEntry struct {
+	key   unsafe.Pointer
+	value unsafe.Pointer
+}
+
+func NewMap() *Map {
+	m := &Map{}
+	m.resizeCond = *sync.NewCond(&m.resizeMu)
+	table := make([]bucket, initialMapTableLen)
+	atomic.StorePointer(&m.table, unsafe.Pointer(&table))
+	return m
+}
+
+// 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)
+	for {
+	load_attempt:
+		tablep := atomic.LoadPointer(&m.table)
+		table := *(*[]bucket)(tablep)
+		b := &table[uint32(len(table)-1)&hash]
+		for {
+			for i := 0; i < entriesPerMapBucket; i++ {
+				vp := atomic.LoadPointer(&b.values[i])
+				kp := atomic.LoadPointer(&b.keys[i])
+				if kp != nil && vp != nil {
+					k := *(*string)(kp)
+					if k == key {
+						if uintptr(vp) == uintptr(atomic.LoadPointer(&b.values[i])) {
+							// Atomic snapshot succeeded.
+							return *(*interface{})(vp), true
+						} else {
+							// Concurrent update/remove detected, so go for another spin.
+							goto load_attempt
+						}
+					}
+				}
+			}
+			bucketPtr := atomic.LoadPointer(&b.next)
+			if bucketPtr == nil {
+				return nil, false
+			}
+			b = (*bucket)(bucketPtr)
+		}
+	}
+}
+
+// Store sets the value for a key.
+//
+// A panic is raised if a nil value is provided.
+func (m *Map) Store(key string, 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.
+//
+// A panic is raised if a nil value is provided.
+func (m *Map) LoadOrStore(key string, 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) {
+	if value == nil {
+		panic("nil values are not supported")
+	}
+	// Read-only path.
+	if loadIfExists {
+		if v, ok := m.Load(key); ok {
+			return v, true
+		}
+	}
+	// Write path.
+	hash := fnv32(key)
+	for {
+	store_attempt:
+		var emptykp, emptyvp *unsafe.Pointer
+		tablep := atomic.LoadPointer(&m.table)
+		table := *(*[]bucket)(tablep)
+		rootb := &table[uint32(len(table)-1)&hash]
+		b := rootb
+		chainSize := 0
+		rootb.mu.Lock()
+		if m.newerTableExists(tablep) {
+			// Someone resized the table. Go for another attempt.
+			rootb.mu.Unlock()
+			goto store_attempt
+		}
+		if m.resizeInProgress() {
+			// Resize is in progress. Wait, then go for another attempt.
+			rootb.mu.Unlock()
+			m.waitForResize()
+			goto store_attempt
+		}
+		for {
+			for i := 0; i < entriesPerMapBucket; i++ {
+				if b.keys[i] != nil {
+					k := *(*string)(b.keys[i])
+					if k == key {
+						if loadIfExists {
+							return *(*interface{})(b.values[i]), true
+						}
+						// In-place update case. Luckily we get a copy of the value
+						// 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.
+						atomic.StorePointer(&b.values[i], unsafe.Pointer(&value))
+						rootb.mu.Unlock()
+						return
+					}
+				} else if emptykp == nil {
+					emptykp = &b.keys[i]
+					emptyvp = &b.values[i]
+				}
+			}
+			if b.next == nil {
+				if emptykp != nil {
+					// Insertion case. First we update the value, then the key.
+					// This is important for atomic snapshot states.
+					atomic.StorePointer(emptyvp, unsafe.Pointer(&value))
+					atomic.StorePointer(emptykp, unsafe.Pointer(&key))
+					rootb.mu.Unlock()
+					return
+				}
+				if chainSize == resizeMapThreshold {
+					// Need to resize the table. Then go for another attempt.
+					rootb.mu.Unlock()
+					m.resize(tablep)
+					goto store_attempt
+				}
+				// Create and append a new bucket.
+				newb := new(bucket)
+				newb.keys[0] = unsafe.Pointer(&key)
+				newb.values[0] = unsafe.Pointer(&value)
+				atomic.StorePointer(&b.next, unsafe.Pointer(newb))
+				rootb.mu.Unlock()
+				return
+			}
+			b = (*bucket)(b.next)
+			chainSize++
+		}
+	}
+}
+
+func (m *Map) newerTableExists(tablePtr unsafe.Pointer) bool {
+	curTablePtr := atomic.LoadPointer(&m.table)
+	return uintptr(curTablePtr) != uintptr(tablePtr)
+}
+
+func (m *Map) resizeInProgress() bool {
+	return atomic.LoadUint64(&m.resizing) == 1
+}
+
+func (m *Map) waitForResize() {
+	m.resizeMu.Lock()
+	for m.resizeInProgress() {
+		m.resizeCond.Wait()
+	}
+	m.resizeMu.Unlock()
+}
+
+func (m *Map) resize(tablePtr unsafe.Pointer) {
+	if !atomic.CompareAndSwapUint64(&m.resizing, 0, 1) {
+		// Someone else started resize. Wait for it to finish.
+		m.waitForResize()
+		return
+	}
+	table := *(*[]bucket)(tablePtr)
+	// Grow the table with factor of 2.
+	newTable := make([]bucket, len(table)<<1)
+	for i := 0; i < len(table); i++ {
+		copyBucket(&table[i], newTable)
+	}
+	// Publish the new table and wake up all waiters.
+	atomic.StorePointer(&m.table, unsafe.Pointer(&newTable))
+	atomic.StoreUint64(&m.resizing, 0)
+	m.resizeCond.Broadcast()
+}
+
+func copyBucket(b *bucket, table []bucket) {
+	rootb := b
+	rootb.mu.Lock()
+	for {
+		for i := 0; i < entriesPerMapBucket; i++ {
+			if b.keys[i] != nil {
+				k := *(*string)(b.keys[i])
+				hash := fnv32(k)
+				destb := &table[uint32(len(table)-1)&hash]
+				appendToBucket(destb, b.keys[i], b.values[i])
+			}
+		}
+		if b.next == nil {
+			rootb.mu.Unlock()
+			return
+		}
+		b = (*bucket)(b.next)
+	}
+}
+
+func appendToBucket(b *bucket, keyPtr, valPtr unsafe.Pointer) {
+	for {
+		for i := 0; i < entriesPerMapBucket; i++ {
+			if b.keys[i] == nil {
+				b.keys[i] = keyPtr
+				b.values[i] = valPtr
+				return
+			}
+		}
+		if b.next == nil {
+			newb := new(bucket)
+			newb.keys[0] = keyPtr
+			newb.values[0] = valPtr
+			b.next = unsafe.Pointer(newb)
+			return
+		}
+		b = (*bucket)(b.next)
+	}
+}
+
+// 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)
+	for {
+		tablep := atomic.LoadPointer(&m.table)
+		table := *(*[]bucket)(tablep)
+		rootb := &table[uint32(len(table)-1)&hash]
+		b := rootb
+		rootb.mu.Lock()
+		if m.newerTableExists(tablep) {
+			// Someone resized the table. Go for another attempt.
+			rootb.mu.Unlock()
+			continue
+		}
+		if m.resizeInProgress() {
+			// Resize is in progress. Wait, then go for another attempt.
+			rootb.mu.Unlock()
+			m.waitForResize()
+			continue
+		}
+		for {
+			for i := 0; i < entriesPerMapBucket; i++ {
+				kp := b.keys[i]
+				if kp != nil {
+					k := *(*string)(kp)
+					if k == key {
+						vp := b.values[i]
+						// Deletion case. First we update the value, then the key.
+						// This is important for atomic snapshot states.
+						atomic.StorePointer(&b.values[i], nil)
+						atomic.StorePointer(&b.keys[i], nil)
+						rootb.mu.Unlock()
+						return *(*interface{})(vp), true
+					}
+				}
+			}
+			if b.next == nil {
+				rootb.mu.Unlock()
+				return nil, false
+			}
+			b = (*bucket)(b.next)
+		}
+	}
+}
+
+// Delete deletes the value for a key.
+func (m *Map) Delete(key string) {
+	m.LoadAndDelete(key)
+}
+
+// Range calls f sequentially for each key and value present in the
+// map. If f returns false, range stops the iteration.
+//
+// Range does not necessarily correspond to any consistent snapshot
+// of the Map's contents: no key will be visited more than once, but
+// if the value for any key is stored or deleted concurrently, Range
+// may reflect any mapping for that key from any point during the
+// Range call.
+//
+// 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) {
+	tablep := atomic.LoadPointer(&m.table)
+	table := *(*[]bucket)(tablep)
+	bentries := make([]rangeEntry, 0)
+	for i := range table {
+		copyRangeEntries(&bentries, &table[i])
+		for j := range bentries {
+			if bentries[j].key == nil {
+				break
+			}
+			k := *(*string)(bentries[j].key)
+			v := *(*interface{})(bentries[j].value)
+			if !f(k, v) {
+				return
+			}
+		}
+	}
+}
+
+func copyRangeEntries(bentries *[]rangeEntry, b *bucket) {
+	// Clean up the slice.
+	for i := range *bentries {
+		(*bentries)[i] = rangeEntry{}
+	}
+	*bentries = (*bentries)[:0]
+	// Make a copy.
+	idx := 0
+	rootb := b
+	rootb.mu.Lock()
+	for {
+		for i := 0; i < entriesPerMapBucket; i++ {
+			if b.keys[i] != nil {
+				*bentries = append(*bentries, rangeEntry{
+					key:   b.keys[i],
+					value: b.values[i],
+				})
+				idx++
+			}
+		}
+		if b.next == nil {
+			rootb.mu.Unlock()
+			return
+		}
+		b = (*bucket)(b.next)
+	}
+}
diff --git a/mpmcqueue.go b/mpmcqueue.go
index 68b317e..d9662e1 100644
--- a/mpmcqueue.go
+++ b/mpmcqueue.go
@@ -6,12 +6,13 @@ import (
 	"unsafe"
 )
 
-// A MPMCQueue is a bounded multi-producer multi-consumer concurrent queue.
+// A MPMCQueue is a bounded multi-producer multi-consumer concurrent
+// queue.
 //
 // MPMCQueue instances must be created with NewMPMCQueue function.
 // A MPMCQueue must not be copied after first use.
 //
-// Based on the algorithm from the following C++ library:
+// Based on the data structure from the following C++ library:
 // https://github.com/rigtorp/MPMCQueue
 type MPMCQueue struct {
 	cap   uint64
@@ -32,7 +33,8 @@ type slotInternal struct {
 	item interface{}
 }
 
-// NewMPMCQueue creates a new MPMCQueue instance with the given capacity.
+// NewMPMCQueue creates a new MPMCQueue instance with the given
+// capacity.
 func NewMPMCQueue(capacity int) *MPMCQueue {
 	if capacity < 1 {
 		panic("capacity must be positive number")
@@ -71,10 +73,9 @@ func (q *MPMCQueue) Dequeue() interface{} {
 	return item
 }
 
-// TryEnqueue inserts the given item into the queue.
-// Does not block and returns immediately.
-// The result indicates that the queue isn't full and the item was
-// inserted.
+// TryEnqueue inserts the given item into the queue. Does not block
+// and returns immediately. The result indicates that the queue isn't
+// full and the item was inserted.
 func (q *MPMCQueue) TryEnqueue(item interface{}) bool {
 	head := atomic.LoadUint64(&q.head)
 	for {
@@ -97,10 +98,9 @@ func (q *MPMCQueue) TryEnqueue(item interface{}) bool {
 	}
 }
 
-// TryDequeue retrieves and removes the item from the head of the queue.
-// Does not block and returns immediately.
-// The ok result indicates that the queue isn't empty and an item was
-// retrieved.
+// TryDequeue retrieves and removes the item from the head of the
+// queue. Does not block and returns immediately. The ok result
+// indicates that the queue isn't empty and an item was retrieved.
 func (q *MPMCQueue) TryDequeue() (item interface{}, ok bool) {
 	tail := atomic.LoadUint64(&q.tail)
 	for {
diff --git a/rbmutex.go b/rbmutex.go
index c31bb86..4708bba 100644
--- a/rbmutex.go
+++ b/rbmutex.go
@@ -29,13 +29,13 @@ type RToken struct {
 //
 // A RBMutex must not be copied after first use.
 //
-// RBMutex is based on the BRAVO (Biased Locking for Reader-Writer Locks)
-// algorithm: https://arxiv.org/pdf/1810.01553.pdf
+// RBMutex is based on the BRAVO (Biased Locking for Reader-Writer
+// Locks) algorithm: https://arxiv.org/pdf/1810.01553.pdf
 //
-// RBMutex is a specialized mutex for scenarios, such as caches, where
-// the vast majority of locks are acquired by readers and write lock
-// acquire attempts are infrequent. In such scenarios, RBMutex performs
-// better than the sync.RWMutex on large multicore machines.
+// RBMutex is a specialized mutex for scenarios, such as caches,
+// where the vast majority of locks are acquired by readers and write
+// lock acquire attempts are infrequent. In such scenarios, RBMutex
+// performs better than the sync.RWMutex on large multicore machines.
 //
 // RBMutex extends sync.RWMutex internally and uses it as the "reader
 // bias disabled" fallback, so the same semantics apply. The only
@@ -76,11 +76,10 @@ func (m *RBMutex) RLock() *RToken {
 	return nil
 }
 
-// RUnlock undoes a single RLock call. A reader token
-// obtained from the RLock call must be provided.
-// RUnlock does not affect other simultaneous readers.
-// A panic is raised if m is not locked for reading
-// on entry to RUnlock.
+// RUnlock undoes a single RLock call. A reader token obtained from
+// the RLock call must be provided. RUnlock does not affect other
+// simultaneous readers. A panic is raised if m is not locked for
+// reading on entry to RUnlock.
 func (m *RBMutex) RUnlock(t *RToken) {
 	if t == nil {
 		m.rw.RUnlock()
@@ -92,9 +91,8 @@ func (m *RBMutex) RUnlock(t *RToken) {
 	rtokenPool.Put(t)
 }
 
-// Lock locks m for writing.
-// If the lock is already locked for reading or writing,
-// Lock blocks until the lock is available.
+// Lock locks m for writing. If the lock is already locked for
+// reading or writing, Lock blocks until the lock is available.
 func (m *RBMutex) Lock() {
 	m.rw.Lock()
 	if atomic.LoadInt32(&m.rbias) == 1 {
@@ -109,12 +107,12 @@ func (m *RBMutex) Lock() {
 	}
 }
 
-// Unlock unlocks m for writing. A panic is raised if m is
-// not locked for writing on entry to Unlock.
+// Unlock unlocks m for writing. A panic is raised if m is not locked
+// for writing on entry to Unlock.
 //
-// As with RWMutex, a locked RBMutex is not associated with a particular
-// goroutine. One goroutine may RLock (Lock) a RBMutex and then
-// arrange for another goroutine to RUnlock (Unlock) it.
+// As with RWMutex, a locked RBMutex is not associated with a
+// particular goroutine. One goroutine may RLock (Lock) a RBMutex and
+// then arrange for another goroutine to RUnlock (Unlock) it.
 func (m *RBMutex) Unlock() {
 	m.rw.Unlock()
 }
diff --git a/util.go b/util.go
index 61ac7f3..69164d2 100644
--- a/util.go
+++ b/util.go
@@ -6,6 +6,8 @@ const (
 	// 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
@@ -15,3 +17,14 @@ func hash64(x uintptr) uint32 {
 	x = (x >> 33) ^ x
 	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
+	}
+	return hash
+}


Test patch:
diff --git a/export_test.go b/export_test.go
new file mode 100644
index 0000000..37850e6
--- /dev/null
+++ b/export_test.go
@@ -0,0 +1,3 @@
+package xsync
+
+type Bucket = bucket
diff --git a/map_test.go b/map_test.go
new file mode 100644
index 0000000..35f5249
--- /dev/null
+++ b/map_test.go
@@ -0,0 +1,425 @@
+package xsync_test
+
+import (
+	"math/bits"
+	"math/rand"
+	"strconv"
+	"sync"
+	"testing"
+	"time"
+	"unsafe"
+
+	. "github.com/puzpuzpuz/xsync"
+)
+
+const (
+	// number of entries to use in benchmarks
+	benchmarkNumEntries = 1_000_000
+	// key prefix used in benchmarks
+	benchmarkKeyPrefix = "what_a_looooooooooooooooooooooong_key_prefix_"
+)
+
+var benchmarkCases = []struct {
+	name           string
+	writeThreshold int
+}{
+	{"99%-reads", 99}, // 99% loads,  0.5% stores,  0.5% deletes
+	{"90%-reads", 90}, // 90% loads,    5% stores,    5% deletes
+	{"75%-reads", 75}, // 75% loads, 12.5% stores, 12.5% deletes
+	{"50%-reads", 50}, // 50% loads,   25% stores,   25% deletes
+	{"0%-reads", 0},   //  0% loads,   50% stores,   50% deletes
+}
+
+func TestMapBucketStructSize(t *testing.T) {
+	if bits.UintSize != 64 {
+		return // skip for 32-bit builds
+	}
+	size := unsafe.Sizeof(Bucket{})
+	if size != 64 {
+		t.Errorf("size of 64B (cache line) is expected, got: %d", size)
+	}
+}
+
+func TestMapMissingEntry(t *testing.T) {
+	m := NewMap()
+	v, ok := m.Load("foo")
+	if ok {
+		t.Errorf("value was not expected: %v", v)
+	}
+	if deleted, loaded := m.LoadAndDelete("foo"); loaded {
+		t.Errorf("value was not expected %v", deleted)
+	}
+	if actual, loaded := m.LoadOrStore("foo", "bar"); loaded {
+		t.Errorf("value was not expected %v", actual)
+	}
+}
+
+func TestMapStoreNilValue(t *testing.T) {
+	m := NewMap()
+	defer func() {
+		recover()
+	}()
+	m.Store("foo", nil)
+	t.Error("no panic was raised")
+}
+
+func TestMapLoadOrStoreNilValue(t *testing.T) {
+	m := NewMap()
+	defer func() {
+		recover()
+	}()
+	m.LoadOrStore("foo", nil)
+	t.Error("no panic was raised")
+}
+
+func TestMapRange(t *testing.T) {
+	const numEntries = 1000
+	m := NewMap()
+	for i := 0; i < numEntries; i++ {
+		m.Store(strconv.Itoa(i), i)
+	}
+	iters := 0
+	met := make(map[string]int)
+	m.Range(func(key string, 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
+		}
+		met[key] += 1
+		iters++
+		return true
+	})
+	if iters != numEntries {
+		t.Errorf("got unexpected number of iterations: %d", iters)
+	}
+	for i := 0; i < numEntries; i++ {
+		if c := met[strconv.Itoa(i)]; c != 1 {
+			t.Errorf("range did not iterate correctly over %d: %d", i, c)
+		}
+	}
+}
+
+func TestMapRange_FalseReturned(t *testing.T) {
+	m := NewMap()
+	for i := 0; i < 100; i++ {
+		m.Store(strconv.Itoa(i), i)
+	}
+	iters := 0
+	m.Range(func(key string, value interface{}) bool {
+		iters++
+		return iters != 13
+	})
+	if iters != 13 {
+		t.Errorf("got unexpected number of iterations: %d", iters)
+	}
+}
+
+func TestMapRange_NestedDelete(t *testing.T) {
+	const numEntries = 256
+	m := NewMap()
+	for i := 0; i < numEntries; i++ {
+		m.Store(strconv.Itoa(i), i)
+	}
+	m.Range(func(key string, value interface{}) bool {
+		m.Delete(key)
+		return true
+	})
+	for i := 0; i < numEntries; i++ {
+		if _, ok := m.Load(strconv.Itoa(i)); ok {
+			t.Errorf("value found for %d", i)
+		}
+	}
+}
+
+func TestMapSerialStore(t *testing.T) {
+	const numEntries = 128
+	m := NewMap()
+	for i := 0; i < numEntries; i++ {
+		m.Store(strconv.Itoa(i), i)
+	}
+	for i := 0; i < numEntries; i++ {
+		v, ok := m.Load(strconv.Itoa(i))
+		if !ok {
+			t.Errorf("value not found for %d", i)
+		}
+		if v == nil {
+			t.Errorf("nil value found for %d", i)
+		}
+		if vi, ok := v.(int); ok && vi != i {
+			t.Errorf("values do not match for %d: %v", i, v)
+		}
+	}
+}
+
+func TestMapSerialLoadOrStore(t *testing.T) {
+	const numEntries = 1000
+	m := NewMap()
+	for i := 0; i < numEntries; i++ {
+		m.Store(strconv.Itoa(i), i)
+	}
+	for i := 0; i < numEntries; i++ {
+		if _, loaded := m.LoadOrStore(strconv.Itoa(i), i); !loaded {
+			t.Errorf("value not found for %d", i)
+		}
+	}
+}
+
+func TestMapSerialStoreThenDelete(t *testing.T) {
+	const numEntries = 1000
+	m := NewMap()
+	for i := 0; i < numEntries; i++ {
+		m.Store(strconv.Itoa(i), i)
+	}
+	for i := 0; i < numEntries; i++ {
+		m.Delete(strconv.Itoa(i))
+		if _, ok := m.Load(strconv.Itoa(i)); ok {
+			t.Errorf("value was not expected for %d", i)
+		}
+	}
+}
+
+func TestMapSerialStoreThenLoadAndDelete(t *testing.T) {
+	const numEntries = 1000
+	m := NewMap()
+	for i := 0; i < numEntries; i++ {
+		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 _, ok := m.Load(strconv.Itoa(i)); ok {
+			t.Errorf("value was not expected for %d", i)
+		}
+	}
+}
+
+func parallelSeqStorer(t *testing.T, m *Map, storeEach, numIters, numEntries int, cdone chan bool) {
+	for j := 0; j < numEntries; j++ {
+		if storeEach == 0 || j%storeEach == 0 {
+			m.Store(strconv.Itoa(j), j)
+			// Due to atomic snapshots we must either see no entry, or a "<j>"/j pair.
+			v, ok := m.Load(strconv.Itoa(j))
+			if !ok {
+				t.Errorf("value was not found for %d", j)
+				break
+			}
+			if vi, ok := v.(int); !ok || vi != j {
+				t.Errorf("value was not expected for %d: %d", j, vi)
+				break
+			}
+		}
+	}
+	cdone <- true
+}
+
+func TestMapParallelStores(t *testing.T) {
+	const numStorers = 4
+	const numIters = 100_000
+	const numEntries = 100
+	m := NewMap()
+	cdone := make(chan bool)
+	for i := 0; i < numStorers; i++ {
+		go parallelSeqStorer(t, m, i, numIters, numEntries, cdone)
+	}
+	// Wait for the goroutines to finish.
+	for i := 0; i < numStorers; i++ {
+		<-cdone
+	}
+	// Verify map contents.
+	for i := 0; i < numEntries; i++ {
+		v, ok := m.Load(strconv.Itoa(i))
+		if !ok {
+			t.Errorf("value not found for %d", i)
+		}
+		if v == nil {
+			t.Errorf("nil value found for %d", i)
+		}
+		if vi, ok := v.(int); ok && vi != i {
+			t.Errorf("values do not match for %d: %v", i, v)
+		}
+	}
+}
+
+func parallelRandStorer(m *Map, numIters, numEntries int, cdone chan bool) {
+	r := rand.New(rand.NewSource(time.Now().UnixNano()))
+	for i := 0; i < numIters; i++ {
+		j := r.Intn(numEntries)
+		m.Store(strconv.Itoa(j), j)
+	}
+	cdone <- true
+}
+
+func parallelRandDeleter(m *Map, numIters, numEntries int, cdone chan bool) {
+	r := rand.New(rand.NewSource(time.Now().UnixNano()))
+	for i := 0; i < numIters; i++ {
+		j := r.Intn(numEntries)
+		m.Delete(strconv.Itoa(j))
+	}
+	cdone <- true
+}
+
+func parallelLoader(t *testing.T, m *Map, numIters, numEntries int, cdone chan bool) {
+	for i := 0; i < numIters; i++ {
+		for j := 0; j < numEntries; j++ {
+			// Due to atomic snapshots we must either see no entry, or a "<j>"/j pair.
+			if v, ok := m.Load(strconv.Itoa(j)); ok {
+				if vi, ok := v.(int); !ok || vi != j {
+					t.Errorf("value was not expected for %d: %d", j, vi)
+				}
+			}
+		}
+	}
+	cdone <- true
+}
+
+func TestMapAtomicSnapshot(t *testing.T) {
+	const numIters = 100_000
+	const numEntries = 100
+	m := NewMap()
+	cdone := make(chan bool)
+	// Update or delete each entry in parallel with loads.
+	go parallelRandStorer(m, numIters, numEntries, cdone)
+	go parallelRandDeleter(m, numIters, numEntries, cdone)
+	go parallelLoader(t, m, numIters, numEntries, cdone)
+	// Wait for the goroutines to finish.
+	for i := 0; i < 3; i++ {
+		<-cdone
+	}
+}
+
+type SyncMap interface {
+	Load(key string) (value interface{}, ok bool)
+	Store(key string, value interface{})
+}
+
+func BenchmarkMap_NoWarmUp(b *testing.B) {
+	for _, bc := range benchmarkCases {
+		b.Run(bc.name, func(b *testing.B) {
+			m := NewMap()
+			benchmarkMap(b, func(k string) (interface{}, bool) {
+				return m.Load(k)
+			}, func(k string, v interface{}) {
+				m.Store(k, v)
+			}, func(k string) {
+				m.Delete(k)
+			}, bc.writeThreshold)
+		})
+	}
+}
+
+func BenchmarkMapStandard_NoWarmUp(b *testing.B) {
+	for _, bc := range benchmarkCases {
+		b.Run(bc.name, func(b *testing.B) {
+			var m sync.Map
+			benchmarkMap(b, func(k string) (interface{}, bool) {
+				return m.Load(k)
+			}, func(k string, v interface{}) {
+				m.Store(k, v)
+			}, func(k string) {
+				m.Delete(k)
+			}, bc.writeThreshold)
+		})
+	}
+}
+
+func BenchmarkMap_WarmUp(b *testing.B) {
+	for _, bc := range benchmarkCases {
+		b.Run(bc.name, func(b *testing.B) {
+			m := NewMap()
+			for i := 0; i < benchmarkNumEntries; i++ {
+				m.Store(benchmarkKeyPrefix+strconv.Itoa(i), i)
+			}
+			benchmarkMap(b, func(k string) (interface{}, bool) {
+				return m.Load(k)
+			}, func(k string, v interface{}) {
+				m.Store(k, v)
+			}, func(k string) {
+				m.Delete(k)
+			}, bc.writeThreshold)
+		})
+	}
+}
+
+// This is a nice scenario for sync.Map since a lot of updates
+// will hit the readOnly part of the map.
+func BenchmarkMapStandard_WarmUp(b *testing.B) {
+	for _, bc := range benchmarkCases {
+		b.Run(bc.name, func(b *testing.B) {
+			var m sync.Map
+			for i := 0; i < benchmarkNumEntries; i++ {
+				m.Store(benchmarkKeyPrefix+strconv.Itoa(i), i)
+			}
+			benchmarkMap(b, func(k string) (interface{}, bool) {
+				return m.Load(k)
+			}, func(k string, v interface{}) {
+				m.Store(k, v)
+			}, func(k string) {
+				m.Delete(k)
+			}, bc.writeThreshold)
+		})
+	}
+}
+
+func benchmarkMap(
+	b *testing.B,
+	loadFn func(k string) (interface{}, bool),
+	storeFn func(k string, v interface{}),
+	deleteFn func(k string),
+	writeThreshold int) {
+
+	b.ResetTimer()
+	b.RunParallel(func(pb *testing.PB) {
+		r := rand.New(rand.NewSource(time.Now().UnixNano()))
+		// convert percent to permille to support 99% case
+		storeThreshold := 10 * writeThreshold
+		deleteThreshold := 10*writeThreshold + ((1000 - 10*writeThreshold) / 2)
+		for pb.Next() {
+			op := r.Intn(1000)
+			i := r.Intn(benchmarkNumEntries)
+			if op >= deleteThreshold {
+				deleteFn(benchmarkKeyPrefix + strconv.Itoa(i))
+			} else if op >= storeThreshold {
+				storeFn(benchmarkKeyPrefix+strconv.Itoa(i), i)
+			} else {
+				loadFn(benchmarkKeyPrefix + strconv.Itoa(i))
+			}
+		}
+	})
+}
+
+func BenchmarkMapRange(b *testing.B) {
+	m := NewMap()
+	for i := 0; i < benchmarkNumEntries; i++ {
+		m.Store(benchmarkKeyPrefix+strconv.Itoa(i), i)
+	}
+	b.ResetTimer()
+	b.RunParallel(func(pb *testing.PB) {
+		foo := 0
+		for pb.Next() {
+			m.Range(func(key string, value interface{}) bool {
+				foo++
+				return true
+			})
+			_ = foo
+		}
+	})
+}
+
+func BenchmarkMapRangeStandard(b *testing.B) {
+	var m sync.Map
+	for i := 0; i < benchmarkNumEntries; i++ {
+		m.Store(benchmarkKeyPrefix+strconv.Itoa(i), i)
+	}
+	b.ResetTimer()
+	b.RunParallel(func(pb *testing.PB) {
+		foo := 0
+		for pb.Next() {
+			m.Range(func(key interface{}, value interface{}) bool {
+				foo++
+				return true
+			})
+			_ = foo
+		}
+	})
+}