PaC-trees: supporting parallel and compressed purely-functional collections

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

TL;DR

PaC-trees (Parallel Compressed trees) introduce a hybrid data structure that combines the safety and parallelism of purely-functional trees with the memory efficiency of compressed arrays. By "blocking" leaf nodes and applying difference encoding, the authors achieve up to an 8x reduction in memory usage while matching or exceeding the performance of state-of-the-art functional libraries.

What Problem Does This Paper Address?

In modern data processing, "purely-functional" data structures are highly desirable. Because they are immutable, they are inherently thread-safe and allow for "instant" snapshots—you can keep a version of a database for analysis while a stream of updates continues on a new version without complex locking.

However, there is a "space tax." Standard functional trees (like those in the PAM library) store every single element in its own tree node. This creates massive overhead: for every 8-byte integer you store, you might spend 24–32 bytes on 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 is: how do we get the memory density of a compressed array without losing the flexible, parallel-friendly nature of a tree?

Methods

The authors introduce PaC-trees and an associated C++ library called CPAM. The core innovation is a structural shift:

  1. Blocked Leaves: Instead of a standard Binary Search Tree (BST) where every leaf is a single element, PaC-trees use "flat nodes." These are contiguous arrays containing between $B$ and $2B$ elements (where $B$ is a tunable parameter, typically 128).
  2. Difference Encoding (DE): Within these blocks, the library can compress sorted integer keys by storing only the differences (deltas) between consecutive elements. This exploits the fact that sorted data often has small gaps, which can be represented in fewer bits.
  3. The Join-Based Framework: Most tree operations (union, intersect, filter) are implemented using a "join" primitive. The authors redesigned join and expose (the function that splits a node) to handle the transition between internal nodes and compressed blocks transparently. This allows high-level algorithms to remain unchanged while the underlying structure handles the compression.
  4. Efficient Augmentation: Functional trees often store "augmented" values (like the sum or maximum of a subtree) at every node. PaC-trees only store one augmented value per block, further slashing memory overhead.

Datasets

The authors evaluated CPAM against several baselines (PAM, Aspen, and Intel’s Parallel STL) using:

  • Microbenchmarks: Synthetic sets, maps, and sequences of $10^8$ elements.
  • Inverted Indices: A Wikipedia corpus containing 1.94 billion words across 8.13 million documents.
  • Graph Processing: Several massive real-world graphs, including Twitter (2.4B edges) and Friendster (3.6B edges).
  • Geometric Data: 100 million 2D points for range query benchmarks.

Key Insights and Ideas

  • The "Sweet Spot" of Blocking: By moving the "functional" boundary from individual elements to blocks of elements, the authors eliminate the vast majority of pointer overhead. For $B=128$, only about 1% of the memory is spent on tree metadata.
  • Cache Locality: Standard trees involve pointer-chasing, which is slow. By storing elements in blocks (arrays), PaC-trees significantly improve cache performance during scans and filters.
  • Algorithmic Transparency: One of the most elegant parts of the paper is that by carefully redefining the join and split primitives, they didn't have to rewrite complex parallel algorithms like union. The "blocking" logic is encapsulated at the lowest level.
  • Deterministic Compression: Unlike some previous compressed tree structures (like C-trees in Aspen) that rely on randomization, PaC-trees are deterministic, providing more consistent theoretical bounds on work and space.

Key Results

  • Memory Efficiency: CPAM consistently uses about 1/4 the space of the PAM library for uncompressed data. When difference encoding is enabled, it uses 2.1x to 7.8x less space than PAM.
  • Performance: Despite the overhead of compressing/decompressing blocks, CPAM is often faster than PAM because the reduced memory footprint leads to fewer cache misses.
  • Graph Superiority: 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.

Limitations and Future Work

  • Single-Point Update Cost: Because elements are stored in blocks, inserting a single element requires re-processing an entire block ($O(B + \log n)$). While the authors propose an "in-place" update version to mitigate this, it sacrifices some of the purity of the functional model.
  • Internal Node Fan-out: The current implementation uses binary trees for the internal structure. The authors suggest that moving to a higher fan-out (like a B-tree) for the internal nodes could further reduce the number of cache misses during lookups.
  • Non-Volatile Memory: The authors identify exploring PaC-trees on new hardware, such as persistent/non-volatile memory, as a promising direction for future research.

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},
}

Loading related content...

Figure