SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Thu 21 Oct 2021 14:05 - 14:20 at Zurich G - PLDI 2021 Papers 2 Chair(s): Michael D. Bond

We present a family of new safe memory reclamation schemes, Hyaline, which are fast, scalable, and transparent to the underlying lock-free data structures. Hyaline is based on reference counting – considered impractical for memory reclamation in the past due to high overheads. Hyaline uses reference counters only during reclamation, but not while accessing individual objects, which reduces overheads for object accesses. Since with reference counters, an arbitrary thread ends up freeing memory, Hyaline’s reclamation workload is (almost) balanced across all threads, unlike most prior reclamation schemes such as epoch-based reclamation (EBR) or hazard pointers (HP). Hyaline often yields (excellent) EBR-grade performance with (good) HP-grade memory efficiency, which is a challenging trade-off with all existing schemes.

Hyaline schemes offer the following properties: (i) high \emph{performance}; (ii) good memory \emph{efficiency}; (iii) \emph{robustness}: guaranteeing bounded memory usage even in the presence of stalled threads, a well-known problem with EBR; (iv) \emph{transparency}: supporting virtually unbounded number of threads (or any concurrent entities) that can be created and deleted dynamically, and effortlessly join existent workload; (v) \emph{autonomy}: are neither intrusive to runtime or compiler environments nor rely on OS mechanisms; (vi) \emph{simplicity}: API enables easy integration into unmanaged C/C++ code, while not causing any undue burden on programmers, making the entire process fully automatic through smart pointers; and (vii) \emph{generality}: supporting many data structures. All existing schemes lack one or more properties.

We have implemented and tested Hyaline on x86(-64), ARM32/64, PowerPC, and MIPS. The general approach requires LL/SC or double-width CAS, while a specialized version also works with single-width CAS. Our evaluation reveals that Hyaline’s throughput is very high – it steadily outperforms EBR by 10% in one test and yields \textbf{2x} gains in oversubscribed scenarios. Hyaline’s superior memory efficiency is especially evident in read-dominated workloads.

Thu 21 Oct

Displayed time zone: Central Time (US & Canada) change

13:50 - 15:10
PLDI 2021 Papers 2SIGPLAN Papers at Zurich G
Chair(s): Michael D. Bond Ohio State University, USA
13:50
15m
Talk
Concurrent Deferred Reference Counting for Non-garbage-collected Languages
SIGPLAN Papers
Daniel Anderson Carnegie Mellon University, Guy E. Blelloch Carnegie Mellon University, USA, Yuanhao Wei Carnegie Mellon University, USA
14:05
15m
Talk
Snapshot-Free, Transparent, and Robust Memory Reclamation for Lock-Free Data Structures
SIGPLAN Papers
Ruslan Nikolaev Virginia Tech, Binoy Ravindran Virginia Tech
14:20
15m
Talk
SyRust: Automatic Testing of Rust Libraries with Semantic-Aware Program Synthesis
SIGPLAN Papers
Yoshiki Takashima Carnegie Mellon University, Ruben Martins Carnegie Mellon University, Limin Jia Carnegie Mellon University, Corina S. Păsăreanu Carnegie Mellon University
14:35
15m
Talk
Vectorized Secure Evaluation of Decision Forests
SIGPLAN Papers
Raghav Malik Purdue University, Vidush Singhal Purdue University, Benjamin Gottfried Purdue University, Milind Kulkarni Purdue University
14:50
20m
Live Q&A
Discussion, Questions and Answers
SIGPLAN Papers