Scan-scatter fusion

Summary

Posted on March 24, 2026 by Troels Henriksen This post is about the compiler optimisation with the coolest name: Fusion. In the functional literature it is sometimes called deforestation, which sounds rather less cool, and in fact somewhat undesirable. But I digress already. The post to follow is at a high level about a new optimisation we wanted to add to the Futhark compiler to handle a reasonably common (and quite important) class of parallel programs, how we changed our approach to make it tenable, how we also had to adjust our Futhark programming style to cater to this optimisation, and why that is not quite as horrible as it sounds. I will note in advance that the vast majority of the work was done by William Henrich Due, who is a PhD student here at DIKU, and one critical idea was suggested by Cosmin Oancea. Fusion is an optimisation that combines together data parallel operations in order to avoid storing intermediate results in memory. The simplest example is map-map fusion, which occurs when the output of a map is passed to another map. For example, the expression map (\y -> y + 2) (map (\x -> x * 2) xs) could be rewritten through fusion to which, if we imagine the straightforward execution on a computer, performs fewer reads and writes to memory. Except for edge cases fusion does not affect the asymptotics of a program, but it is an important source of constant-time improvements. What is particularly important is that it allows a program to be structured as many small modular operations, which are easier to maintain than a single big one, without suffering any overhead. Indeed, I think the main advantage of optimising compilers is not to magically make code faster, but rather to allow us to write more modular and abstract code without suffering performance penalties. The example above is a case of vertical fusion, where two operations are connected in a producer-consumer relationship. Another case of fusion is horizontal, where two parallel operations on ...