PPoPP 2024
Sat 2 - Wed 6 March 2024 Edinburgh, United Kingdom
Tue 5 Mar 2024 10:40 - 11:00 at Moorfoot - Synchronization and Concurrency Control 2 Chair(s): Erez Petrank

Van Emde Boas (vEB) trees are sequential data structures optimized for extremely fast predecessor and successor queries. These queries are one of the most important incentives to use ordered sets or maps such as vEB trees. All operations in a vEB tree are doubly logarithmic in the universe size. Attempts to implement concurrent vEB trees have either simplified their structure in a way that eliminated their ability to perform fast predecessor and successor queries, or have otherwise compromised on the doubly logarithmic complexity. In this work, we leverage Hardware Transactional Memory (HTM) to implement vEB tree-based sets and maps in which operations are doubly logarithmic in the absence of contention. Our proposed concurrent vEB tree is the first to implement recursive summaries, the key algorithmic component of fast predecessor and successor operations. Through extensive experiments, we demonstrate that our algorithm outperforms state-of-the-art concurrent maps by an average of 5.4x, the C++ standard ordered map by 70% (1 thread), and even its unordered map by about 15% (1 thread). And, it does so while using two orders of magnitude less memory than traditional vEB trees.

Tue 5 Mar

Displayed time zone: London change

10:00 - 11:00
Synchronization and Concurrency Control 2Main Conference at Moorfoot
Chair(s): Erez Petrank Technion
10:00
20m
Talk
Memory Bounds for Bounded Queues
Main Conference
Nikita Koval JetBrains, Anton Paramonov EPFL, Petr Kuznetsov Telecom Paris, Institut Polytechnique Paris, Vitaly Aksenov City, University of London
Link to publication DOI
10:20
20m
Talk
VERLIB: Concurrent Versioned Pointers
Main Conference
Guy E. Blelloch Carnegie Mellon University, USA, Yuanhao Wei Carnegie Mellon University, USA
Link to publication DOI
10:40
20m
Talk
Practical Hardware Transactional vEB Trees
Main Conference
Mohammad Khalaji University of Waterloo, Trevor Brown University of Waterloo, Khuzaima Daudjee University of Waterloo, Vitaly Aksenov City, University of London
Link to publication DOI