PaC-trees: supporting parallel and compressed purely-functional collections
Laxman Dhulipala, Guy E. Blelloch, Yan Gu, Yihan Sun · 2022
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.