Performance of lazy combinator graph reduction


Hartel, P.H. (1991) Performance of lazy combinator graph reduction. Software: Practice and Experience, 21 (3). pp. 299-329. ISSN 0038-0644

open access
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 combinator. 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 programderived combinator are used instead of standard combinator. The analysis is based on experimental evidence obtained from a small bench-mark of medium-size functional programs. Performance gains of up to 11 ´ 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.
Item Type:Article
Copyright:© 1991 by John Wiley
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page