A skip list for multicore

摘要

In this paper, we introduce the Rotating skip list, the fastest concurrent skip list to date. Existing concurrent data structures experience limited scalability with the growing core count for two main reasons: threads contend while accessing the same shared data, and they require off-chip communication to synchronize. Our solution combines the rotation of a tree to maintain logarithmic complexity deterministically, a skip list structure to avoid the tree root bottleneck, and no locks to limit cache line bouncing. This combination requires us to trade usual skip list towers for wheels, a novel algorithmic design that favors spatial locality and allows for a constant-time restructuring operation. We evaluate the performance of our skip list on AMD Opteron and Intel Xeon multicores, show that its rotations guarantee its balance and compare its performance against seven state-of-the-art skip lists and trees using four different synchronisation techniques. The Rotating skip list shows an unprecedented peak performance of 200 Mops/second. Copyright (C) 2016 John Wiley & Sons, Ltd.