O'Boyle, Michael

Franke, Bjoern

Hollenbeck, Celeste

2025-07-17T11:29:56Z

2025-07-17T11:29:56Z

2025-07-17

Inlining has been claimed to be the single most important optimization in Haskell, and also the optimization receiving the most attention. It is also considered one of the hardest optimizations to get right. If done poorly, it may cause code bloat, cache misses, and register spilling; yet if done well, it can provide orders of magnitude better performance in terms of run time and code size. Despite its importance, the Glasgow Haskell Compiler’s inliner has not undergone significant change in decades. This thesis explores the decision space of GHC’s inliner; presents potential approaches to re-imagining the inliner, along with data and discussion for why they do not work; and additionally provides a conceptually simple analysis which guides inlining decisions at the function declaration site by advising the placement of compiler pragmas in source code. The decision space exploration conducts an empirical investigation of the search space of GHC’s inlining decisions as it pertains to the randomization of the magic numbers—or handcoded constant integers—in the inlining heuristic.We demonstrate that randomizing the magic numbers produces some speedup over default GHC about half of the time, showing ample room for improvement. Then using iterative search, we produce four configurations into which we can cluster Haskell packages to produce a 26% mean speedup over 10 benchmark packages. Following search space exploration, we investigate three machine learning models to predict inlining decisions: a genetic algorithm and neural networks from within the middle of the compiler, and graph neural networks to place pragmas at the source-code level. Our investigation reveals that although we can train the models with a high degree of accuracy, their predictions still fail to produce significant performance results when used in practice. Finally, we devise a technique to place pragmas along hot call-chains—or complete, overapproximated chains of functions connected to profiled hot spots—which yields a 10% runtime speedup when combined with existing developer-placed pragmas, and 9% speedup without existing pragmas. This approach uses packages’ abstract syntax trees to approximate control flow in quadratic time, whereas a conventional context-insensitive flow analysis would be cubic.

https://hdl.handle.net/1842/43690

http://dx.doi.org/10.7488/era/6222

en

The University of Edinburgh

Celeste Hollenbeck, Michael F. P. O’Boyle, and Michel Steuwer. 2022. Investigating magic numbers: improving the inlining heuristic in the Glasgow Haskell Compiler. In Proceedings of the 15th ACM SIGPLAN International Haskell Symposium (Ljubljana, Slovenia) (Haskell 2022). Association for Computing Machinery, New York, NY, USA, 81–94. https://doi.org/10.1145/3546189.3549918

Celeste Hollenbeck and Michael F. P. O’Boyle. 2024. Hot Call-Chain Inlining for the Glasgow Haskell Compiler. In Proceedings of the 23rd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (Pasadena, CA, USA) (GPCE ’24). Association for Computing Machinery, New York, NY, USA, 66–79. https://doi.org/10.1145/3689484.3690730

inline expansion

inlining

Glasgow Haskell Compiler

GHC

optimization

randomization

machine learning

hot call-chains

pragmas

Inlining in the Glasgow Haskell Compiler: empirical investigation and improvement

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy