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
10000000
cpu time: 60 real time: 60 gc time: 0
10000000
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
Racket.)
----------------------------------------
#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))
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
