An Implementation and Experimental Comparison of Dynamic Ordered Sets

It is becoming increasingly difficult to improve the performance of a a single process (thread) on a computer due to physical limitations. Modern systems use multi-core processors in which multiple processes (threads) may run concurrently. A lock-free data structure can allow these processes to communicate with each other without requiring mutual exclusion, and may increase the amount of work they may perform in parallel rather than sequentially, thus improving the performance of the system as a whole. This paper contains an implementation of Ko's Lock-Free Binary Trie, which stores a dynamic set of keys from an ordered universe. It supports insert, remove, search and predecessor operations. One novel component of this implementation is a lock-free linked list which allows multiple processes to attempt to insert the same node, but which prevents a node from being reinserted once it has been removed from the list. The final section of this paper contains an experimental comparison of this implementation against other data structures which implement the same abstract data type (ADT) as the lock-free trie. Analysis of these experiments reveal that the implementation of Ko's Trie performs better than existing theoretical implementations of this ADT when the universe of keys is large, when removes are rare and when the number of processes performing operations concurrently is low.