Lockless hash trie
Description
Environment
None
Gliffy Diagrams
Activity
Show:
Details
Details
Assignee
Philipp Koerner
Philipp KoernerReporter
Philipp Koerner
Philipp KoernerPriority
Created March 18, 2015 at 2:53 PM
Updated March 18, 2015 at 2:53 PM
The hash trie uses semaphores for locking to manage concurrency in shared memory. We could use CAS semantics, if the links (indices in arrays) in a node are tagged with an additonal bit. E.g. values < 0 could be reserved for other nodes and values >= 0 for hash codes.
This would mess with additional infomartion because usually a CAS is only supported for up to eight byte. Fine-grained locking (on hash-code basis via CAS on the checked/unchecked byte) could be used. Another solution would be immutable tuples of hash code and information that are controlled via a more sophisticated memory management.