hashmap

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{}
i := 123
m.Set("amount", unsafe.Pointer(&i))

Read a value for a key from the map:

val, ok := m.Get("amount")
if ok {
    amount := *(*int)(val)
}

Use the map to count URL requests:

var i int64
actual, _ := m.GetOrInsert("api/123", unsafe.Pointer(&i))
counter := (*int64)(actual)
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                	 1000000	      6633 ns/op
BenchmarkReadGoMapUintUnsafe-8            	 1000000	      5875 ns/op
BenchmarkReadGoMapUintMutex-8             	  200000	     44339 ns/op
BenchmarkReadGoSyncMapUint-8              	  500000	     14350 ns/op

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

BenchmarkReadHashMapHashedKey-8           	 5000000	      1632 ns/op

Reading from the map while writes are happening:

BenchmarkReadHashMapWithWritesUint-8      	 1000000	      8314 ns/op
BenchmarkReadGoMapWithWritesUintMutex-8   	   50000	    171032 ns/op
BenchmarkReadGoSyncMapWithWritesUint-8    	  200000	     71992 ns/op

Write performance without any concurrent reads:

BenchmarkWriteHashMapUint-8               	   50000	    182276 ns/op
BenchmarkWriteGoMapMutexUint-8            	  200000	     51174 ns/op
BenchmarkWriteGoSyncMapUint-8             	   50000	    124758 ns/op

The benchmarks were run with Golang 1.9 on MacOS.

Technical details

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

• The API uses unsafe.Pointer instead of the common interface{} for the values for faster speed when reading values.

• 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. Golang 1.9 will bring inlining optimizations.

• 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 New(size uintptr) *HashMap
  • func (m *HashMap) Cas(key interface{}, from, to unsafe.Pointer) bool
  • func (m *HashMap) CasHashedKey(hashedKey uintptr, from, to unsafe.Pointer) 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 unsafe.Pointer, ok bool)
  • func (m *HashMap) GetHashedKey(hashedKey uintptr) (value unsafe.Pointer, ok bool)
  • func (m *HashMap) GetOrInsert(key interface{}, value unsafe.Pointer) (actual unsafe.Pointer, loaded bool)
  • func (m *HashMap) GetStringKey(key string) (value unsafe.Pointer, ok bool)
  • func (m *HashMap) GetUintKey(key uintptr) (value unsafe.Pointer, ok bool)
  • func (m *HashMap) Grow(newSize uintptr)
  • func (m *HashMap) Insert(key interface{}, value unsafe.Pointer) bool
  • func (m *HashMap) Iter() <-chan KeyValue
  • func (m *HashMap) Len() int
  • func (m *HashMap) Set(key interface{}, value unsafe.Pointer)
  • func (m *HashMap) SetHashedKey(hashedKey uintptr, value unsafe.Pointer)
  • func (m *HashMap) String() string
• type KeyValue
• type List
  • func NewList() *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 unsafe.Pointer, searchStart *ListElement) bool
  • func (l *List) Delete(element *ListElement)
  • func (l *List) First() *ListElement
  • func (l *List) Len() int
• type ListElement
  • func (e *ListElement) CasValue(from, to unsafe.Pointer) bool
  • func (e *ListElement) Next() *ListElement
  • func (e *ListElement) Previous() *ListElement
  • func (e *ListElement) SetValue(value unsafe.Pointer)
  • func (e *ListElement) Value() (value unsafe.Pointer)

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.

Types

type HashMap

type HashMap struct {
	// contains filtered or unexported fields
}

HashMap implements a read optimized hash map.

func New

func New(size uintptr) *HashMap

New returns a new HashMap instance with a specific initialization size.

func (*HashMap) Cas

func (m *HashMap) Cas(key interface{}, from, to unsafe.Pointer) bool

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

func (m *HashMap) CasHashedKey(hashedKey uintptr, from, to unsafe.Pointer) bool

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) Del

func (m *HashMap) Del(key interface{})

Del deletes the key from the map.

func (*HashMap) DelHashedKey

func (m *HashMap) DelHashedKey(hashedKey uintptr)

DelHashedKey deletes the hashed key from the map.

func (*HashMap) Fillrate

func (m *HashMap) Fillrate() uintptr

Fillrate returns the fill rate of the map as an percentage integer.

func (*HashMap) Get

func (m *HashMap) Get(key interface{}) (value unsafe.Pointer, ok bool)

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

func (m *HashMap) GetHashedKey(hashedKey uintptr) (value unsafe.Pointer, ok bool)

GetHashedKey retrieves an element from the map under given hashed key.

func (*HashMap) GetOrInsert

func (m *HashMap) GetOrInsert(key interface{}, value unsafe.Pointer) (actual unsafe.Pointer, loaded bool)

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

func (m *HashMap) GetStringKey(key string) (value unsafe.Pointer, ok bool)

GetStringKey retrieves an element from the map under given string key.

func (*HashMap) GetUintKey

func (m *HashMap) GetUintKey(key uintptr) (value unsafe.Pointer, ok bool)

GetUintKey retrieves an element from the map under given integer key.

func (*HashMap) Grow

func (m *HashMap) Grow(newSize uintptr)

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

func (m *HashMap) Insert(key interface{}, value unsafe.Pointer) bool

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

func (m *HashMap) Iter() <-chan KeyValue

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) Len

func (m *HashMap) Len() int

Len returns the number of elements within the map.

func (*HashMap) Set

func (m *HashMap) Set(key interface{}, value unsafe.Pointer)

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

func (m *HashMap) SetHashedKey(hashedKey uintptr, value unsafe.Pointer)

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.

func (*HashMap) String

func (m *HashMap) String() string

String returns the map as a string, only hashed keys are printed.

type KeyValue

type KeyValue struct {
	Key   interface{}
	Value unsafe.Pointer
}

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 NewList

func NewList() *List

NewList returns an initialized 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.

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 unsafe.Pointer, 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 marks the list element as deleted.

func (*List) First

func (l *List) First() *ListElement

First returns the first item of the list.

func (*List) Len

func (l *List) Len() int

Len returns the number of elements within the list.

type ListElement

type ListElement struct {
	// contains filtered or unexported fields
}

ListElement is an element of a list.

func (*ListElement) CasValue

func (e *ListElement) CasValue(from, to unsafe.Pointer) bool

CasValue compares and swaps the values of the item.

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) SetValue

func (e *ListElement) SetValue(value unsafe.Pointer)

SetValue sets the value of the item.

func (*ListElement) Value

func (e *ListElement) Value() (value unsafe.Pointer)

Value returns the value of the list item.