[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