/LockFreeHashTable

Lock Free Resizable Hash Table Based On Split-Ordered Lists.

Primary LanguageC++

LockFreeHashTable

Lock Free Resizable Hash Table Based On Split-Ordered Lists.

Feature

  • Thread-safe and Lock-free.
  • ABA safe.
  • Support Multi-producer & Multi-consumer.
  • Use Hazard Pointer to manage memory.
  • Lock Free LinkedList base on Harris' ListBasedSet, see also LockFreeLinkedList
  • Resize without waiting.

Benchmark

Magnitude Insert Find Delete Insert&Find&Delete
10K 7.8ms 1.6ms 2.1ms 10.4ms
100K 74.9ms 13.4ms 18.4ms 111.2ms
1000K 961ms 117.8ms 216.1ms 1264.1ms

The above data was tested on my 2013 macbook-pro with Intel Core i7 4 cores 2.3 GHz.

The data of first three column was obtained by starting 8 threads to insert concurrently, find concurrently, delete concurrently, the data of four column was obtained by starting 2 threads to insert, 2 threads to find, 2 threads to delete concurrently, each looped 10 times to calculate the average time consumption. See also test.

Build

make && ./test

API

bool Insert(const K& key, const V& value);
bool Insert(const K& key, V&& value);
bool Insert(K&& key, const V& value);
bool Insert(K&& key, V&& value);
bool Find(const K& key, V& value);
bool Delete(const T& data);
size_t size() const;

TODO List

  • Shrink Hash Table without waiting.

Reference

[1]A Pragmatic Implementation of Non-BlockingLinked-Lists. Timothy L.Harris
[2]Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. Maged M. Michael
[3]Split-Ordered Lists: Lock-Free Extensible Hash Tables. Tel-Aviv University and Sun Microsystems Laboratories, Tel-Aviv, Israel