Concurrent Deferred Reference Counting with Constant-Time Overhead
We present a safe automatic memory reclamation approach for concurrent programs, and show that it is both theoretically and practically efficient. Our approach combines ideas from referencing counting and hazard pointers in a novel way to implement concurrent reference counting with wait-free, constant-time overhead. It overcomes the limitations of previous approaches by significantly reducing modifications to, and hence contention on, the reference counts. Furthermore, it is safer and easier to use than manual approaches Our technique involves deferring the reference-count decrements until no other process can be incrementing them, and deferring or eliding reference-count increments for short-lived references. This is supported by a novel generalization of hazard pointers. We have implemented the approach as a C++ library and compared it experimentally to several other methods including existing atomic reference-counting libraries, and state-of-the-art manual techniques. Our results indicate that our technique is faster than existing reference-counting implementations, and competitive with manual memory reclamation techniques. More importantly, it is significantly safer than manual techniques since objects are reclaimed automatically.