Skip to main content

Efficient tree-traversals: reconciling parallelism and dense data representations

Koparkar, Chaitanya, Rainey, Mike, Vollmer, Michael, Kulkarni, Milind, Newton, Ryan R. (2021) Efficient tree-traversals: reconciling parallelism and dense data representations. Proceedings of the ACM on Programming Languages, 5 (ICFP). Article Number 91. ISSN 2475-1421. (doi:10.1145/3473596) (KAR id:95504)

PDF Publisher pdf
Language: English

Download (683kB)
[thumbnail of parallel_gibbon.pdf]
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL:


Recent work showed that compiling functional programs to use dense, serialized memory representations

for recursive algebraic datatypes can yield significant constant-factor speedups for sequential programs. But serializing data in a maximally dense format consequently serializes the processing of that data, yielding a tension between density and parallelism. This paper shows that a disciplined, practical compromise is possible. We present Parallel Gibbon, a compiler that obtains the benefits of dense data formats and parallelism. We formalize the semantics of the parallel location calculus underpinning this novel implementation strategy, and show that it is type-safe. Parallel Gibbon exceeds the parallel performance of existing compilers for purely functional programs that use recursive algebraic datatypes, including, notably, abstract-syntax-tree traversals as in compilers.

Item Type: Article
DOI/Identification number: 10.1145/3473596
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Funders: Engineering and Physical Sciences Research Council (
Depositing User: Michael Vollmer
Date Deposited: 06 Dec 2022 16:52 UTC
Last Modified: 09 Dec 2022 10:16 UTC
Resource URI: (The current URI for this page, for reference purposes)
Vollmer, Michael:
  • Depositors only (login required):


Downloads per month over past year