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" <mfl...@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)) > > > _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
