Wed 15 Jun 2022 11:40 - 12:00 at Toucan - Memory Chair(s): Clément Pit-Claudel
Wed 15 Jun 2022 23:40 - 00:00 at Toucan - Memory

Many modern programming languages are shifting toward a functional style for collection interfaces such as sets, maps, and sequences. Functional interfaces offer many advantages, including being safe for parallelism and providing simple and lightweight snapshots. However, existing high-performance functional interfaces such as PAM, which are based on balanced purely-functional trees, incur large space overheads for large-scale data analysis due to storing every element in a separate node in a tree.

This paper presents PaC-trees, a purely-functional data structure supporting functional interfaces for sets, maps, and sequences that provides a significant reduction in space over existing approaches. A PaC-tree is a balanced binary search tree which blocks the leaves and compresses the blocks using arrays. We provide novel techniques for compressing and uncompressing the blocks which yield practical parallel functional algorithms for a broad set of operations on PaC-trees such as union, intersection, filter, reduction, and range queries which are both theoretically and practically efficient.

Using PaC-trees we designed CPAM, a C++ library that implements the full functionality of PAM, while offering significant extra functionality for compression. CPAM consistently matches or outperforms PAM on a set of microbenchmarks on sets, maps, and sequences while using about a quarter of the space. On applications including inverted indices, 2D range queries, and 1D interval queries, CPAM is competitive with or faster than PAM, while using 2.1–7.8x less space. For static and streaming graph processing, CPAM offers 1.6x faster batch updates while using 1.3–2.6x less space than the state-of-the-art graph processing system Aspen.

Wed 15 Jun

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

10:40 - 12:00
MemoryPLDI at Toucan +12h
Chair(s): Clément Pit-Claudel EPFL, AWS
10:40
20m
Talk
Is it Time to Retire Manual Concurrent Memory Reclamation?
PLDI
Daniel Anderson Carnegie Mellon University, Guy E. Blelloch Carnegie Mellon University, Yuanhao Wei Carnegie Mellon University, USA
11:00
20m
Talk
Low-Latency, High-Throughput Garbage Collection
PLDI
Wenyu Zhao Australian National University, Steve Blackburn Google and Australian National University, Kathryn S McKinley Google
DOI
11:20
20m
Talk
Mako: A Low-Pause, High-Throughput Evacuating Collector for Memory-Disaggregated Datacenters
PLDI
Haoran Ma University of California, Los Angeles, Shi Liu UCLA, Chenxi Wang UCLA, Yifan Qiao UCLA, Michael D. Bond Ohio State University, Steve Blackburn Google and Australian National University, Miryung Kim University of California at Los Angeles, USA, Guoqing Harry Xu University of California at Los Angeles
DOI
11:40
20m
Talk
PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
PLDI
Laxman Dhulipala Carnegie Mellon University, Guy E. Blelloch Carnegie Mellon University, Yan Gu UC Riverside, Yihan Sun University of California, Riverside
DOI
22:40 - 00:00
MemoryPLDI at Toucan
22:40
20m
Talk
Is it Time to Retire Manual Concurrent Memory Reclamation?
PLDI
Daniel Anderson Carnegie Mellon University, Guy E. Blelloch Carnegie Mellon University, Yuanhao Wei Carnegie Mellon University, USA
23:00
20m
Talk
Low-Latency, High-Throughput Garbage Collection
PLDI
Wenyu Zhao Australian National University, Steve Blackburn Google and Australian National University, Kathryn S McKinley Google
DOI
23:20
20m
Talk
Mako: A Low-Pause, High-Throughput Evacuating Collector for Memory-Disaggregated Datacenters
PLDI
Haoran Ma University of California, Los Angeles, Shi Liu UCLA, Chenxi Wang UCLA, Yifan Qiao UCLA, Michael D. Bond Ohio State University, Steve Blackburn Google and Australian National University, Miryung Kim University of California at Los Angeles, USA, Guoqing Harry Xu University of California at Los Angeles
DOI
23:40
20m
Talk
PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
PLDI
Laxman Dhulipala Carnegie Mellon University, Guy E. Blelloch Carnegie Mellon University, Yan Gu UC Riverside, Yihan Sun University of California, Riverside
DOI