README
¶
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.
Documentation
¶
Index ¶
- Constants
- type HashMap
- func (m *HashMap) Cas(key, from, to interface{}) bool
- func (m *HashMap) CasHashedKey(hashedKey uintptr, from, to interface{}) bool
- func (m *HashMap) Del(key interface{})
- func (m *HashMap) DelHashedKey(hashedKey uintptr)
- func (m *HashMap) Fillrate() uintptr
- func (m *HashMap) Get(key interface{}) (value interface{}, ok bool)
- func (m *HashMap) GetHashedKey(hashedKey uintptr) (value interface{}, ok bool)
- func (m *HashMap) GetOrInsert(key interface{}, value interface{}) (actual interface{}, loaded bool)
- func (m *HashMap) GetStringKey(key string) (value interface{}, ok bool)
- func (m *HashMap) GetUintKey(key uintptr) (value interface{}, ok bool)
- func (m *HashMap) Grow(newSize uintptr)
- func (m *HashMap) Insert(key interface{}, value interface{}) bool
- func (m *HashMap) Iter(quit chan struct{}) <-chan KeyValue
- func (m *HashMap) Len() int
- func (m *HashMap) Set(key interface{}, value interface{})
- func (m *HashMap) SetHashedKey(hashedKey uintptr, value interface{})
- func (m *HashMap) String() string
- type KeyValue
- type List
- func (l *List) Add(element *ListElement, searchStart *ListElement) (existed bool, inserted bool)
- func (l *List) AddOrUpdate(element *ListElement, searchStart *ListElement) bool
- func (l *List) Cas(element *ListElement, oldValue interface{}, searchStart *ListElement) bool
- func (l *List) Delete(element *ListElement)
- func (l *List) First() *ListElement
- func (l *List) Head() *ListElement
- func (l *List) Len() int
- type ListElement
Constants ¶
const DefaultSize = 8
DefaultSize is the default size for a zero allocated map
const MaxFillRate = 50
MaxFillRate is the maximum fill rate for the slice before a resize will happen.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type HashMap ¶
type HashMap struct {
// contains filtered or unexported fields
}
HashMap implements a read optimized hash map.
func (*HashMap) Cas ¶
Cas performs a compare and swap operation sets the value under the specified hash key to the map. An existing item for this key will be overwritten.
func (*HashMap) CasHashedKey ¶
CasHashedKey performs a compare and swap operation sets the value under the specified hash key to the map. An existing item for this key will be overwritten.
func (*HashMap) DelHashedKey ¶
DelHashedKey deletes the hashed key from the map.
func (*HashMap) Get ¶
Get retrieves an element from the map under given hash key. Using interface{} adds a performance penalty. Please consider using GetUintKey or GetStringKey instead.
func (*HashMap) GetHashedKey ¶
GetHashedKey retrieves an element from the map under given hashed key.
func (*HashMap) GetOrInsert ¶
GetOrInsert 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.
func (*HashMap) GetStringKey ¶
GetStringKey retrieves an element from the map under given string key.
func (*HashMap) GetUintKey ¶
GetUintKey retrieves an element from the map under given integer key.
func (*HashMap) Grow ¶
Grow resizes the hashmap to a new size, gets rounded up to next power of 2. To double the size of the hashmap 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 (*HashMap) Insert ¶
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 Set, the item might show up in the map only after the resize operation is finished. Returns true if the item was inserted or false if it existed.
func (*HashMap) Iter ¶
Iter returns an iterator which could be used in a for range loop. The order of the items is sorted by hash keys.
func (*HashMap) Set ¶
func (m *HashMap) Set(key interface{}, value interface{})
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 only after the resize operation is finished.
func (*HashMap) SetHashedKey ¶
SetHashedKey sets the value under the specified hash key to the map. An existing item for this key will be overwritten. You can use this function if your keys are already hashes and you want to avoid another hashing of the key. Do not use non hashes as keys for this function, the performance would decrease! If a resizing operation is happening concurrently while calling Set, the item might show up in the map only after the resize operation is finished.
type KeyValue ¶
type KeyValue struct {
Key interface{}
Value interface{}
}
KeyValue represents a key/value that is returned by the iterator.
type List ¶
type List struct {
// contains filtered or unexported fields
}
List is a sorted doubly linked list.
func (*List) Add ¶
func (l *List) Add(element *ListElement, searchStart *ListElement) (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) AddOrUpdate ¶
func (l *List) AddOrUpdate(element *ListElement, searchStart *ListElement) bool
AddOrUpdate adds or updates an item to the list.
func (*List) Cas ¶
func (l *List) Cas(element *ListElement, oldValue interface{}, searchStart *ListElement) bool
Cas compares and swaps the value of an item in the list.
func (*List) Delete ¶
func (l *List) Delete(element *ListElement)
Delete deletes an element from the list.
type ListElement ¶
type ListElement struct {
// contains filtered or unexported fields
}
ListElement is an element of a list.
func (*ListElement) Next ¶
func (e *ListElement) Next() *ListElement
Next returns the item on the right.
func (*ListElement) Previous ¶
func (e *ListElement) Previous() *ListElement
Previous returns the item on the left.
func (*ListElement) Value ¶
func (e *ListElement) Value() (value interface{})
Value returns the value of the list item.
Source Files