[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