I propose to make Haskell programs run faster by using trace-based runtime optimization to reduce the overhead of key abstractions in Haskell. Abstraction has always been a cornerstone in the construction of large programs and will be even more important as we scale the size of our programs to consume ever increasing hardware resources. Language abstractions must be implemented efficiently if they are to be used in large programs of the future. Haskell provides many useful abstractions for the programmer in the form of type classes, lazy evaluation, and higher-order functions. Unfortunately, these abstractions can be detrimental to performance and have limited the spread of Haskell in research and industry.
Trace-based runtime optimization is a technique for performing transformations on the paths executed by a program as it runs. The transformations can use the runtime context not available to a traditional static compiler, but they must be efficient because the additional overhead slows down the program. Runtime optimization has been applied to traditional languages, as exemplified by DynamoRIO, as well as object-oriented languages, such as Java. My work will be one of the first to look at runtime optimization for a lazy functional language such as Haskell.
Initial results provide evidence for why runtime optimization optimization of Haskell is necessary. The first result shows that the low-level code of Haskell programs differs from that of traditional languages, suggesting that new optimization techniques are needed. The second result reinforces this idea by showing how traditional optimizations have a limited effect on Haskell codes, producing only a 6% improvement on average. Finally, I present a hand-coded case study showing potential effectiveness of trace-based runtime optimization.
As a result of this research I expect to produce a runtime optimizer for Haskell along with the important techniques for runtime optimization of lazy functional programs.