Time- and Size-Efficient Supercompilation

• Plain version with links: [A4 PDF]

Abstract

Intermediate structures such as lists and higher-order functions are very common in most styles of functional programming. While allowing the programmer to write clear and concise programs, the creation and destruction of these structures impose a run time overhead which is not negligible. Supercompilation algorithms is a family of program transformations that remove these intermediate structures in an automated fashion, thereby improving program performance.

While there has been plenty of work on supercompilation algorithms that remove intermediate structures for languages with call-by-name semantics, no investigations have been performed for call-by-value languages. It has been suggested that existing call-by-name algorithms could be applied to call-by-value programs, possibly introducing termination in the program. This hides looping bugs from the programmer, and changes the behaviour of a program depending on whether it is optimized or not.

We present positive supercompilation algorithms for higher-order call-by-value and call-by-name languages that preserves termination properties of the programs they optimize. We prove the call-by-value algorithm correct and compare it to existing call-by-name transformations. Our results show that deforestation-like transformations are both possible and useful for call-by-value languages, with speedups up to an order of magnitude for certain benchmarks. We also suggest to speculatively supercompile expressions and discard the result if it turned out bad. To test this approach we implemented the call-by-name algorithm in GHC and performed measurements on the standard nofib benchmark suite. We manage to supercompile large parts of the imaginary and spectral parts of nofib in a matter of seconds while keeping the binary size increase below 5%.

Our algorithms are particularly important in the context of embedded systems where resources are scarce. By both removing intermediate structures and performing program specialization the footprint of programs can shrink considerably without any manual intervention by the programmer.

Taming Code Explosion in Supercompilation

• Paper: [A4 PDF]

Abstract

Supercompilation algorithms can perform great optimizations but sometimes suffer from the problem of code explosion. This results in huge binaries which might hurt the performance on a modern processor. We present a supercompilation algorithm that is fast enough to speculatively supercompile expressions and discard the result if it turned out bad. This allows us to supercompile large parts of the imaginary and spectral parts of nofib in a matter of seconds while keeping the binary size increase below 5%.

Strengthening Supercompilation For Call-By-Value Languages

• Paper: [A4 PDF]

Abstract

A termination preserving supercompiler for a call-by-value language sometimes fails to remove intermediate structures that a supercompiler for a call-by-name language would remove. This discrepancy in power stems from the fact that many function bodies are either non-linear in use of an important variable or often start with a pattern match on their first argument and are therefore not strict in all their arguments. As a consequence, intermediate structures are left in the output program, making it slower. We present a revised supercompilation algorithm for a call-by-value language that propagates let-bindings into case-branches and uses termination analysis to remove dead code. This allows the algorithm to remove all intermediate structures for common examples where previous algorithms for call-by-value languages had to leave the intermediate structures in place.

Supercompiling Overloaded Functions

• Paper: [A4 PDF]

Abstract

A naïve translation of recursive cases in type class instances will give code that allocates a new dictionary and copies the data from the input dictionary to the new dictionary for the recursive call. This record creation allocates memory and leads to bad performance for a conceptually simple and rather common operation, for example equality between lists. We present a positive supercompilation algorithm, parametrized with respect to evaluation order, and show how this algorithm can remove these allocations resulting in both time and space savings. We also show how a small extension to the folding mechanism of our supercompiler can give similar effects the static argument transformation at nearly no extra cost.

Positive Supercompilation for a Higher Order Call-By-Value Language

• Journal version (LMCS): [A4 PDF]
• Paper: [A4 PDF]
• Companion technical report: [A4 PDF]
• Related work (for a lazy language): Supero by Neil Mitchell and Colin Runciman

Abstract

Previous deforestation and supercompilation algorithms may introduce accidental termination when applied to call-by-value programs. This hides looping bugs from the programmer, and changes the behavior of a program depending on whether it is optimized or not. We present a supercompilation algorithm for a higher-order call-by-value language and we prove that the algorithm both terminates and preserves termination properties. This algorithm utilizes strictness information for deciding whether to substitute or not and compares favorably with previous call-by-name transformations.

Positive Supercompilation for a higher order call-by-value language

• Plain version with links: [A4 PDF]
• Nice cover version without any links: [A4 PDF]
• Related work (for a lazy language): Supero by Neil Mitchell and Colin Runciman

Abstract

Intermediate structures such as lists and higher-order functions are very common in most styles of functional programming. While allowing the programmer to write clear and concise programs, the creation and destruction of these structures impose a run time overhead which is not negligible. Deforestation algorithms is a family of program transformations that remove these intermediate structures in an automated fashion, thereby improving program performance.

While there has been plenty of work on deforestation-like transformations that remove intermediate structures for languages with call-by-name semantics, no investigations have been performed for call-by-value languages. It has been suggested that existing call-by-name algorithms could be applied to call-by-value programs, possibly introducing termination in the program. This hides looping bugs from the programmer, and changes the behaviour of a program depending on whether it is optimized or not.

We present a transformation, positive supercompilation, for a higher-order call-by-value language that preserves termination properties of the programs it is applied to. We prove the algorithm correct and compare it to existing call-by-name transformations. Our results show that deforestation-like transformations are both possible and useful for call-by-value languages, with speedups up to an order of magnitude for certain benchmarks.

Our algorithm is particularly important in the context of embedded systems where resources are scarce. By both removing intermediate structures and performing program specialization the footprint of programs can shrink considerably without any manual intervention by the programmer.