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, although, in real workloads, objects are often accessed at different rates. Efficient distribution-adaptive data structures, such as splay-trees, are known in the sequential case; however, they often are hard to translate efficiently to the concurrent case. 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. Experiments show that the splay-list can leverage distribution-adaptivity for performance, and can outperform the only previously-known distribution-adaptive concurrent design in certain workloads.
Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive concurrent skip-list. Distributed Computing. 2023;36:395-418. doi:10.1007/s00446-022-00441-x
Aksenov, V., Alistarh, D.-A., Drozdova, A., & Mohtashami, A. (2023). The splay-list: A distribution-adaptive concurrent skip-list. Distributed Computing. Springer Nature. https://doi.org/10.1007/s00446-022-00441-x
Aksenov, Vitalii, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” Distributed Computing. Springer Nature, 2023. https://doi.org/10.1007/s00446-022-00441-x.
V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list: A distribution-adaptive concurrent skip-list,” Distributed Computing, vol. 36. Springer Nature, pp. 395–418, 2023.
Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2023. The splay-list: A distribution-adaptive concurrent skip-list. Distributed Computing. 36, 395–418.
Aksenov, Vitalii, et al. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” Distributed Computing, vol. 36, Springer Nature, 2023, pp. 395–418, doi:10.1007/s00446-022-00441-x.