License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.3
URN: urn:nbn:de:0030-drops-130818
Go to the corresponding LIPIcs Volume Portal

Aksenov, Vitaly ; Alistarh, Dan ; Drozdova, Alexandra ; Mohtashami, Amirkeivan

The Splay-List: A Distribution-Adaptive Concurrent Skip-List

LIPIcs-DISC-2020-3.pdf (0.7 MB)


The design and implementation of efficient concurrent data structures has seen significant attention. However, most of this work has focused on concurrent data structures providing good 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.

BibTeX - Entry

  author =	{Vitaly Aksenov and Dan Alistarh and Alexandra Drozdova and Amirkeivan Mohtashami},
  title =	{{The Splay-List: A Distribution-Adaptive Concurrent Skip-List}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Hagit Attiya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-130818},
  doi =		{10.4230/LIPIcs.DISC.2020.3},
  annote =	{Keywords: Data structures, self-adjusting, concurrency}

Keywords: Data structures, self-adjusting, concurrency
Collection: 34th International Symposium on Distributed Computing (DISC 2020)
Issue Date: 2020
Date of publication: 07.10.2020
Supplementary Material: The code is available at

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI