Aelve Guide | Haskell

Authors: Simon Peyton Jones, Luke Maurer, Paul Downen, Zena M. Ariola.
Discussions: Reddit.

The paper describes a concept called “join points” which allows to perform many optimisations without having to represent the code in CPS form. The authors also claim to have “resolved a long-standing tension between stream fusion and unfoldr/destroy fusion”. They have also tried adding the concept of join points to GHC; it results in a slight decrease in allocations for most benchmarks from the spectral part of nofib, as well as decreasing allocation by 86% in k-nucleotide benchmark from the shootout and removing allocation completely from the n-body benchmark.

Many fields of study in compilers give rise to the concept of a join point—a place where different execution paths come together. While they have often been treated by representing them as functions or continuations, we believe it is time to study them in their own right. We show that adding them to a direct-style functional intermediate language allows new optimizations to be performed, including a functional version of loop-invariant code motion. Finally, we report on recent work on the Glasgow Haskell Compiler which added join points to the Core language.

As hoped, adding join points turned out to be a very modest change, despite GHC’s scale and complexity. Like any optimization, it does not make every program go faster, but it has a dramatic effect on some.

Duncan Coutts's 250-page PhD thesis about stream fusion. Serves as a good, comprehensive introduction to the concept of fusion.