City Research Online

Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures

Aksenov, V. ORCID: 0000-0001-9134-5490, Anoprenko, M., Fedorov, A. & Spear, M. (2023). Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures. In: Leibniz International Proceedings in Informatics. International Symposium on Distributed Computing (DISC), 10-12 Oct 2023, L'Aquila, Italy. doi: 10.4230/LIPIcs.DISC.2023.35


Batching is a technique that stores multiple keys/values in each node of a data structure. In sequential search data structures, batching reduces latency by reducing the number of cache misses and shortening the chain of pointers to dereference. Applying batching to concurrent data structures is challenging, because it is difficult to maintain the search property and keep contention low in the presence of batching. In this paper, we present a general methodology for leveraging batching in concurrent search data structures, called BatchBoost. BatchBoost builds a search data structure from distinct “data” and “index” layers. The data layer's purpose is to store a batch of key/value pairs in each of its nodes. The index layer uses an unmodified concurrent search data structure to route operations to a position in the data layer that is “close” to where the corresponding key should exist. The requirements on the index and data layers are low: with minimal effort, we were able to compose three highly scalable concurrent search data structures based on three original data structures as the index layers with a batched version of the Lazy List as the data layer. The resulting BatchBoost data structures provide significant performance improvements over their original counterparts.

Publication Type: Conference or Workshop Item (Paper)
Additional Information: © Vitaly Aksenov, Michael Anoprenko, Alexander Fedorov, and Michael Spear; licensed under Creative Commons License CC-BY 4.0
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology > Computer Science
[thumbnail of LIPIcs.DISC.2023.35.pdf]
Text - Published Version
Available under License Creative Commons Attribution.

Download (646kB) | Preview


Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email


Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login