“High Performance C++ Concurrent Transactional Data Structures"

on YouTube ↗55m

" summary

Detailed implementations and measured claims: a lock manager MRLock uses a lock-free FIFO queue of bitset requests as a drop-in replacement for std::lock/boost::lock and shows up to 3×–5× speedup over hierarchy locks under high contention; a lock-free transactional transform LFTT embeds a transaction descriptor in nodes so helpers complete pending work, avoids rollbacks and reports ~60% throughput over boosting and ~3× over STM; a multi-dimensional list keeps updates to at most two nodes, yields up to 100% faster maps on write-heavy workloads, and reduces spurious aborts.

AI-written summary · about

" chapters (38)

1. 0:00Intro
2. 1:34Non-blocking Data Structures
3. 3:25The Catch: Composite Operations
4. 5:45Transactional Data Structures
5. 6:27Software Transactional Memory (STM)
6. 8:11Transactional Boosting Herlihy and Koskinen, 2008
7. 10:04Methodology Overview
8. 11:14Implementation Techniques
9. 12:27Transaction Synchronization as Resource Allocation
10. 13:11Acquiring Multiple Locks
11. 14:13Extended TATAS
12. 15:15Queue-based Multi-resource Lock
13. 17:10Lock Acquire
14. 17:57Lock Release
15. 18:37Sequence Number
16. 20:41Challenges for Lock-free Transactions
17. 21:46LFTT Overview
18. 22:46Node-based Conflict Detection
19. 23:45Transformed INSERT Workflow
20. 25:17Interpretation-based Logical Rollback
21. 26:28Cooperative Transaction Execution
22. 32:45Concurrent Map
23. 36:27Coordinate Mapping
24. 38:10Find Operation
25. 39:08Insert - 2 Steps
26. 40:44Normal Delete Does Not Work
27. 41:31Asymmetrical Delete-Decoupled Physical Removal
28. 42:15Abstract State
29. 42:50Environment
30. 43:4916 Threads
31. 45:18Thread Scale
32. 46:13Alternatives
33. 46:40Throughput - Skiplist Mixed Workload
34. 48:23Throughput - Linked List Mixed Workload
35. 50:52Dimension Sweep
36. 51:35Scalability Summary
37. 52:01Libtxd Architecture
38. 52:55Future Development

" related talks

• 01h 03mA Multi-threaded, Transaction-Based Locking Strategy for ContainersBob Steagall · CppCon 2020
• 26mConcurrency: Unlocking a SolutionRanadheer Pulluru, Angila Talreja · Great International Developer Summit 2023
• 01h 30mLive Lock-Free or Deadlock (Practical Lock-free Programming)Fedor Pikus · CppCon 2015
• 01h 03mIntro to Concurrent Programming 3/3: Relaxed Data Structures for Parallel AlgorithmsNikita Koval · Hydra 2022
• 01h 11mLock-Free Programming (or, Juggling Razor Blades), Part IIHerb Sutter · CppCon 2014
• 01h 08mThinking Outside the Synchronisation QuadrantKevlin Henney · NDC London 2017
• 21mEvery Data Structure Deserves Lock-Free Memory ReclamationNachshon Cohen · OOPSLA 2018
• 01h 08mBetter Code: ConcurrencySean Parent · NDC London 2017