CppCon 2021 has ended
Back To Schedule
Wednesday, October 27 • 3:15pm - 4:15pm
Design and Implementation of Highly Scalable Quantifiable Data Structures in C++

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

Feedback form is now closed.
Architectural imperatives due to the slowing of Moore's Law, the broad acceptance of relaxed semantics and the O(n!) worst case verification complexity of generating sequential histories motivate a new approach to concurrent correctness. Quantifiability is proposed as a novel correctness condition that models a system in vector space to launch a new mathematical analysis of concurrency. Analysis is facilitated with linear algebra, better supported and of much more efficient time complexity than traditional combinatorial methods.

In this talk, we present the design and implementation of a lock-free quantifiable stack (QStack) and a lock-free quantifiable queue (QQueue) in the C++ programming language. Our design achieves lock-freedom using compare_exchange_strong from the C++17 Atomic Operations Library. We depict several code snippets that illustrate how quantifiable data structures are highly scalable through use of relaxed semantics, an explicit implementation trade-off permitted by quantifiability. We explain how to reason about the correctness of quantifiable data structures and present a technique and a dynamic analysis tool developed in C++ for efficiently verifying a concurrent history as quantifiably correct, referred to as Vector Space Verification (VSV). We illustrate why it is impractical to use alternative verification techniques that compare concurrent histories to sequential histories for determining correctness for real programs.

We showcase the performance of quantifiable data structures by presenting a live demonstration that runs the QStack and QQueue and plots the results in real time. The QStack is compared with the lock-free Elimination Backoff Stack and the lock-free Treiber stack. The QQueue is compared with the lock-free LCRQ, and the wait-free Fetch-And-Add queue. The live performance demonstration illustrates how the QStack and QQueue achieve substantially higher scalability than the state-of-the-art linearizable counterparts. We also present a live demonstration of our VSV tool to dynamically check a concurrent history for the QStack and QQueue as quantifiably correct in less than O(n^2) time.

ALL TALK SESSIONS CAN BE ACCESSED FROM THE MAIN LOBBY: https://cppcon.digital-medium.co.uk/

avatar for Victor Cook

Victor Cook

Researcher, University of Central Florida
Victor Cook is a Ph.D. candidate in Computer Science at the University of Central Florida. He received his Bachelor of Science in Geophysics from the Massachusetts Institute of Technology in 1987, and Master of Science in Civil Engineering from the University of Florida in 1989. Mr... Read More →
avatar for Zachary Painter

Zachary Painter

Zachary Painter is a Ph.D. student at the University of Central Florida. His area of research includes concurrent programming, transactional data structures, and blockchain concurrency. His prior work includes a lock-free transactional adjacency list as well as a parallel Hash-Mark-Set... Read More →
avatar for Christina Peterson

Christina Peterson

Postdoctoral Associate, University of Central Florida
Dr. Christina Peterson is a Postdoctoral Associate at the University of Central Florida. Dr. Peterson completed her dissertation work under the supervision of Dr. Damian Dechev with a focus on correctness and progress guarantees of multiprocessor algorithms and data structures. Her... Read More →

Wednesday October 27, 2021 3:15pm - 4:15pm MDT