1. 6


  1. 2

    Here’s the abstract.

    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.

    1. 2

      It’s a follow-up to the Gibbon paper! It looks like Parallel Gibbon still has one of the weaknesses of original Gibbon: because the data structures are dense, random access and non-linear transformations are expensive. We must eat “the whole plate,” so to speak. But the authors do show how to trade memory for faster consumption of data structures in parallel, and they also leverage linear types for Haskell to enforce consumption of values. And the sheer size of objects cannot be ignored:

      For our implementation, we store the ASTs on disk in a serialized format which is read using a single mmap call. All others parse the text files before operating on them. … The size of the text file is 1.2G, and that same file when serialized for our implementation is 356M.