Attending this event?
Back To Schedule
Tuesday, October 3 • 14:00 - 15:00
Lock-free Atomic Shared Pointers Without a Split Reference Count? It Can Be Done!

Log in to save this to your schedule, view media, leave feedback and see who's attending!

Log in to leave feedback.
Smart pointers such as std::unique_ptr and std::shared_pointer are the recommended way to manage dynamic memory in C++ programs. At least, that is what we try to teach people. But what if you are writing parallel and concurrent code, can we will make use of std::shared_ptr? Yes, but only if concurrent modifications are done via a std::atomic<std::shared_prt>! Atomic smart pointers were recently introduced to the C++20 standard for this purpose, however, existing implementations in major standard libraries are not lock-free. This makes them impractical for applications with heavy concurrency, as their performance degrades badly.

There are several well known implementations of a lock-free atomic shared pointer, such as Folly's, and Anthony William's which is included in a commercial library. These implementations and several others are all based on the so-called "split reference count" technique, which solves the problem of atomically modifying the reference count and the object pointer when performing an update operation. This technique is difficult to make fully portable however, since it either relies on a double-word compare-exchange operation, or packs a reference count inside the "unused" high-order bits of the pointer.

In this talk, we describe a strategy for implementing lock-free atomic shared pointers without a split reference count. The solution is surprisingly simple and elegant, as it does not require adding any fields to the shared pointer or atomic shared pointer and does not hide anything inside the bits of the pointer. Under the hood, it makes use of hazard pointers and deferred reclamation. Since hazard pointers are on track for inclusion in C++26, this implementation is timely, simple to implement with nearly-standard C++, and achieves excellent performance.

avatar for Daniel Anderson

Daniel Anderson

Assistant Teaching Professor, Carnegie Mellon University
Daniel Anderson is an assistant teaching professor at Carnegie Mellon University, where he recently graduated with a PhD in computer science focusing on parallel computing and parallel algorithms. Daniel teaches algorithms classes to hundreds of undergraduate students and spends his... Read More →

Tuesday October 3, 2023 14:00 - 15:00 MDT
Maple 3/4/5