
arXiv: 2008.01009
The design and implementation of efficient concurrent data structures have seen significant attention. However, most of this work has focused on concurrent data structures providing good \emph{worst-case} guarantees. In real workloads, objects are often accessed at different rates, since access distributions may be non-uniform. Efficient distribution-adaptive data structures are known in the sequential case, e.g. the splay-trees; however, they often are hard to translate efficiently in the concurrent case. In this paper, we investigate distribution-adaptive concurrent data structures and propose a new design called the splay-list. At a high level, the splay-list is similar to a standard skip-list, with the key distinction that the height of each element adapts dynamically to its access rate: popular elements ``move up,'' whereas rarely-accessed elements decrease in height. We show that the splay-list provides order-optimal amortized complexity bounds for a subset of operations while being amenable to efficient concurrent implementation. Experimental results show that the splay-list can leverage distribution-adaptivity to improve on the performance of classic concurrent designs, and can outperform the only previously-known distribution-adaptive design in certain settings.
FOS: Computer and information sciences, Data structures, 000, self-adjusting data structures, 004, self-adjusting, Computer Science - Distributed, Parallel, and Cluster Computing, Theory of computation → Concurrent algorithms, Computer Science - Data Structures and Algorithms, concurrency, Data Structures and Algorithms (cs.DS), Distributed, Parallel, and Cluster Computing (cs.DC), Theory of computation → Data structures design and analysis, ddc: ddc:004
FOS: Computer and information sciences, Data structures, 000, self-adjusting data structures, 004, self-adjusting, Computer Science - Distributed, Parallel, and Cluster Computing, Theory of computation → Concurrent algorithms, Computer Science - Data Structures and Algorithms, concurrency, Data Structures and Algorithms (cs.DS), Distributed, Parallel, and Cluster Computing (cs.DC), Theory of computation → Data structures design and analysis, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
