ChainMap

README

ChainMap is a fast concurrent hash map implementation.

ChainMap is implemented using a concurrent(lock free) sorted singly linked list. This is the reason that this implementation can be completely lock free without complicated logics. If Go allows double CAS or manual memory management like C++, this implementation can be even more efficient. Yes, implementing ChainMap in C++ would be way faster than in Go.

Details:

1. There is completely lock-free and non-blocking.
2. The linked list is implemented using https://www.cl.cam.ac.uk/research/srg/netos/papers/2001-caslists.pdf by Timothy L. Harris.
3. Read operations are completely non-blocking with no busy waiting.
4. Expanding the map is treated as a series of insertion operation.
5. Shrinking the map is treated as a series of deletion operation.

Here are the benchmarks I did to compare ChainMap to sync.Map and a normal map with RWMutex. These test cases are inspired by https://github.com/dustinxie/lockfree/blob/master/map_test.go.

1. This is to mimic the first use case described for sync.Map. Some keys are inserted and read multiple times.
2. This is to mimic the second use case described for sync.Map. Disjoint set of keys are read and write.
3. This is a general case to mimic a concurrent environment where keys are inserted, read, and deleted.

BenchmarkChainMap_Case1-16 1528 748276 ns/op 918799 B/op 45113 allocs/op

BenchmarkSyncMap_Case1-16 370 3212790 ns/op 1438684 B/op 40750 allocs/op

BenchmarkMutexMap_Case1-16 337 3540829 ns/op 686400 B/op 293 allocs/op

BenchmarkChainMap_Case2-16 9228 113376 ns/op 66072 B/op 8208 allocs/op

BenchmarkSyncMap_Case2-16 1004 1147019 ns/op 258789 B/op 24083 allocs/op

BenchmarkMutexMap_Case2-16 450 2665258 ns/op 644 B/op 16 allocs/op

BenchmarkChainMap_Case3-16 1230 999950 ns/op 1016945 B/op 55616 allocs/op

BenchmarkSyncMap_Case3-16 364 3304403 ns/op 1461508 B/op 40750 allocs/op

BenchmarkMutexMap_Case3-16 188 6297385 ns/op 622392 B/op 306 allocs/op

Observations:

1. Sync.Map is faster than mutex map in the first 2 cases.
2. In all 3 cases, ChainMap is significantly faster than the rest.
3. ChainMap uses lots of memory allocations, which is true according to the implementation. However, many of these are garbage collected (many of these are temporary variables), so it can be potentially optimized by using some pooling mechanics.
4. On average, ChainMap uses 33% less memory than Sync.Map. However, a normal map uses the least amount of memory.

Documentation

Index

• type ChainMap
  • func New[K any, V any](minBucketLen, maxBucketLen byte, maxHash uint, hasher func(K) uint, ...) *ChainMap[K, V]
  • func (u *ChainMap[K, V]) Delete(key K)
  • func (u *ChainMap[K, V]) HasKey(key K) bool
  • func (u *ChainMap[K, V]) Load(key K) (val V, ok bool)
  • func (u *ChainMap[K, V]) LoadAndDelete(key K) (val V, loaded bool)
  • func (u *ChainMap[K, V]) LoadOrStore(key K, val V) (V, bool)
  • func (u *ChainMap[K, V]) LoadPtr(key K) (vp *V)
  • func (u *ChainMap[K, V]) LoadPtrAndDelete(key K) (val *V, loaded bool)
  • func (u *ChainMap[K, V]) LoadPtrOrStore(key K, val V) (*V, bool)
  • func (u *ChainMap[K, V]) Range(f func(K, V) bool)
  • func (u *ChainMap[K, V]) RangePtr(f func(K, *V) bool)
  • func (u *ChainMap[K, V]) Set(key K, val V) (v *V)
  • func (u *ChainMap[K, V]) Size() uint
  • func (u *ChainMap[K, V]) Store(key K, val V)
  • func (u *ChainMap[K, V]) Take() (K, V)
  • func (u *ChainMap[K, V]) TakePtr() (K, *V)

Types

type ChainMap

type ChainMap[K any, V any] struct {
	// contains filtered or unexported fields
}

func New

func New[K any, V any](minBucketLen, maxBucketLen byte, maxHash uint, hasher func(K) uint, comparator func(K, K) bool) *ChainMap[K, V]

func (*ChainMap[K, V]) Delete

func (u *ChainMap[K, V]) Delete(key K)

func (*ChainMap[K, V]) HasKey

func (u *ChainMap[K, V]) HasKey(key K) bool

func (*ChainMap[K, V]) Load

func (u *ChainMap[K, V]) Load(key K) (val V, ok bool)

func (*ChainMap[K, V]) LoadAndDelete

func (u *ChainMap[K, V]) LoadAndDelete(key K) (val V, loaded bool)

func (*ChainMap[K, V]) LoadOrStore

func (u *ChainMap[K, V]) LoadOrStore(key K, val V) (V, bool)

func (*ChainMap[K, V]) LoadPtr

func (u *ChainMap[K, V]) LoadPtr(key K) (vp *V)

func (*ChainMap[K, V]) LoadPtrAndDelete

func (u *ChainMap[K, V]) LoadPtrAndDelete(key K) (val *V, loaded bool)

func (*ChainMap[K, V]) LoadPtrOrStore

func (u *ChainMap[K, V]) LoadPtrOrStore(key K, val V) (*V, bool)

func (*ChainMap[K, V]) Range

func (u *ChainMap[K, V]) Range(f func(K, V) bool)

func (*ChainMap[K, V]) RangePtr

func (u *ChainMap[K, V]) RangePtr(f func(K, *V) bool)

func (*ChainMap[K, V]) Set

func (u *ChainMap[K, V]) Set(key K, val V) (v *V)

func (*ChainMap[K, V]) Size

func (u *ChainMap[K, V]) Size() uint

func (*ChainMap[K, V]) Store

func (u *ChainMap[K, V]) Store(key K, val V)

func (*ChainMap[K, V]) Take

func (u *ChainMap[K, V]) Take() (K, V)

func (*ChainMap[K, V]) TakePtr

func (u *ChainMap[K, V]) TakePtr() (K, *V)