Concurrent Deferred Reference Counting for Non-garbage-collected Languages
We present a safe automatic memory reclamation approach for non garbage-collected languages, and show that it is both theoretically and practically efficient. The approach combines ideas from referencing counting with ideas related to hazard pointers. It overcomes the limitations of previous approaches by significantly reducing modifications to, and hence contention on, the reference counts. The approach is much safer and easier to use than manual approaches such as direct usage of hazard pointers, epoch based reclamation, RCU, or interval-based reclamation. One of the key ideas is a generalization of hazard pointers that allows the same handle to be retired multiple times, which we call acquire-retire. This technique is then used to protect the reference counter of an object, which allows our method to defer decrements on the counter until no other process could be incrementing it. Another key idea is to defer or elide increments of reference counters for short-lived references by temporarily protecting the counter instead of eagerly incrementing it.
We have implemented the approach as a C++ library, which is as simple to use as conventional C++ reference-counted pointers. We run experiments on the library, comparing it to several other methods including state-of-the-art atomic reference-counted pointers, and four manual techniques: hazard-pointers, epochs, hazard-eras and interval-based reclamation. Our results indicate that our technique is faster than existing reference-counted pointer implementations, and competitive with manual memory reclamation techniques. On a variety of data structures and workloads, it achieves throughput rates within a factor of $2$ of the fastest manual approaches, while using a small fraction of the memory. Perhaps most importantly, it is significantly safer since objects are reclaimed automatically.
Thu 21 OctDisplayed time zone: Central Time (US & Canada) change
13:50 - 15:10
|Concurrent Deferred Reference Counting for Non-garbage-collected Languages|
|Snapshot-Free, Transparent, and Robust Memory Reclamation for Lock-Free Data Structures|
|SyRust: Automatic Testing of Rust Libraries with Semantic-Aware Program Synthesis|
|Vectorized Secure Evaluation of Decision Forests|
|Discussion, Questions and Answers|