[racket] Y-combinator perfomance

I pointed out Jinx's paper to Matthew last week.

Not surprisingly, reality and theory never match with the MIT Scheme  
compiler.


On Jun 28, 2010, at 3:04 PM, Joe Marshall wrote:

> On Fri, Jun 25, 2010 at 11:50 AM, Matthew Flatt <mflatt at cs.utah.edu>  
> wrote:
>>
>> 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.)
>
> See
> @INPROCEEDINGS{Juan92tamingthe,
>    author = {Guillermo Juan and Guillermo Juan Rozas},
>    title = {Taming the Y operator},
>    booktitle = {In ACM Conference on LISP and Functional Programming},
>    year = {1992},
>    pages = {226--234},
>    publisher = {ACM Press}
> }
>  ``In this paper I present a set of conceptually simple but involved
> techniques used by Liar 1 , the MIT Scheme compiler, to generate good
> code when recursive procedures are specified in terms of suitable
> versions of the Y operator. The techniques presented are
> general-purpose analysis and optimization tools, similar to well-known
> techniques used in the analysis and optimization of applicative
> languages, that combine synergistically to enable Liar to generate
> identical machine code for ordinary recursive definitions written
> using letrec and those written using suitable forms of Y.''
>
> ;; Allow compiler to inline standard procedures.
> (declare (usual-integrations))
>
> (define-syntax U
> (syntax-rules ()
>   ((_ f) (f f))))
>
> (define-syntax define/comb
> (syntax-rules ()
>   ((_ comb name (arg1 arg2) body)
>    (define name
>      (comb (lambda (name) (lambda (arg1 arg2) body)))))))
>
> ;; Allow compiler to inline Z
> (define-integrable (Z f)
> (U (lambda (g) (lambda (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 (test1)
>  (let ((start-time (runtime))
> 	(l (make-list 10000000 1)))
>    (let ((answer (comb-sum l 0)))
>      (- (runtime) start-time))))
>
> (define (test2)
>  (let ((start-time (runtime))
> 	(l (make-list 10000000 1)))
>    (let ((answer (sum l 0)))
>      (- (runtime) start-time))))
>
> (test1) => .11 seconds
> (test2) => .11 seconds
>
>
> -- 
> ~jrm
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users