Summary
Watermelon is an incomplete concurrent, lock-free implementation of unordered associative arrays in C++. Watermelon exposes supports all the same operations as std::unordered_map, making it an easy drop-in replacement when parallelizing single-threaded code.
Background
Associative arrays, more commonly referred to as dictionaries, are a vital part of modern software systems. Associative arrays are commonly implemented using hash tables, which even distribute keys across an random-access table. Unlike trees or linked lists, because the keys are so evenly distributed across the hash table, concurrent access to a hash table has low average contention.
std::unordered_map supports the normal insertion, deletion, and lookup operations. It also supports iteration, assignment, equality, and swap operations, along with several specializations to decrease the number of data copies. However, std::unordered_map is not thread-safe, and so requires external locking to be used in multi-threaded programs.
Approach
Watermelon implements associative arrays with hash tables with closed addressing and separate chaining. Each bucket in the underlying array contains a linked-list which contains the key-value pairs stored by the user. Keys are matched to buckets in the usual way with a hash function modulo the table size.
The linked-lists for each bucket are singly-linked, which allows simple data-structure invariants to be maintained more easily. However, singly-linked lists make node deletion challenging. So instead, nodes are marked for deletion manually by setting a per-node state variable. Once this variable is set, subsequent traversals of the list will ignore this node.
Nodes are reclaimed once the occupancy of the hash table (including 'deleted' nodes) grows too high. A new table is allocated, all nodes from the old table are copied to the new table, and then the old nodes are deleted en masse. Memory is managed with a per-table shared pointer, which prevents any memory from being deallocated before all threads have finished using it.
While the copy operation takes place, all threads operate on both the old and new tables, short-circuiting their work where applicable. The copying thread additionally marks nodes as copied using the state variable to allow subsequent threads to delete elements while the copy takes place.
Results
I was unable to complete the project. C++ is a devil of a language, and attempting to debug the heavily-templated code necessary for compatibility with std::unordered_map ruined my life. As it stands right now, table resizing and recycling are not fully supported, nor are swap semantics.
Furthermore, std::unordered_map returns iterators for every function call. However, in my implementation, iterators are invalidated on certain deletions and on resize operations, so on a resize, no useful work can be performed.
I was not able to get a full test suite working, but I performed preliminary testing, comparing Watermelon to an std::unordered_map protected by an std::mutex. The std::unordered_map outperformed Watermelon by a factor of 3.