Design and Implementation of Highly Scalable Quantifiable Data Structures in C++
summary
Claims a new correctness condition, quantifiability, and ships lock‑free C++ implementations of a QStack and QQueue using compare_exchange_strong and descriptor objects; pending pops become stored “negative” entries and forks/branching reduce contention. A runtime verifier, Vector Space Verification (VSV), turns histories into matrices and checks correctness in O(n + i·j) (presented as sub‑quadratic) rather than NP‑complete linearizability checks. Entropy uses Knuth inversion counts and normalized Shannon entropy to quantify correctness/performance tradeoffs; demos on a 32‑core EPYC show QStack scaling far better than Treiber and LCRQ at the cost of increased disorder.
AI-written summary · about
chapters (21)
- 0:00Start
- 1:30Overview
- 1:59Correctness Conditions
- 3:00Linearizability
- 5:35Concurrent Histories
- 11:12Definition of Quantifiability
- 13:12Basis Vector
- 18:51Inspiration from Linearizability
- 20:03Entropy Measurements
- 20:46Quantifiability
- 24:59Stacks
- 29:39Design Goal
- 30:13Conservation of Method Calls
- 30:48Negative Stack
- 31:29Compare and Swap
- 32:23The Quantifiable Stack
- 34:06Descriptor Objects
- 36:56Fork
- 46:29Check Quantifiability
- 48:22Conclusion
- 57:10Memory Allocation
related talks
36mFull Stack. Real Scale. No Bullshit? – A Quantum Reality Check
01h 04mBuilding confidence in concurrent code with a model checker
01h 00mTrading at light speed: designing low latency systems in C++
55mC++ Concurrency TS 2 Use Cases and Future Direction
01h 05mThe Imperatives Must Go!
44mUserspace Assisted Scheduling via Sc...
57mHow to Design a Slimmer Vector of Variants in C++
53mAsync sequences and algorithms to compose them