C++ Memory Model Meets High-Update-Rate Data Structures
summary
Claims that specialized update-side techniques can match RCU and hazard pointers lead to a concrete prototype: a pair of binary-search trees that perform atomic multi-structure moves via an existence switch indirection and single-store switching, using RCU assign pointer and synchronized RCU for reclamation. The prototype runs and scales but is not production ready: early runs show 3.7x (old build) and 12.7x throughput on 60 CPUs for worst-case moves, 39.9x on a mixed workload and 8.5x for lookups on 60 CPUs, with allocator and user-space RCU work remaining.
AI-written summary · about
chapters (11)
- 0:00Intro
- 4:22Atomic Multi-Structure Update: Issaquah Challenge
- 6:22Parallel Processing Workhorse Hash Tables
- 9:35Hardware Structure and Laws of Physics
- 23:43RCU Addition to a Unked Structure
- 31:11Synchronization Without Changing Machine State???
- 40:47Locking Regions for Binary Search Tree
- 43:08Example Existence Structure Before Switch
- 53:13Abbreviated Existence Switch Operation (206)
- 55:05Abbreviated Existence Switch Operation (46)
- 56:54Abbreviated Allegiance Switch Operation (6/6)
related talks
01h 01mSmarter Cpp Atomic Smart Pointers - Efficient Concurrent Memory Management
17mArctic: A Practical Lock-Free Adaptive Radix Tree
17mA New Radix-Tree Based Memory Storage Engine
01h 07mEmerging Embdedded Memories and Storage
45mBeyond Lists: High Performance Data Structures
18mCuckoo for Clients: Disaggregated Cuckoo Hashing
48mC++ Data Structures That Make Video Games Go Round
01h 02m“Lightweight Object Persistence With Relocatable Heaps in Modern C++"