[racket] Y-combinator perfomance

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Fri Jun 25 14:50:34 EDT 2010

If you're interested in specially the overhead of combinator style,
then your example still understates the overhead compared to relatively
cheap operations.

In addition to Matthias's change to get rid of `apply', I've revised
your program (see below) to replace `first' and `rest' with `car' and
`cdr' (which don't have to check that they're given lists) and to lift
out the list creation (which becomes significant). With those changes,
I get

 cpu time: 1655 real time: 1668 gc time: 1546 ; list creation
 cpu time: 422 real time: 426 gc time: 41
 cpu time: 60 real time: 60 gc time: 0

The direct version is faster because the compiler can see the loop, so
it can produce code with fewer jumps and less allocation of
intermediate closures. I suppose that the general rule is that the
compiler is more effective when you can use constructs that say more
directly what you want.

Compilers can't easily see through a Y combinator, and a factor of 8 or
so difference is probably typical for Lisp compilers. (I tried Ikarus
and Gambit to double check, and performance was about the same as with


#lang racket
(define-syntax U
  (syntax-rules ()
    [(_ f) (f f)]))
(define-syntax define/comb
  (syntax-rules ()
    [(_ comb name (arg . args) f)
     (define name 
       (comb (λ (name) (λ (arg . args) f))))]))

(define (Z f)
  (U (λ (g) (λ (x y)
              ((f (U g)) x y)))))

(define/comb Z comb-sum (l t) 
  (if (null? l) t (comb-sum (cdr l) (+ t (car l)))))

(define (sum l t)
  (if (null? l) t (sum (cdr l) (+ t (car l)))))

(define l (time (make-list 10000000 1)))
(time (comb-sum l 0))
(time (sum l 0))

Posted on the users mailing list.