On 06/25/2010 12:59 PM, Groshev Dmitry wrote:
> 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?
You might find this version interesting:
(define-syntax define/rec
(syntax-rules ()
[(define/rec (name arg ...) body)
(define name
(let ([actual
(λ (self arg ...)
(let-syntax ([name
(syntax-rules ()
[(name name-arg (... ...))
(self self name-arg (... ...))])])
body))])
(lambda (arg ...) (actual actual arg ...))))]))
The (... ...) escapes the ellipses, so they are interpreted as ellipses
for the local 'name' macro, not the 'define/rec' macro.
(define/rec (rec-sum l t)
(if (empty? l) t (rec-sum (cdr l) (+ t (car l)))))
Ryan
> 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
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
