[gambit-list] Poor compilation of do-loops
Bradley Lucier
lucier at math.purdue.edu
Thu Oct 15 12:22:37 EDT 2009
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
More information about the Gambit-list
mailing list