A Multi-threaded, Transaction-Based Locking Strategy for Containers
summary
Presents a C++17 implementation of strict timestamp ordering for transactional locking on elements (std::vector elements hold an atomic pointer to a transaction manager and a per-element timestamp), using std::mutex, std::condition_variable and atomic operations including compare_exchange_strong. Testbed: 10M items, 100k transactions, update group size 20, 1–16 threads; result: transactional run time grows only ~2× from 1→16 threads on large tables but rollbacks and cost climb as table size shrinks; vector resizing is not supported and starvation is possible.
AI-written summary · about
chapters (11)
- 0:00Introduction and motivation
- 1:14Problem definition and constraints
- 8:27Desired properties of solution
- 13:01Overview of strict timestamp ordering
- 20:05Synchronization components needed
- 22:09Algorithm high-level overview
- 26:21Transaction manager implementation
- 33:03Acquiring elements in update group
- 41:09Testing strategy and race detection
- 50:30Performance results and analysis
- 1:00:18Q&A session
related talks
55m “High Performance C++ Concurrent Transactional Data Structures"
01h 00mConcurrency in C++20: A Deep Dive
01h 07mThe C++20 Synchronization Library
01h 24mConcurrency in C++20 and Beyond
26mConcurrency: Unlocking a Solution
53mAtomics, Locks, and Tasks (part 1 of 2)
01h 04mAtomics, Locks, and Tasks (part 2 of 2)
01h 00mConcurrency Improvements in C++20: A Deep Dive