Concurrent Unrolled Skiplist
Kenneth Platz, Neeraj Mittal, Subbarayan Venkatesan · 2019
Skiplist is an important data structure used for storing and managing ordered data. It provides logarithmic time complexity (in list size) for lookup, insert and remove operations with high probability without the need for complex balancing actions. Several algorithms have been proposed for concurrent maintenance of a skiplist using both blocking and non-blocking synchronization techniques. In this work, we propose a new algorithm for maintaining a concurrent skiplist that uses two techniques to boost performance. The first technique, referred to as "unrolling", involves storing multiple key-value pairs in the same node. The second technique involves using an advanced locking primitive, based on "group mutual exclusion", to allow certain operations to work on the same node concurrently. In our experiments, our concurrent skiplist consistently outperformed existing concurrent skiplists by as much as 90% in some cases.