[racket] Y-combinator perfomance

Is there any way to avoid this overhead? I'm really interested in combinator style, but if it makes programs 8 times slower, it is useless. Maybe some compiler/macro optimizations is possible?

25.06.10, 22:50, "Matthew Flatt" <mflatt at cs.utah.edu>:

> 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))
>  
>  
>