一句话：提出 Parallel Gibbon 编译器，在稠密序列化数据表示上实现类型安全的并行树遍历，兼顾密度与并行性。
问题：把函数式程序编译为对递归代数数据类型采用稠密、序列化内存表示，虽能显著提升串行程序性能，却会迫使数据处理串行化，导致密度与并行性冲突。方法：提出 Parallel Gibbon 编译器，通过一种有纪律的实用折中同时获得稠密数据格式与并行性；作者形式化了支撑该实现策略的 parallel location calculus 语义，并证明其类型安全。评估：在纯函数式、使用递归代数数据类型的程序上与现有编译器比较并行性能，尤其是编译器中的抽象语法树遍历，Parallel Gibbon 的并行性能更优。
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.
@article{paperbot1132,
title = {Efficient tree-traversals: reconciling parallelism and dense data representations},
author = {Chaitanya Koparkar and Mike Rainey and Michael Vollmer and Milind Kulkarni and Ryan R. Newton},
journal = {Proceedings of the ACM on Programming Languages},
volume = {5},
number = {ICFP},
year = {2021},
doi = {10.1145/3473596}
}