[racket] Y-combinator perfomance

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