“Beyond the Issaquah Challenge: High-Performance Scalable Complex Updates"
summary
Extends the Issaquah Challenge into a general method that atomically moves groups of elements among linked structures by combining RCU read-side traversal with a single-store indirection layer of existence structures (tagged pointers) to flip element presence across many containers. Implements rotations and kaleidoscopic updates (multi-state flips), demonstrates linear read scalability up to ~32 CPUs, shows worst-case update slowdown and allocator pressure (needed a special-purpose allocator), achieves prototype correctness and reasonable performance but is not yet production-ready.
AI-written summary · about
chapters (22)
- 0:00Intro
- 0:45The Issaquah Challenge
- 3:00Parallel Updates
- 3:56Laws of Physics
- 4:54Two Fundamental Laws
- 6:32Abstraction
- 10:45Insertion
- 16:48Networking stacks
- 19:10Readonly traversal
- 20:42Tree traversal
- 22:19Existence structure
- 24:31Application to 2014 problem
- 37:58Performance
- 38:40Scale Loading
- 41:35More Elements
- 43:22State Variable
- 46:48Loop
- 48:11Advantages
- 50:15What would you use this
- 51:34Software production readiness
- 54:10Summary
- 56:05Reading protection
related talks
01h 08mRead, Copy, Update, then what? RCU for non-kernel programmers
43mC++ Atomics...
01h 05mNo Touchy! A Case Study of Software Architecture with Immutable Objects
28mRevisit Multi-Reader Synchronizations for Scalable Applications
56m“High-Radix Concurrent C++”
01h 06m“How to make your data structures wait-free for reads"
39mThe best multicore-parallelization refactoring you've never heard of
20mRRR-SMR: Reduce, Reuse, Recycle: Better Methods for Practical Lock-Free Data Structures