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