Performance of lazy combinator graph reduction

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. KEY WORDS Turner’s combinators G-machine Performance modelling Graph reduction Instruction level timing Small functional bench-mar