Double-Ended Bit-Stealing at ICFP 2024
05 September 2024
My paper Double-Ended Bit-Stealing for Algebraic Data Types was accepted for presentation at ICFP 2024 in Milan, with the talk on September 5.
Functional programs rely heavily on data structures such as trees and syntax representations. This paper shows how to make many of them more compact by using spare bits at both ends of a machine word to identify their constructors. The technique avoids some extra allocations while keeping a uniform representation of values. Implemented in MLKit, it improves memory use and delivers speedups on affected benchmarks, including around 9% when compiling MLKit itself and MLton.