PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections

Laxman Dhulipala, Guy E. Blelloch, Yan Gu, Yihan Sun

Abstract

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.

Introduction: The "Space Tax" of Functional Data Structures

In modern data processing, purely-functional data structures are highly desirable due to their immutability, which makes them inherently thread-safe and allows for instantaneous snapshots. These properties enable a stream of updates to continue on one version of a database while a separate version is held for analysis, all without complex locking mechanisms.

However, standard functional trees, such as those in the PAM library, suffer from a significant "space tax." Because every element is stored in its own tree node, the overhead is massive: an 8-byte integer may require 24–32 bytes of pointers and metadata. For large-scale analytics like graph processing or search indices, this overhead often makes functional approaches impractical compared to static compressed arrays. The challenge lies in achieving the memory density of a compressed array without sacrificing the flexible, parallel-friendly nature of a tree.

The PaC-tree Architecture

The core innovation of this work is the PaC-tree (Parallel Compressed tree) and the associated CPAM C++ library. The structure shifts the functional boundary from individual elements to blocks of elements.

Comparison of tree structures: (a) P-tree in PAM, (b) B-tree, (c) C-tree in Aspen, and (d) PaC-tree, which compresses leaves in a BST.

Key structural features include:

  1. Blocked Leaves: Instead of a standard Binary Search Tree (BST) where every leaf is a single element, PaC-trees use "flat nodes"—contiguous arrays containing between $B$ and $2B$ elements (typically $B=128$).
  2. Difference Encoding (DE): Within these blocks, sorted integer keys are compressed by storing only the differences (deltas) between consecutive elements, exploiting the small gaps common in sorted data.
  3. Join-Based Framework: Most tree operations (union, intersect, filter) are implemented using a "join" primitive. The authors redesigned join and expose to handle the transition between internal nodes and compressed blocks transparently, allowing high-level parallel algorithms to remain unchanged.
  4. Efficient Augmentation: Functional trees often store augmented values (like subtree sums) at every node. PaC-trees store only one augmented value per block, further reducing memory overhead.

Key Insights

  • The "Sweet Spot" of Blocking: By using $B=128$, only about 1% of the memory is spent on tree metadata, eliminating the vast majority of pointer overhead.
  • Cache Locality: Storing elements in blocks improves cache performance during scans and filters compared to the pointer-chasing required by standard trees.
  • Deterministic Compression: Unlike previous structures like C-trees in Aspen that rely on randomization, PaC-trees are deterministic, providing consistent theoretical bounds on work and space.

Experimental Results

The authors evaluated CPAM against several baselines, including PAM, Aspen, and Intel’s Parallel STL, using microbenchmarks, Wikipedia inverted indices, and massive real-world graphs like Twitter (2.4B edges) and Friendster (3.6B edges).

Memory efficiency of CPAM (PaC-tree) compared to PAM (P-tree), Aspen, and GBBS across various datasets.
  • Memory Efficiency: CPAM consistently uses approximately 1/4 the space of the PAM library for uncompressed data. With difference encoding enabled, it uses 2.1x to 7.8x less space than PAM.
  • Performance: Despite the overhead of block compression/decompression, CPAM is often faster than PAM because the reduced memory footprint leads to fewer cache misses.
  • Graph Processing: Compared to Aspen, a state-of-the-art graph streaming system, CPAM is 1.6x faster at batch updates while using 1.3x to 2.6x less memory.
  • Scalability: The system demonstrates excellent parallel scaling, achieving up to 100x speedup on a 72-core machine for various primitives.

Conclusion

PaC-trees successfully bridge the gap between the efficiency of compressed arrays and the flexibility of purely-functional trees. By blocking leaves and utilizing difference encoding, the CPAM library provides a high-performance, memory-efficient alternative for large-scale functional data analysis. Future work includes exploring higher fan-out internal nodes (like B-trees) and evaluating PaC-trees on persistent/non-volatile memory hardware.

Summary updated

Abstract

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.
BibTeX
@inproceedings{dhulipala2022pac,
  author = {Laxman Dhulipala and Guy E. Blelloch and Yan Gu and Yihan Sun},
  title = {{PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections}},
  booktitle = {PLDI},
  year = {2022},
  doi = {10.1145/3519939.3523733},
}
Figure