README
¶
hashmap
Overview
A Golang lock-free thread-safe HashMap optimized for fastest read access.
It is not a general-use HashMap and currently has slow write performance for write heavy uses.
The minimal supported Golang version is 1.19 as it makes use of Generics and the new atomic package helpers.
Usage
Example uint8 key map uses:
m := New[uint8, int]()
m.Set(1, 123)
value, ok := m.Get(1)
Example string key map uses:
m := New[string, int]()
m.Set("amount", 123)
value, ok := m.Get("amount")
Using the map to count URL requests:
m := New[string, *int64]()
var i int64
counter, _ := m.GetOrInsert("api/123", &i)
atomic.AddInt64(counter, 1) // increase counter
...
count := atomic.LoadInt64(counter) // read counter
Benchmarks
Reading from the hash map for numeric key types in a thread-safe way is faster than reading from a standard Golang map
in an unsafe way and four times faster than Golang's sync.Map:
BenchmarkReadHashMapUint-8 1774460 677.3 ns/op
BenchmarkReadHaxMapUint-8 1758708 679.0 ns/op
BenchmarkReadGoMapUintUnsafe-8 1497732 790.9 ns/op
BenchmarkReadGoMapUintMutex-8 41562 28672 ns/op
BenchmarkReadGoSyncMapUint-8 454401 2646 ns/op
Reading from the map while writes are happening:
BenchmarkReadHashMapWithWritesUint-8 1388560 859.1 ns/op
BenchmarkReadHaxMapWithWritesUint-8 1306671 914.5 ns/op
BenchmarkReadGoSyncMapWithWritesUint-8 335732 3113 ns/op
Write performance without any concurrent reads:
BenchmarkWriteHashMapUint-8 54756 21977 ns/op
BenchmarkWriteGoMapMutexUint-8 83907 14827 ns/op
BenchmarkWriteGoSyncMapUint-8 16983 70305 ns/op
The benchmarks were run with Golang 1.19.0 on Linux and AMD64 using make benchmark.
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 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, therefore 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.
-
For hashing, specialized xxhash implementations are used that match the size of the key type where available
Documentation
¶
Overview ¶
Package hashmap provides a lock-free and thread-safe HashMap.
Index ¶
- type List
- func (l *List[Key, Value]) Add(searchStart *ListElement[Key, Value], hash uintptr, key Key, value Value) (element *ListElement[Key, Value], existed bool, inserted bool)
- func (l *List[Key, Value]) AddOrUpdate(searchStart *ListElement[Key, Value], hash uintptr, key Key, value Value) (*ListElement[Key, Value], bool)
- func (l *List[Key, Value]) Delete(element *ListElement[Key, Value])
- func (l *List[Key, Value]) First() *ListElement[Key, Value]
- func (l *List[Key, Value]) Len() int
- type ListElement
- type Map
- func (m *Map[Key, Value]) Del(key Key) bool
- func (m *Map[Key, Value]) FillRate() int
- func (m *Map[Key, Value]) Get(key Key) (Value, bool)
- func (m *Map[Key, Value]) GetOrInsert(key Key, value Value) (Value, bool)
- func (m *Map[Key, Value]) Grow(newSize uintptr)
- func (m *Map[Key, Value]) Insert(key Key, value Value) bool
- func (m *Map[Key, Value]) Len() int
- func (m *Map[Key, Value]) Range(f func(Key, Value) bool)
- func (m *Map[Key, Value]) Set(key Key, value Value)
- func (m *Map[Key, Value]) SetHasher(hasher func(Key) uintptr)
- func (m *Map[Key, Value]) String() string
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type List ¶
type List[Key comparable, Value any] struct { // contains filtered or unexported fields }
List is a sorted linked list.
func NewList ¶
func NewList[Key comparable, Value any]() *List[Key, Value]
NewList returns an initialized list.
func (*List[Key, Value]) Add ¶
func (l *List[Key, Value]) Add(searchStart *ListElement[Key, Value], hash uintptr, key Key, value Value) (element *ListElement[Key, Value], existed bool, inserted bool)
Add adds an item to the list and returns false if an item for the hash existed. searchStart = nil will start to search at the head item.
func (*List[Key, Value]) AddOrUpdate ¶
func (l *List[Key, Value]) AddOrUpdate(searchStart *ListElement[Key, Value], hash uintptr, key Key, value Value) (*ListElement[Key, Value], bool)
AddOrUpdate adds or updates an item to the list.
func (*List[Key, Value]) Delete ¶
func (l *List[Key, Value]) Delete(element *ListElement[Key, Value])
Delete deletes an element from the list.
func (*List[Key, Value]) First ¶
func (l *List[Key, Value]) First() *ListElement[Key, Value]
First returns the first item of the list.
type ListElement ¶
type ListElement[Key comparable, Value any] struct { // contains filtered or unexported fields }
ListElement is an element of a list.
func (*ListElement[Key, Value]) Next ¶
func (e *ListElement[Key, Value]) Next() *ListElement[Key, Value]
Next returns the item on the right.
func (*ListElement[Key, Value]) Value ¶
func (e *ListElement[Key, Value]) Value() Value
Value returns the value of the list item.
type Map ¶ added in v1.0.7
type Map[Key hashable, Value any] struct { // contains filtered or unexported fields }
Map implements a read optimized hash map.
func NewSized ¶ added in v1.0.2
NewSized returns a new map instance with a specific initialization size.
func (*Map[Key, Value]) Del ¶ added in v1.0.7
Del deletes the key from the map and returns whether the key was deleted.
func (*Map[Key, Value]) FillRate ¶ added in v1.0.7
FillRate returns the fill rate of the map as a percentage integer.
func (*Map[Key, Value]) Get ¶ added in v1.0.7
Get retrieves an element from the map under given hash key.
func (*Map[Key, Value]) GetOrInsert ¶ added in v1.0.7
GetOrInsert returns the existing value for the key if present. Otherwise, it stores and returns the given value. The returned bool is true if the value was loaded, false if stored.
func (*Map[Key, Value]) Grow ¶ added in v1.0.7
Grow resizes the map to a new size, the size gets rounded up to next power of 2. To double the size of the map use newSize 0. This function returns immediately, the resize operation is done in a goroutine. No resizing is done in case of another resize operation already being in progress.
func (*Map[Key, Value]) Insert ¶ added in v1.0.7
Insert sets the value under the specified key to the map if it does not exist yet. If a resizing operation is happening concurrently while calling Insert, the item might show up in the map after the resize operation is finished. Returns true if the item was inserted or false if it existed.
func (*Map[Key, Value]) Range ¶ added in v1.0.7
Range calls f sequentially for each key and value present in the map. If f returns false, range stops the iteration.
func (*Map[Key, Value]) Set ¶ added in v1.0.7
func (m *Map[Key, Value]) Set(key Key, value Value)
Set sets the value under the specified key to the map. An existing item for this key will be overwritten. If a resizing operation is happening concurrently while calling Set, the item might show up in the map after the resize operation is finished.
Source Files
Directories