[gambit-list] Poor compilation of do-loops
Marc Feeley
feeley at iro.umontreal.ca
Thu Oct 15 15:57:42 EDT 2009
On 2009-10-15, at 12:22 PM, Bradley Lucier wrote:
> Marc:
>
> At the end of this message I suggest a compiler transformation of
> do-loops that doubles the speed of the sample code.
Your transformation of nested do loops is not always a win. It may
increase the number of free variables of the inner loop. See the
example below. In fact the transformation that Gambit uses can be
made arbitrarily faster than yours (by increasing the number of free
variables). It is in the worst case a constant factor slower.
So a heuristic would have to be developed to identify the cases where
your transformation is a win. Care to find one? It doesn't seem easy.
Marc
(declare (standard-bindings) (extended-bindings) (fixnum) (not safe))
(define (f1 n)
;; Gambit expansion of nested do loops
(let loop1 ((a n) (b n) (c n))
(if (> a 0)
(begin
(let loop2 ((x n) (y n) (z n))
(if (> x 0)
(loop2 (- y 1) z x)))
(loop1 (- b 1) c a)))))
(define (f2 n)
;; Brad's version
(let loop1 ((a n) (b n) (c n))
(if (> a 0)
(begin
(let loop2 ((x n) (y n) (z n))
(if (> x 0)
(loop2 (- y 1) z x)
(loop1 (- b 1) c a)))))))
(time (f1 10000)) ;; 435 ms
(time (f2 10000)) ;; 651 ms
More information about the Gambit-list
mailing list