goniubi / hashmap

A Golang lock-free thread-safe HashMap optimized for fastest read access.

hashmap

Overview

A Golang lock-free thread-safe HashMap optimized for fastest read access.

Usage

Set a value for a key in the map:

m := &HashMap{}
m.Set("amount", 123)

Read a value for a key from the map:

amount, ok := m.Get("amount")

Use the map to count URL requests:

var i int64
actual, _ := m.GetOrInsert("api/123", &i)
counter := (actual).(*int64)
atomic.AddInt64(counter, 1) // increase counter
...
count := atomic.LoadInt64(counter) // read counter

Benchmarks

Reading from the hash map in a thread-safe way is nearly as fast as reading from a standard Golang map in an unsafe way and twice as fast as Go's sync.Map:

BenchmarkReadHashMapUint-8                	  200000	      6830 ns/op
BenchmarkReadGoMapUintUnsafe-8            	  300000	      4280 ns/op
BenchmarkReadGoMapUintMutex-8             	   30000	     51294 ns/op
BenchmarkReadGoSyncMapUint-8              	  200000	     10351 ns/op

If your keys for the map are already hashes, no extra hashing needs to be done by the map:

BenchmarkReadHashMapHashedKey-8           	 1000000	      1692 ns/op

Reading from the map while writes are happening:

BenchmarkReadHashMapWithWritesUint-8      	  200000	      8395 ns/op
BenchmarkReadGoMapWithWritesUintMutex-8   	   10000	    143793 ns/op
BenchmarkReadGoSyncMapWithWritesUint-8    	  100000	     12221 ns/op

Write performance without any concurrent reads:

BenchmarkWriteHashMapUint-8               	   10000	    210383 ns/op
BenchmarkWriteGoMapMutexUint-8            	   30000	     53331 ns/op
BenchmarkWriteGoSyncMapUint-8             	   10000	    176903 ns/op

The benchmarks were run with Golang 1.10.1 on MacOS.

Benefits over Golangs builtin map

• Faster

• thread-safe access without need of a(n extra) mutex

• Compare-and-swap access for values

• Access functions for keys that are hashes and do not need to be hashed again

Benefits over Golangs sync.Map

• Faster

• Access functions for keys that are hashes and do not need to be hashed again

Technical details

• Technical design decisions have been made based on benchmarks that are stored in an external repository: go-benchmark

• The library uses a sorted doubly linked list and a slice as an index into that list.

• The Get() function contains helper functions that have been inlined manually until the Golang compiler will inline them automatically.

• It optimizes the slice access by circumventing the Golang size check when reading from the slice. Once a slice is allocated, the size of it does not change. The library limits the index into the slice, therefor the Golang size check is obsolete. When the slice reaches a defined fill rate, a bigger slice is allocated and all keys are recalculated and transferred into the new slice.