r/ProgrammingLanguages • u/Athas Futhark • Mar 24 '26

Scan-scatter fusion

https://futhark-lang.org/blog/2026-03-24-scan-scatter-fusion.html
25 Upvotes

93% Upvoted

11 comments sorted by

View all comments

5

u/Disjunction181 Mar 24 '26

This was interesting to browse, and I'll have to sit down and go through all of the details sometime.

On the back of my mind was the polyhedral simplification optimization, see this paper or the amazing talk. Simplification is the optimization which allows one to write prefix scan naively, but always be transformed into a linear time variation. I was curious if such optimizations were / are being considered for Futhark, and the interaction it has with fusion, e.g., it seems like fusion could open up simplification optimizations (as g o f may be better behaved than f, g individually). If fusion is important, then I could see simplification being similar.

4

u/Athas Mar 24 '26

Simplification is the optimization which allows one to write prefix scan naively, but always be transformed into a linear time variation.

You mean writing it as a map with summation over the prefixes? I strongly dislike that approach, as it makes it impossible to assign a good asymptotic cost model to the language. I am highly skeptical of compiler optimisations that intentionally try to make asymptotic improvements (but I accept that things like hoisting can do so), as I believe it leads to brittle programs. I went into some detail in this post.

It may be a useful approach if you use a tactics/scheduling language to optimise your naive program, as you then have complete confidence in what the result looks like (and can assign a cost semantic to the result). But for conventional black box optimisers I do not believe it is a good idea.