Stealing from Biologists to Compile Haskell Faster
The article discusses the challenges of optimizing the ApplicativeDo feature in the GHC Haskell compiler. It highlights the complexity of grouping independent statements for better performance and the algorithmic difficulties involved. The author draws parallels between the optimization problem and techniques used in biology for RNA folding predictions.
- ▪GHC has an optimization flag for ApplicativeDo that is disabled by default due to performance issues.
- ▪The optimal layout algorithm for ApplicativeDo is complex and has a high computational cost.
- ▪The goal is to optimize the scheduling of independent statements without incurring the O(n³) cost of the optimal algorithm.
Opening excerpt (first ~120 words) tap to expand
Stealing from Biologists to Compile Haskell Faster [ 2026-05-30 ] This started when someone mentioned, mostly in passing, that GHC has a flag for ApplicativeDo (-foptimal-applicative-do) that’s switched off by default because the algorithm behind it is too slow to use. That sounded like a bug to me. An optimization that’s correct but disabled for being slow is the kind of thing you fix in an afternoon, I figured. It wasn’t; it turned out to be a properly hard problem, and the problem has been eating at me for months. ApplicativeDo is a quiet corner of GHC to start with. Most programs never switch it on, and most of the ones that do are fine with the default and never reach for the optimal flag, so we’re well into the weeds even by compiler-internals standards.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at Ian Duncan.
Discussion
0 commentsMore from Ian Duncan
