PaC-trees: supporting parallel and compressed purely-functional collections
PaC-trees: supporting parallel and compressed purely-functional collections
复制标题
DOI：
10.1145/3519939.3523733
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Laxman Dhulipala;G. Blelloch;Yan Gu;Yihan Sun
中科院分区：
文献类型：
--
作者：
Laxman Dhulipala;G. Blelloch;Yan Gu;Yihan Sun
许多现代编程语言正在转向集合接口（例如集合、映射和序列）的函数式风格。函数式接口提供了许多优点，包括安全的并行性以及提供简单且轻量级的快照。然而，现有的高性能功能接口（例如基于平衡纯功能树的PAM）由于将每个元素存储在树中的单独节点中，因此在大规模数据分析时会产生大量空间开销。本文介绍了 PaC 树，这是一种支持集合、映射和序列的功能接口的纯功能数据结构，与现有方法相比，它显着减少了空间。 PaC 树是一种平衡二叉搜索树，它将叶子分块并使用数组压缩块。我们提供了用于压缩和解压缩块的新颖技术，这些技术为 PaC 树上的一系列广泛操作（例如并集、交集、过滤、归约和范围查询）产生了实用的并行功能算法，这些算法在理论上和实践上都是高效的。我们使用 PaC-trees 设计了 CPAM，这是一个 C++ 库，它实现了 PAM 的全部功能，同时提供了重要的额外压缩功能。 CPAM 在集合、地图和序列的一组微基准上始终匹配或优于 PAM，同时使用大约四分之一的空间。在倒排索引、2D 范围查询和 1D 区间查询等应用中，CPAM 与 PAM 竞争或更快，同时使用的空间少 2.1--7.8 倍。对于静态和流式图形处理，CPAM 的批量更新速度比最先进的图形处理系统 Aspen 快 1.6 倍，同时使用的空间减少 1.3--2.6 倍。
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.