Designing Wait-free Weak Reference Counting
summary
Claims a wait-free weak reference counting algorithm that lets weak-to-strong promotions terminate regardless of other threads by changing the state machine and encoding strong counts as even numbers with a special odd “close” state. Implementation uses atomic +2/−2 increments for fast paths and a single CAS for closing; systematic testing uncovers and fixes a missing weak-ref transfer bug in an earlier PDI-style design. Verifies the design with Starling and ISMM paper artifacts; microbenchmarks show flattened contention on promotion but a worst-case ~2x work cost that a merged-state variant reduces.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:05Reference counting challenges
- 3:30Progress properties
- 4:37Reference counting state machine
- 6:01Weak to strong promotion performance
- 7:02Wait-free weak reference design
- 9:48Verification with Starling
- 13:36Benchmarking results
- 15:41Lessons from Peter’s office
- 16:25Questions and future applications
related talks
14mMaking Weak Memory Models Fair
17mConcurrent Immediate Reference Counting
19mReference Counting Deeply Immutable Data Structures with Cycles
01h 28mA lock-free std::atomic std::shared_ptr
36mImplementing wait-free space bounded shared memory primitives on concurrent systems
17mPutting Weak Memory in Order via a Promising Intermediate Representation
01h 03mSafety: off --- How not to shoot yourself in the foot with C++ atomics
01h 08mDesigning fast lock free algorithms by understanding cache coherence dynamics