How common libraries are doing it
- Lookups: lock a segment of the hashtable instead of the entire thing. (
concurrent_hash_map.h) - Inserts: lock the pending element (slot) of the target value, instead of the segment. (
concurrent_hash_map.h) - Updates: RCU the element instead of locking it, allowing updates and reads to happen at the same time, albeit on different versions of the object. RCU also makes the critical section of a update a simple pointer swap. (
viewable_hash_map.h) - Everything: use other lock-free algorithms such as
skip_list_set.h.
Step by step guide
The key is to gradually remove locks while managing element lifecycle.
- Shard the hashtable. Replicate all shard pointers to all threads before hand. Never delete a shard. Lock one shard each time. This is called "segments" above.
- Lock a single element and release the shard lock once it is found.
- Do not lock while reading the element. Read-copy-update (RCU) it.
- Alternatively, wrap your element in
std::shared_ptr. - Remove locks for updates (RCU).
If this still does not work, you should consider using one of the impossible-to-use lock-free datastructures. Remember to manage the lifetime of elements well.