README
¶
hashmap 
Overview
A Golang thread-safe HashMap optimized for fastest lock-free read access on 64 bit systems.
Benchmarks
The benchmarks are run with Golang 1.7.4 on MacOS and amd64 architecture. Reading from the hash map in a thread-safe way is faster than reading from standard Golang map in an unsafe way:
BenchmarkReadHashMap-8 1000000 1637 ns/op
BenchmarkReadGoMapUnsafe-8 1000000 2044 ns/op
BenchmarkReadGoMap-8 50000 28846 ns/op
Writing to the hash map vs a Mutex protected standard Golang map:
BenchmarkWriteHashMap-8 100000 23718 ns/op
BenchmarkWriteGoMap-8 10000 102594 ns/op
The API uses unsafe.Pointer instead of the common interface{} for the values for faster speed when reading values:
BenchmarkUnsafePointer-8 20000000 107 ns/op
BenchmarkInterface-8 10000000 128 ns/op
Hashing algorithm benchmark:
BenchmarkComparisonMD5-8 5000000 257 ns/op 31.06 MB/s
BenchmarkComparisonSHA1-8 5000000 313 ns/op 25.51 MB/s
BenchmarkComparisonSHA256-8 3000000 562 ns/op 14.22 MB/s
BenchmarkComparisonSHA3B224-8 1000000 1359 ns/op 5.88 MB/s
BenchmarkComparisonSHA3B256-8 1000000 1579 ns/op 5.06 MB/s
BenchmarkComparisonRIPEMD160-8 1000000 1106 ns/op 7.23 MB/s
BenchmarkComparisonBlake2B-8 2000000 717 ns/op 11.14 MB/s
BenchmarkComparisonBlake2BSimd-8 2000000 628 ns/op 12.73 MB/s
BenchmarkComparisonMurmur3-8 10000000 139 ns/op 57.47 MB/s
BenchmarkComparisonSipHash-8 10000000 127 ns/op 62.95 MB/s
Technical details
The library uses a sorted linked list and a slice as an index into the 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.
The resize operation uses a lock to ensure that only one resize operation is happening. This way, no CPU and memory resources are wasted by multiple goroutines working on the resize.
Documentation
¶
Index ¶
- Constants
- type HashMap
- func (m *HashMap) Cas(hashedKey uint64, from, to unsafe.Pointer) bool
- func (m *HashMap) Del(key interface{})
- func (m *HashMap) DelHashedKey(hashedKey uint64)
- func (m *HashMap) Fillrate() uint64
- func (m *HashMap) Get(key interface{}) (unsafe.Pointer, bool)
- func (m *HashMap) GetHashedKey(hashedKey uint64) (unsafe.Pointer, bool)
- func (m *HashMap) GetStringKey(key string) (unsafe.Pointer, bool)
- func (m *HashMap) GetUintKey(key uint64) (unsafe.Pointer, bool)
- func (m *HashMap) Grow(newSize uint64)
- func (m *HashMap) Iter() <-chan KeyValue
- func (m *HashMap) Len() uint64
- func (m *HashMap) Set(key interface{}, value unsafe.Pointer)
- func (m *HashMap) SetHashedKey(hashedKey uint64, value unsafe.Pointer)
- func (m *HashMap) String() string
- type KeyValue
- type List
- type ListElement
Constants ¶
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 {
sync.Mutex // mutex that is only used for resize operations
// contains filtered or unexported fields
}
HashMap implements a read optimized hash map.
func (*HashMap) Del ¶
func (m *HashMap) Del(key interface{})
Del deletes the hashed key from the map.
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) 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.
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 ¶
Set sets the value under the specified hash 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 List ¶
type List struct {
// contains filtered or unexported fields
}
List is a sorted list.
func (*List) Add ¶
func (l *List) Add(newElement *ListElement, searchStart *ListElement) bool
Add adds or updates an item to the list.
func (*List) Cas ¶
func (l *List) Cas(newElement *ListElement, oldValue unsafe.Pointer, searchStart *ListElement) bool
Cas compares and swaps the values and add an item to the list.
func (*List) Delete ¶
func (l *List) Delete(element *ListElement)
Delete marks the list element as deleted.
type ListElement ¶
type ListElement struct {
// contains filtered or unexported fields
}
ListElement is an element of the list.
func (*ListElement) CasValue ¶
func (e *ListElement) CasValue(from, to unsafe.Pointer) bool
CasValue compares and swaps the values of the item.
func (*ListElement) Deleted ¶
func (e *ListElement) Deleted() bool
Deleted returns whether the item was deleted.
func (*ListElement) Next ¶
func (e *ListElement) Next() *ListElement
Next returns the item on the right.
func (*ListElement) SetDeleted ¶
func (e *ListElement) SetDeleted(deleted bool) bool
SetDeleted sets the deleted flag of the item.
func (*ListElement) SetValue ¶
func (e *ListElement) SetValue(value unsafe.Pointer)
SetValue sets the value of the item.
func (*ListElement) Value ¶
func (e *ListElement) Value() unsafe.Pointer
Value returns the value of the list item.
Source Files