Faster Lock-Free Atomic Shared Pointers

Abstract

CPU's don't increase in speed anymore, as Moore's Law has claimed for so long. Although, "the free lunch is over" (Herb Sutter), parallel algorithms can gain more throughput and reduce latency, which is crucial to complex real-time applications like audio and video processing, robotics, or real-time sensor data processing in embedded hardware. Parallel algorithms, however, come with the price of concurrency and synchronization. For example, the priority-inversion is a problem, where low-priority threads can block high-priority threads due to locking data structures used by both threads. Lock-free data structures, on the other hand, use atomic CPU instructions to avoid these problems. They, however, are hard to implement and even harder to prove correct. Atomic shared pointers have been proposed as a (part of a) solution to making lock-free algorithms easier to write and verify. Since they are a fundamental tool in the toolbox of parallel algorithms, their run-time performance has a huge trailing impact. So far, there is just a hand-full of existing implementations to atomic shared pointers. This work contributes an improved implementation to atomic shared pointers, a formal proof of its correctness, and an extensive performance evaluation in comparison to other implementations showing that it outperforms others in most use-cases.