Write a Blog >>
PPoPP 2022
Sat 2 - Wed 6 April 2022
Wed 6 Apr 2022 12:15 - 12:30 - Session 8 Chair(s): Naama Ben-David

Many concurrent dictionary implementations are designed and optimized for read-mostly workloads with uniformly distributed keys, and often perform poorly on update-heavy workloads. In this work, we first present a concurrent (a,b)-tree, the OCC-ABtree, which outperforms its fastest competitor by up to 2x on uniform update-heavy workloads, and is competitive on other workloads. We then turn our attention to skewed update-heavy workloads (which feature many inserts/deletes on the same key) and introduce the Elim-ABtree, which uses a new optimization called publishing elimination. In publishing elimination, concurrent inserts and deletes to a key are reordered to eliminate them. This reduces the number of writes in the data structure. The Elim-ABtree achieves up to 2.5x the performance of its fastest competitor (including the OCC-ABtree). The OCC-ABtree and Elim-ABtree are linearizable. We also introduce durable linearizable versions (for systems with Intel Optane DCPMM non-volatile main memory) that are nearly as fast.

Wed 6 Apr

Displayed time zone: Eastern Time (US & Canada) change

12:00 - 13:15
Session 8Main Conference
Chair(s): Naama Ben-David VMware
12:00
15m
Talk
Bundling Linked Data Structures for Linearizable Range Queries
Main Conference
Jacob Nelson Lehigh University, Ahmed Hassan Lehigh University, Roberto Palmieri Lehigh University
12:15
15m
Talk
Elimination (a,b)-trees with fast, durable updates
Main Conference
Anubhav Srivastava University of Waterloo, Trevor Brown University of Waterloo
12:30
15m
Talk
Jiffy: A Lock-free Skip List with Batch Updates and Snapshots
Main Conference
Tadeusz Kobus Poznan University of Technology, Maciej Kokociński Poznan University of Technology, Paweł T. Wojciechowski Poznan University of Technology
12:45
15m
Talk
Multi-Queues Can Be State-of-the-Art Priority Schedulers
Main Conference
Anastasiia Postnikova ITMO University, Nikita Koval JetBrains, Giorgi Nadiradze IST Austria, Dan Alistarh IST Austria
13:00
15m
Talk
PathCAS: An Efficient Middle Ground for Concurrent Search Data Structures
Main Conference
Trevor Brown University of Waterloo, William Sigouin University of Waterloo, Dan Alistarh IST Austria