[racket] Y-combinator perfomance

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