Marc:
At the end of this message I suggest a compiler transformation of do-loops that doubles the speed of the sample code.
A matrix multiplication benchmark recently was posted to the Chicken list, see the thread beginning here:
http://lists.gnu.org/archive/html/chicken-users/2009-10/msg00050.html
The Gambit version of the benchmark has no Gambit-specific declarations, uses generic vectors and arithmetic.
When I built the Gambit benchmark the way that it was done in that thread and run it on the 100x100 example, I get
heine:~/programs/matrix-multiply-benchmarks> ./gamb-bench
10 ------------ (time (set! c (bench-multiply a b times))) 2838 ms real time 2836 ms cpu time (2836 user, 0 system) 326 collections accounting for 382 ms real time (376 user, 0 system) 702278640 bytes allocated 835 minor faults no major faults ------------
When I build it with gsc -exe, I get
heine:~/programs/matrix-multiply-benchmarks> ./matrix-bench-gambit
10 ------------ (time (set! c (bench-multiply a b times))) 1429 ms real time 1424 ms cpu time (1420 user, 4 system) 326 collections accounting for 380 ms real time (352 user, 4 system) 702278640 bytes allocated 833 minor faults no major faults ------------
When I use fx and fl operations, uniform f64vectors, and (standard-bindings)(extended-bindings)(block), I get
heine:~/programs/matrix-multiply-benchmarks> ./matrix-lucier
10 ------------ (time (set! c (bench-multiply a b times))) 1221 ms real time 1220 ms cpu time (1220 user, 0 system) 1027 collections accounting for 357 ms real time (356 user, 0 system) 1409818032 bytes allocated 226 minor faults no major faults ------------
And if I add (not safe) I get
heine:~/programs/matrix-multiply-benchmarks> ./matrix-lucier
10 ------------ (time (set! c (bench-multiply a b times))) 877 ms real time 880 ms cpu time (876 user, 4 system) 772 collections accounting for 268 ms real time (284 user, 0 system) 1057834192 bytes allocated 451 minor faults no major faults ------------
So far, so good. The main loop is
(define multiply (lambda (m1 m2) (let* ((nr1 (matrix-rows m1)) (nr2 (matrix-rows m2)) (nc2 (matrix-columns m2)) (r (make-matrix nr1 nc2))) (if (not (fx= (matrix-columns m1) nr2)) (match-error m1 m2)) (do ((i 0 (fx+ i 1))) ((fx= i nr1) r) (do ((j 0 (fx+ j 1))) ((fx= j nc2)) (do ((k 0 (fx+ k 1)) (a 0.0 (fl+ a (fl* (matrix-ref m1 i k) (matrix-ref m2 k j))))) ((fx= k nr2) (matrix-set! r i j a))))))))
If I rewrite this by hand to use named lets, like
(define multiply (lambda (m1 m2) (let* ((nr1 (matrix-rows m1)) (nr2 (matrix-rows m2)) (nc2 (matrix-columns m2)) (r (make-matrix nr1 nc2))) (if (not (fx= (matrix-columns m1) nr2)) (match-error m1 m2)) (let i-loop ((i 0)) (if (fx= i nr1) r (let j-loop ((j 0)) (if (fx= j nc2) (i-loop (fx+ i 1)) (let k-loop ((k 0) (a 0.0)) (if (fx= k nr2) (begin (matrix-set! r i j a) (j-loop (fx+ j 1))) (k-loop (fx+ k 1) (fl+ a (fl* (matrix-ref m1 i k) (matrix-ref m2 k j)))))))))))))
I get
heine:~/programs/matrix-multiply-benchmarks> ./matrix-lucier-named-let
10 ------------ (time (set! c (bench-multiply a b times))) 422 ms real time 416 ms cpu time (412 user, 4 system) 515 collections accounting for 175 ms real time (184 user, 4 system) 705822880 bytes allocated 451 minor faults no major faults ------------
In other words, this mechanical translation of do loops to named lets (following the known continuation when each loop is finished) more than doubles the speed of the routine.
I've trained myself to write loops as named lets, but other people have not yet been assimilated to modify how they write code to get around the oddities of Gambit's compiler. Do loops are very popular in numerical code; please add a transformation like this to the compiler.
Brad
Afficher les réponses par date
Date: Thu, 15 Oct 2009 12:22:37 -0400 From: Bradley Lucier lucier@math.purdue.edu
In other words, this mechanical translation of do loops to named lets (following the known continuation when each loop is finished) more than doubles the speed of the routine.
I've trained myself to write loops as named lets, but other people have not yet been assimilated to modify how they write code to get around the oddities of Gambit's compiler. Do loops are very popular in numerical code; please add a transformation like this to the compiler.
I'm puzzled: how is DO implemented in Gambit, if not as a macro that performs precisely that transformation?
Date: Thu, 15 Oct 2009 12:28:35 -0400 From: Taylor R Campbell campbell@mumble.net
Date: Thu, 15 Oct 2009 12:22:37 -0400 From: Bradley Lucier lucier@math.purdue.edu
In other words, this mechanical translation of do loops to named lets (following the known continuation when each loop is finished) more than doubles the speed of the routine.
I've trained myself to write loops as named lets, but other people have not yet been assimilated to modify how they write code to get around the oddities of Gambit's compiler. Do loops are very popular in numerical code; please add a transformation like this to the compiler.
I'm puzzled: how is DO implemented in Gambit, if not as a macro that performs precisely that transformation?
I see: Gambit is probably transforming DO the obvious way, to yield
... (let k-loop ((k 0)) (if (fx= k nr2) (matrix-set! r i j a) ...)) (j-loop (fx+ j 1)) ...
But Gambit is not performing the control flow analysis necessary to observe that the continuation of the initial call to K-LOOP -- the continuation which calls J-LOOP -- will be used only once, and can be integrated in-line at its single call site to yield
... (let k-loop ((k 0)) (if (fx= k nr2) (begin (matrix-set! r i j a) (j-loop (fx+ j 1))) ...)) ...
So Gambit is pushing some unnecessary stack frames in this loop.
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
On Thu, 2009-10-15 at 15:57 -0400, Marc Feeley wrote:
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, you're saying that with Gambit's imperfect (to be *very* polite) register allocator, lambda-lifting loops adds more free variables to the inner loops, which can slow things down arbitrarily much with certain loops, which, to my eye, look pretty pathological. So your way of generating code is minimax (minimizes the maximum possible delay), while what I'm suggesting would, I claim, speed up the average loop at the risk of delaying some convoluted code that only a compiler-writer would dream up. (The code looks like a state machine after my transformation, and I believe that state machines should be compiled into efficient code by Scheme compilers.)
There are ways to test this hypothesis of "average loop". One could add this transformation temporarily and then run the benchmark suite with and without the transformation. The source files with '(do ' are:
array1.scm browse.scm compiler.scm destruc.scm diviter.scm divrec.scm gcbench.scm graphs.scm matrix.scm maze.scm nboyer.scm perm9.scm puzzle.scm ray.scm sboyer.scm simplex.scm string.scm sumloop.scm trav1.scm trav2.scm triangl.scm
Or, you could release a special beta version of Gambit with the transformation and let people with numeric codes try it out and reply to this list with their results.
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.
How about "do it if it doesn't increase the number of free variables by k%", like inlining-limit.
Brad
On Oct 16, 2009, at 12:51 PM, Bradley Lucier wrote:
On Thu, 2009-10-15 at 15:57 -0400, Marc Feeley wrote:
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.
How about "do it if it doesn't increase the number of free variables by k%", like inlining-limit.
Marc:
After thinking about it some more, this doesn't seem like such a bad idea.
What do you think?
Brad
If matrix-ref is inlined into the calculation
(fl+ a (fl* (matrix-ref m1 i k) (matrix-ref m2 k j))))))))))))))
then there is even greater speedup, partly because no flonums need to be boxed as return values of matrix-ref. The compiler inlines some uses, but I tried to inline all uses with inlining-limit, but failed (bug 117, I think), but after writing matrix-ref and matrix-set! as macros, I get the following runtimes (on a different machine than before).
Original code (but compiled using gsc -exe, so twice as fast as original report, "with all possible optimizations turned on"): 1344 ms cpu time (1340 user, 4 system) Using declarations, fixnum- and flonum-specific operations, and f64vectors: 784 ms cpu time (776 user, 8 system) Using named let: 336 ms cpu time (328 user, 8 system) Inlining all (not just some) instances of matrix-ref and matrix-set!: 124 ms cpu time (120 user, 4 system)
I'm planning to use Gambit again in my numerical PDE class next semester, so I'd like to win these benchmark games ;-).
Brad
On Thu, 2009-10-15 at 12:22 -0400, 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.
A matrix multiplication benchmark recently was posted to the Chicken list, see the thread beginning here:
http://lists.gnu.org/archive/html/chicken-users/2009-10/msg00050.html
The Gambit version of the benchmark has no Gambit-specific declarations, uses generic vectors and arithmetic.
On 2009-10-17, at 7:45 PM, Bradley Lucier wrote:
If matrix-ref is inlined into the calculation
(fl+ a (fl* (matrix-ref m1 i k) (matrix-ref m2 k j))))))))))))))
then there is even greater speedup, partly because no flonums need to be boxed as return values of matrix-ref. The compiler inlines some uses, but I tried to inline all uses with inlining-limit, but failed (bug 117, I think), but after writing matrix-ref and matrix-set! as macros, I get the following runtimes (on a different machine than before).
Original code (but compiled using gsc -exe, so twice as fast as original report, "with all possible optimizations turned on"): 1344 ms cpu time (1340 user, 4 system) Using declarations, fixnum- and flonum-specific operations, and f64vectors: 784 ms cpu time (776 user, 8 system) Using named let: 336 ms cpu time (328 user, 8 system) Inlining all (not just some) instances of matrix-ref and matrix-set!: 124 ms cpu time (120 user, 4 system)
I'm planning to use Gambit again in my numerical PDE class next semester, so I'd like to win these benchmark games ;-).
Brad
Adding the optimization you propose is certainly something interesting to explore. However, it will not be done soon because the optimization depends on a nontrivial control flow analysis (to determine all the places in the code where the continuation of the do- loop may be invoked). Jeremie Lasalle-Ratelle is currently implementing a 0-CFA and I believe his algorithm can be extended to perform the required analysis.
So to be safe you should plan teaching your students to avoid "do" by using named-let.
Marc