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 MarDisplayed time zone: London change
10:00 - 11:00 | Synchronization and Concurrency Control 2Main Conference at Moorfoot Chair(s): Erez Petrank Technion | ||
10:00 20mTalk | 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 20mTalk | VERLIB: Concurrent Versioned Pointers Main Conference Link to publication DOI | ||
10:40 20mTalk | 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 |