Performance of lazy combinator graph reduction
Pieter Hartel · Software Practice and Experience · 1991
Abstract The performance of program‐derived combinator graph reduction is known to be superior to that of graph reduction based on a fixed set of standard combinators. The major advantage of program‐derived combinator reduction is that it uses less transient store than standard combinator reduction. We show on what activities a combinator reduction algorithm spends its execution time. Based on this analysis we show that it depends to a large extent on the application how much faster a program will run if program‐derived combinators are used instead of standard combinators. The analysis is based on experimental evidence obtained from a small bench‐mark of medium‐size functional programs. Performance gains of up to 11 x are reported for target architectures on which each memory reference consumes one unit of time. The results are valid for implementations of combinator graph reduction that use binary graphs.