Yuanhao Wei

General Techniques for Efficient Concurrent Data Structures Degree Type: Ph.D. in Computer Science
Advisor(s): Guy E. Blelloch
Graduated: August 2023

Abstract:

Scalable concurrent data structures are essential for unlocking the potential of modern multicore machines. This thesis presents techniques for enhancing existing concurrent data structures with several useful properties: lock-freedom, the ability to take consistent snapshots, and safe memory management. The goal is to make these techniques widely applicable, easy-to-use, theoretically efficient (i.e. fast in worst-case executions), and also fast in practice.

For lock-freedom, we present a new approach to lock-free locks based on helping, which allows the user to write code using the familiar interface of locks, but run it in a lock-free manner. This thesis presents some key techniques that make lock-free locks practical and more general. We show that our lock-free locks can significantly outperform traditional blocking locks in certain workloads.

We also present an approach for efficiently capturing a consistent view of a concurrent data structure at a single point in time. This is useful for computing linearizable multi-point queries such as searching for a range of keys, finding the first key that matches some criteria, or checking if a collection of keys are all present. Importantly, our approach preserves the time bound and parallelism of the original data structure. It can be applied to both lock-based and lock-free data structures and is compatible with the lock-free locks approach introduced in the first part of the thesis.

Finally, we present a safe automatic memory reclamation approach for concur- rent programs, and show that it is both theoretically and practically efficient. Our approach combines ideas from reference counting and hazard pointers in a novel way to implement concurrent reference counting with wait-free, constant-time overhead. It overcomes the limitations of previous approaches by significantly reducing modifications to, and hence contention on, the reference counts. We further generalize this approach to allow a variety of safe memory reclamation (SMR) schemes to be used as a substitute for hazard pointers. This augments the SMR schemes with ease-of-use while maintaining their performance profiles in terms of time and space.

Thesis Committee:
Guy E. Blelloch (Chair)
Phillip Gibbons
Andy Pavlo
Faith Ellen (University of Toronto)
Panagiota Fatourou (University of Crete)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Concurrency, Lock-freedom, Snapshot, Memory Reclamation, Idempotence, Multiversioning