The splay-list: A distribution-adaptive concurrent skip-list

V. Aksenov, D.-A. Alistarh, A. Drozdova, A. Mohtashami, ArXiv (n.d.).

Preprint | Submitted | English
Author
Aksenov, Vitaly; Alistarh, Dan-AdrianIST Austria; Drozdova, Alexandra; Mohtashami, Amirkeivan
Department
Abstract
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.
Publishing Year
Date Published
2020-08-03
Journal Title
arXiv
Article Number
2008.01009
IST-REx-ID

Cite this

Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive concurrent skip-list. arXiv.
Aksenov, V., Alistarh, D.-A., Drozdova, A., & Mohtashami, A. (n.d.). The splay-list: A distribution-adaptive concurrent skip-list. arXiv.
Aksenov, Vitaly, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” ArXiv, n.d.
V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list: A distribution-adaptive concurrent skip-list,” arXiv. .
Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive concurrent skip-list. arXiv, 2008.01009.
Aksenov, Vitaly, et al. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” ArXiv, 2008.01009.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 2008.01009

Search this title in

Google Scholar