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