Write a Blog >>
PLDI 2021
Sun 20 - Sat 26 June 2021 PLDI
Wed 23 Jun 2021 09:25 - 09:30 at PLDI-A - Talks 1A: Concurrent and Distributed Programming
Wed 23 Jun 2021 21:25 - 21:30 at PLDI-A - Talks 1A: Concurrent and Distributed Programming

We present a family of 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: (i) high performance; (ii) good memory efficiency; (iii) robustness: bounding memory usage even in the presence of stalled threads, a well-known problem with EBR; (iv) transparency: supporting virtually unbounded number of threads (or concurrent entities) that can be created and deleted dynamically, and effortlessly join existent workload; (v) autonomy: avoiding special OS mechanisms and being non-intrusive to runtime or compiler environments; (vi) simplicity: enabling easy integration into unmanaged C/C++ code; and (vii) 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 2x gains in oversubscribed scenarios. Hyaline's superior memory efficiency is especially evident in read-dominated workloads.

Wed 23 Jun

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

09:00 - 09:35
Talks 1A: Concurrent and Distributed ProgrammingPLDI at PLDI-A +12h
09:00
5m
Talk
Abstraction for Conflict-Free Replicated Data Types
PLDI
Hongjin Liang Nanjing University, Xinyu Feng Nanjing University
DOI
09:05
5m
Talk
Modular Data-Race-Freedom Guarantees in the Promising Semantics
PLDI
Minki Cho Seoul National University, Sung-Hwan Lee Seoul National University, Chung-Kil Hur Seoul National University, Ori Lahav Tel Aviv University
DOI
09:10
5m
Talk
Viaduct: An Extensible, Optimizing Compiler for Secure Distributed Programs
PLDI
Coşku Acay Cornell University, Rolph Recto Cornell University, Joshua Gancher Cornell University, Andrew C. Myers Cornell University, Elaine Shi Cornell University
DOI Pre-print
09:15
5m
Talk
Canary: Practical Static Detection of Inter-thread Value-Flow Bugs
PLDI
Yuandao Cai Hong Kong University of Science and Technology, Peisen Yao Hong Kong University of Science and Technology, Charles Zhang Hong Kong University of Science and Technology
DOI
09:20
5m
Talk
Practical Smart Contract Sharding with Ownership and Commutativity Analysis
PLDI
George Pîrlea National University of Singapore, Amrit Kumar Zilliqa Research, Ilya Sergey Yale-NUS College; National University of Singapore
DOI
09:25
5m
Talk
Snapshot-Free, Transparent, and Robust Memory Reclamation for Lock-Free Data Structures
PLDI
Ruslan Nikolaev Virginia Tech, Binoy Ravindran Virginia Tech
DOI
09:30
5m
Talk
Concurrent Deferred Reference Counting with Constant-Time Overhead
PLDI
Daniel Anderson Carnegie Mellon University, Guy E. Blelloch Carnegie Mellon University, Yuanhao Wei Carnegie Mellon University
DOI
21:00 - 21:35
Talks 1A: Concurrent and Distributed ProgrammingPLDI at PLDI-A
21:00
5m
Talk
Abstraction for Conflict-Free Replicated Data Types
PLDI
Hongjin Liang Nanjing University, Xinyu Feng Nanjing University
DOI
21:05
5m
Talk
Modular Data-Race-Freedom Guarantees in the Promising Semantics
PLDI
Minki Cho Seoul National University, Sung-Hwan Lee Seoul National University, Chung-Kil Hur Seoul National University, Ori Lahav Tel Aviv University
DOI
21:10
5m
Talk
Viaduct: An Extensible, Optimizing Compiler for Secure Distributed Programs
PLDI
Coşku Acay Cornell University, Rolph Recto Cornell University, Joshua Gancher Cornell University, Andrew C. Myers Cornell University, Elaine Shi Cornell University
DOI Pre-print
21:15
5m
Talk
Canary: Practical Static Detection of Inter-thread Value-Flow Bugs
PLDI
Yuandao Cai Hong Kong University of Science and Technology, Peisen Yao Hong Kong University of Science and Technology, Charles Zhang Hong Kong University of Science and Technology
DOI
21:20
5m
Talk
Practical Smart Contract Sharding with Ownership and Commutativity Analysis
PLDI
George Pîrlea National University of Singapore, Amrit Kumar Zilliqa Research, Ilya Sergey Yale-NUS College; National University of Singapore
DOI
21:25
5m
Talk
Snapshot-Free, Transparent, and Robust Memory Reclamation for Lock-Free Data Structures
PLDI
Ruslan Nikolaev Virginia Tech, Binoy Ravindran Virginia Tech
DOI
21:30
5m
Talk
Concurrent Deferred Reference Counting with Constant-Time Overhead
PLDI
Daniel Anderson Carnegie Mellon University, Guy E. Blelloch Carnegie Mellon University, Yuanhao Wei Carnegie Mellon University
DOI