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