RRR-SMR: Reduce, Reuse, Recycle: Better Methods for Practical Lock-Free Data Structures
summary
Method that lets nodes move between lock free structures without reallocation by combining compare-and-swap tags for ABA safety, a strict ownership model with a fallback search to claim nodes, and a traversal rule like Michael's modification so both EBR and hazard pointers work. Applies to lists, skip lists, hash tables, Natarajan‑Mittal trees and a tuned Michael‑Scott queue. Evaluation on a 128 core AMD server shows up to 10x throughput for 90% recycle 64 KB workloads and reduced memory waste, code available.
AI-written summary · about
chapters (10)
- 0:00Introduction to RRR-SMR
- 0:47Moving objects in lock-free structures
- 3:17Triebel stack and ABA problem
- 6:08Harris linked list and deletion
- 7:31RR-Safe linked list design
- 11:26Recyclable binary search trees
- 13:57Reducing queue memory overhead
- 14:38Evaluation setup and benchmarks
- 16:24Performance results and code
- 16:45Q&A
related talks
21mEvery Data Structure Deserves Lock-Free Memory Reclamation
01h 11mLock-Free Programming (or, Juggling Razor Blades), Part II
17mArctic: A Practical Lock-Free Adaptive Radix Tree
55m “High Performance C++ Concurrent Transactional Data Structures"
55m“A lock-free concurrency toolkit for deferred reclamation and optimistic speculation"
01h 30mLive Lock-Free or Deadlock (Practical Lock-free Programming)
40mKernel Locking Engineering
01h 06m“How to make your data structures wait-free for reads"