Compiler Comparison

By Jörg Langowski, MacTutor Editorial Board

Code optimization

You will have noticed the change in the column’s title: a recent reader survey has shown that Forth and Basic are the two languages that our readers would most like to see less of in MacTutor. That’s a shame, but we’re responsive (at least we try)

So, from now on my monthly column will have a wider scope. As you might have seen, I have very often used Forth as a vehicle to explain general concepts of Macintosh programming. Since many subscribers don’t seem to be happy with Forth - in fact, people often have asked about things that had been explained in a Forth column, but they just hadn’t read. The column about the Notification Manager in V5#6 is a good example: at the bottom of page 42, one of the ‘ideas to be written’ was explained as: “ An example that places a Notification Manager request in low System memory, and starts a Timer routine ”; this is just the example that was in the Forth Forum that covered the Notification Manager. Anyway, I’ll try to use other vehicles to convey the message from now on. Such as assembly, or maybe even C. Mach2 Forth still is a very good assembly-language development system because of its interactivity. Of course, you cannot create complicated macros, or structures, and have to resort to Forth code for those purposes. I’ll still inform you about interesting things I come across on the Forth scene, but this won’t be an exclusive Forth column anymore. Emphasis will be on two things: basic system-level things such as drivers, trap patches, INITs, network, new managers as they come up; and - on the other side of the spectrum - object-oriented programming in C++.

Apple will ‘Real Soon Now’ release a C++ under MPW, and we’ll hopefully have a pre-release by the time you read this. C++ is a very interesting language, much more than a simple extension of C; reading Stroustrup’s book I got this feeling of ‘yes, that’s how one should have done it in the first place’ that I had 15 years ago when all I knew was Algol 60, and came across the description of Algol 68. Sadly enough, Algol 68 never really caught on; hopefully, C++ will. The C++ column will start with the next issue; including program examples if we get the pre-release soon enough, just ‘dry swimming’ if not.

This month, we’ll talk once more about one of my favorite subjects, number crunching, speed (or the lack of it), and intelligence in compilers (or the lack of it).

A matrix multiplication routine

Since I am doing more and more everyday computation (mostly Fortran) on the MacII, I’m obviously interested in a good optimizing compiler. Now, a standard trick that every decent compiler should have in its repertoire is the elimination of constant expressions from loops, or assignment of array elements that are not dependent on the loop index to intermediate variables.

Imagine my surprise when I found out that (in Language Systems Fortran 1.2.1) I could speed up a loop that looked like this:

 do k=1,n3
 do i=1,n1
 c(i,k) = 0x0
 do j=1,n2
 c(i,k) = c(i,k)+a(i,j)*b(j,k)
 end do
 end do
 end do

by simply writing:

 do k=1,n3
 do i=1,n1
 sum = 0x0
 do j=1,n2
 sum = sum+a(i,j)*b(j,k)
 end do
 c(i,k) = sum
 end do
 end do

Now, in undergraduate programming classes, years ago, we were actually taught to look for constant arithmetical or index expressions in loops and put them outside if possible. Today, almost everybody assumes that the compiler is smart enough to take care of that; incorrectly, as you see. To see how good the compilers available under MPW can do, I wrote a Fortran program (listing 1) that calls several versions of this matrix multiplication loop, written in Fortran (Lang. Sys. 1.2.1), Pascal (Apple 3.0 beta), and C (Apple 3.0 beta). Surprise: none of the compilers was good enough to move the indexing outside of the loop. The following table gives the results (Mac IIx):

Pascal, hand-optimized: 2.7667 seconds

C, register variables, hand-opt.: 3.4667 seconds

Pascal: 4.0333 seconds

Fortran, const. dimensions, opt=3: 4.5000 seconds

Fortran, hand-optimized, opt=3: 4.6500 seconds

C: 4.7167 seconds

Fortran, opt=3: 6.5167 seconds

Fortran, opt=0: 6.6167 seconds

A difference of more than a factor of 2 between the slowest Fortran and the fastest Pascal code. Apple Pascal lived up to its good reputation here, but even that could be improved a lot by eliminating the constant index expression.

Surprised, I ran the Fortran benchmark on a Microvax II, and found that even there some speed could be gained by ‘hand-optimizing’ the code:

Fortran, plain: 3.6333 seconds

Fortran, hand-opt.: 3.2833 seconds

Fortran, const. dimensions: 3.1000 seconds

However, the difference between the machine-optimized and the hand-optimized version is not quite as big as for the MPW languages (15% for the VAX vs. 27-30% for MPW). If you compile the VAX code without optimization, you get a bigger difference (23%):

Fortran, plain: 6.2500 seconds

Fortran, hand-opt.: 4.8833 seconds

Fortran, const. dimensions: 4.8000 seconds

Therefore, take-home lesson one: don’t take compiler optimizations for granted.

The machine code behind it

Benchmarks have been run on lots of different machines, using lots of different compilers. I was interested in how the code generated by the MPW compilers actually differed. A job for Nosy, and the results are shown in the last listing. I’ve only printed the innermost loops. Don’t be overwhelmed by the pile of assembly code, just note some important details.

First, for the loop optimization examples discussed here, there seems to be no tradeoff between code length and speed. On the contrary, the fastest code is also the shortest. On the other hand, there are some obvious pieces of code which are clearly redundant. The most blatant example is the Fortran-generated code at the end of the listing, where an index expression is recalculated that was actually in register A1 all the time! 14 extra lines of machine code on each pass through the loop will add up to quite some extra time lost. Another point is that Language System obviously has no great trust in the quality of the 68000/20/30, otherwise how can one explain that they repeat the EXT.L D2 instruction each time it occurs? To make sure it works at least once?

Language Systems Fortran makes other funny assumptions about the machine, for instance it seems to think there are only two floating point registers in the 68881, FP0 and FP7. I have looked at some code which had great potential for optimization by using enough FP registers. Language Systems is, however, known for its responsiveness towards customers, so I hope we won’t have to wait too long until a well-optimized Fortran shows up.

Both Pascal and C like juggling floating point registers. Why generate (like Apple’s C):

FMOVE   FP7,FP1
FADD    FP0,FP1
FMOVE   FP1,FP7

when a simple FADD FP0,FP7 would suffice? Eliminates two floating point instructions per loop. Pascal does

   FADD    FP7,FP0
   FMOVE   FP0,FP7

when a simple inversion of the operands

   FADD FP0,FP7

would give the same result. One floating point instruction per loop eliminated. The timing difference between the Pascal and C routines is partly because of the one extra floating point instruction.

Last remark: I haven’t seen the Absoft MPW 3.0 Fortran yet. If anyone from Absoft is reading this, I’d like an evaluation copy to run the same analysis (since you claim in your ads you have such a great optimizer). If I get enough other languages collected together, we’ll have a follow-up on this article.

Next month

The MacHack is over (thanks, Aimée, Carol, and all the others, for organizing such a good meeting), and I’ll tell you some of my impressions in the next column. Otherwise, we’ll start with an introduction to C++; I hope the compiler will arrive here in time.

Listing 1: Matrix multiplication benchmark

!!S Main
 program matrix
c
c Main program in Language Systems Fortran
c
c Some line breaks in the Fortran program are due to 
c editing.
c
 implicit none
 
 integer i,j,ticks1,ticks2
 extended a(50,50), b(50,50), c(50,50)
 extended time1,time2
 
 integer ticks
 
 type *,’Matrix multiplication benchmark’
 type *,’------------------------------’
 type *
 type *,’This program compares the number crunching power’
 type *,’of some of the popular MPW compilers.’
 type *,’Written under MPW 3.0 by J. Langowski / MacTutor 1989'
 type *
 type *,’Setting up 50x50 matrices...’

 ticks1 = ticks()
 
 do i=1,50
 do j=1,50
 a(i,j) = (i-1) + j-1
 b(j,i) = a(i,j)
 end do
 end do
 
 ticks2 = ticks()
 time1 = (ticks2-ticks1)/60.
 type *
 write (6,’(f8.4,’’ seconds for setting up matrices’’)’) time1
 
 ticks1 = ticks()
 call mat_mult_for3(c,50,a,50,b,50,50,50,50)
 
 ticks2 = ticks()
 time1 = (ticks2-ticks1)/60.
 type *
 write (6,’(f8.4,’’ seconds for multiplying matrices’’,
     *  ‘’ using FORTRAN routine, opt=3'’)’) time1
 type *,’c(25,25) = ‘,c(25,25)
 
 ticks1 = ticks()
 call mat_mult_for(c,50,a,50,b,50,50,50,50)
 
 ticks2 = ticks()
 time1 = (ticks2-ticks1)/60.
 type *
 write (6,’(f8.4,’’ seconds for multiplying matrices’’,
     *  ‘’ using FORTRAN routine, opt=0'’)’) time1
 type *,’c(25,25) = ‘,c(25,25)

 ticks1 = ticks()
 call mat_mult_for1(c,50,a,50,b,50,50,50,50)
 
 ticks2 = ticks()
 time1 = (ticks2-ticks1)/60.
 type *
 write (6,’(f8.4,’’ seconds for multiplying matrices’’,
     *  ‘’ using FORTRAN routine, hand-optimized’’)’) time1
 type *,’c(25,25) = ‘,c(25,25)
 
 ticks1 = ticks()
 call mat_mult_for0(c,50,a,50,b,50,50,50,50)
 
 ticks2 = ticks()
 time1 = (ticks2-ticks1)/60.
 type *
 write (6,’(f8.4,’’ seconds for multiplying matrices’’,
     *  ‘’ using FORTRAN routine, constant dimensions’’)’) time1
 type *,’c(25,25) = ‘,c(25,25)
 
 ticks1 = ticks()
 call mat_mul_pas(c,%val(50),a,%val(50),b,%val(50),%val(50),%val(50),%val(50))
 
 ticks2 = ticks()
 time1 = (ticks2-ticks1)/60.
 type *
 write (6,’(f8.4,’’ seconds for multiplying matrices’’,
     *  ‘’ using PASCAL routine’’)’) time1
 type *,’c(25,25) = ‘,c(25,25)
 
 ticks1 = ticks()
 call mat_mul_pas_opt(c,%val(50),a,%val(50),b,%val(50),%val(50),%val(50),%val(50))
 
 ticks2 = ticks()
 time1 = (ticks2-ticks1)/60.
 type *
 write (6,’(f8.4,’’ seconds for multiplying matrices’’,
     *  ‘’ using PASCAL routine, hand-optimized’’)’) time1
 type *,’c(25,25) = ‘,c(25,25)
 
 ticks1 = ticks()
 call mat_mul_c(c,%val(50),a,%val(50),b,%val(50),%val(50),%val(50),%val(50))
 
 ticks2 = ticks()
 time1 = (ticks2-ticks1)/60.
 type *
 write (6,’(f8.4,’’ seconds for multiplying matrices’’,
     *  ‘’ using C routine’’)’) time1
 type *,’c(25,25) = ‘,c(25,25)
 
 ticks1 = ticks()
 call mat_mul_c_opt(c,%val(50),a,%val(50),b,%val(50),%val(50),%val(50),%val(50))
 
 ticks2 = ticks()
 time1 = (ticks2-ticks1)/60.
 type *
 write (6,’(f8.4,’’ seconds for multiplying matrices’’,
     *  ‘’ using C routine, hand-optimized’’)’) time1
 type *,’c(25,25) = ‘,c(25,25)
 
 end

!!S Main
 subroutine mat_mult_for3(c,nc,a,na,b,nb,n1,n2,n3)
c sets c=a.b
c na,nb,nc are first dimensions
c n1 n2 n3 are problem dimensions
c c is n1xn3
c a    n1 n2
c b    n2 n3
 implicit none
 
 integer na,nb,nc,n1,n2,n3
 integer*2 i,j,k
 extended c(nc,n3),a(na,n2),b(nb,n3)
 
 do k=1,n3
 do i=1,n1
 c(i,k) = 0x0
 do j=1,n2
 c(i,k) = c(i,k)+a(i,j)*b(j,k)
 end do
 end do
 end do
 return
 end

!!S Main
 subroutine mat_mult_for1(c,nc,a,na,b,nb,n1,n2,n3)
c
csame as before, invariant matrix element eliminated from loop
c
 implicit none
 
 integer na,nb,nc,n1,n2,n3
 integer*2 i,j,k
 extended c(nc,n3),a(na,n2),b(nb,n3)
 extended sum 
 
 do k=1,n3
 do i=1,n1
 sum = 0x0
 do j=1,n2
 sum = sum+a(i,j)*b(j,k)
 end do
 c(i,k) = sum
 end do
 end do
 return
 end

!!S Main
 subroutine mat_mult_for0(c,nc,a,na,b,nb,n1,n2,n3)
c
csame as before, with constant dimensions
c
 implicit none
 
 integer na,nb,nc,n1,n2,n3
 integer*2 i,j,k
 extended c(50,50),a(50,50),b(50,50)
 extended sum 
 
 do k=1,n3
 do i=1,n1
 sum = 0x0
 do j=1,n2
 sum = sum+a(i,j)*b(j,k)
 end do
 c(i,k) = sum
 end do
 end do
 return
 end

!!S Main
 integer function ticks
 ticks = long(362)
 return
 end

Listing 2 : non-optimized Fortran routine           
!!S Main
 subroutine mat_mult_for(c,nc,a,na,b,nb,n1,n2,n3)
c
cduplicate of mat_mul_for3 for compiling without optimization
c
 implicit none
 
 integer na,nb,nc,n1,n2,n3
 integer*2 i,j,k
 extended c(nc,n3),a(na,n2),b(nb,n3)
 
 do k=1,n3
 do i=1,n1
 c(i,k) = 0x0
 do j=1,n2
 c(i,k) = c(i,k)+a(i,j)*b(j,k)
 end do
 end do
 end do
 return
 end

Listing 3 : Pascal routine

{$S Main}
{$R-}
unit matmul;

interface

type matrix = array [1..50,1..50] of extended;

procedure mat_mul_pas
 (var c : matrix; nc : longint;
  var a : matrix; na : longint;
  var b : matrix; nb : longint;
  n1,n2,n3:longint);

procedure mat_mul_pas_opt
 (var c : matrix; nc : longint;
  var a : matrix; na : longint;
  var b : matrix; nb : longint;
  n1,n2,n3:longint);

implementation

procedure mat_mul_pas;
var
 i,j,k:integer;
begin
 for k:=1 to n3 do
 for i:=1 to n1 do
 begin
 c[i,k] := 0;
 for j:=1 to n2 do
 c[i,k] := c[i,k]+a[i,j]*b[j,k];
 end;
end;

procedure mat_mul_pas_opt;
var
 i,j,k:integer; sum:extended;
begin
 for k:=1 to n3 do
 for i:=1 to n1 do
 begin
 sum := 0;
 for j:=1 to n2 do
 sum := sum+a[i,j]*b[j,k];
 c[i,k] := sum;
 end;
end;

end.

Listing 4 : C routine

pascal void mat_mul_c 
 (extended c[50][], long nc,
  extended a[50][], long na,
  extended b[50][], long nb,
  long n1, long n2, long n3)

{
 int i,j,k;
 
 for ( k=1 ; k <= n3; k++ )
 for ( i=1 ; i <= n1 ; i++ )
 {
 c[i][k] = 0.0;
 for ( j=1 ; j <= n2 ; j++ )
 c[i][k] = c[i][k]+a[i][j]*b[j][k];
 }
}

pascal void mat_mul_c_opt
 (extended c[50][], long nc,
  extended a[50][], long na,
  extended b[50][], long nb,
  long n1, long n2, long n3)

{
 register int i,j,k;
 register extended sum;
 
 for ( k=1 ; k <= n3; k++ )
 for ( i=1 ; i <= n1 ; i++ )
 {
 sum = 0.0;
 for ( j=1 ; j <= n2 ; j++ )
 sum = sum+a[i][j]*b[j][k];
 c[i][k] = sum;
 }
}

Listing 5 : inner loops compared, Nosy-disassembled

pascal, optimized
lan_3 MOVEA.L  param2(A6),A0
 MOVE D6,D0
 MULS #$258,D0
 MOVE D5,D1
 MULS #12,D1
 ADD  D1,D0
 MOVEA.Lparam3(A6),A1
 MOVE D5,D1
 MULS #$258,D1
 MOVE D7,D2
 MULS #12,D2
 ADD  D2,D1
 LEA  -$264(A0),A0
 FMOVE.X0(A0,D0.W),FP0
 LEA  -$264(A1),A0
 FMUL.X 0(A0,D1.W),FP0
 FADD FP7,FP0  ; could use
 FMOVE  FP0,FP7  ; FADD FP0,FP7 here
 ADDQ #1,D5
 BVS.S  lan_5
lan_4 CMP.W van_1(A6),D5
 BLE  lan_3

c, optimized
lar_1 MOVE.LD7,D0
 MOVE.L D0,D1
 MULU #12,D0
 SWAP D1
 MULU #12,D1
 SWAP D1
 CLR  D1
 ADD.L  D1,D0
 ADD.L  D6,D0
 MOVE.L D5,D1
 MOVE.L D1,D2
 MULU #12,D1
 SWAP D2
 MULU #12,D2
 SWAP D2
 CLR  D2
 ADD.L  D2,D1
 ADD.L  D7,D1
 FMOVE.X  0(A3,D0.L),FP0
 FMUL.X 0(A4,D1.L),FP0
 FMOVE  FP7,FP1
 FADD FP0,FP1
 FMOVE  FP1,FP7
 ADDQ.L #1,D7
lar_2 CMP.L D7,D4
 BGE  lar_1

pascal, plain
lam_3 MOVEA.L  param2(A6),A0
 MOVE D6,D0
 MULS #$258,D0
 MOVE D5,D1
 MULS #12,D1
 ADD  D1,D0
 MOVEA.L  param3(A6),A1
 MOVE D5,D1
 MULS #$258,D1
 MOVE D7,D2
 MULS #12,D2
 ADD  D2,D1
 LEA  -$264(A0),A0
 FMOVE.X 0(A0,D0.W),FP0
 LEA  -$264(A1),A0
 FMUL.X 0(A0,D1.W),FP0
 MOVE D6,D0
 MULS #$258,D0
 MOVE D7,D1
 MULS #12,D1
 ADD  D1,D0
 LEA  -$264(A4),A0
 FADD.X 0(A0,D0.W),FP0
 MOVE D6,D0
 MULS #$258,D0
 MOVE D7,D1
 MULS #12,D1
 ADD  D1,D0
 LEA  -$264(A4),A0
 FMOVE.X FP0,0(A0,D0.W)
 ADDQ #1,D5
 BVS.S  lam_5
lam_4 CMP.W vam_1(A6),D5
 BLE  lam_3

c, plain
lao_3 MOVE.LD5,D0
 MOVE.L D0,D1
 MULU #12,D0
 SWAP D1
 MULU #12,D1
 SWAP D1
 CLR  D1
 ADD.L  D1,D0
 ADD.L  D6,D0
 MOVE.L D7,D1
 MOVE.L D1,D2
 MULU #12,D1
 SWAP D2
 MULU #12,D2
 SWAP D2
 CLR  D2
 ADD.L  D2,D1
 ADD.L  D6,D1
 MOVEA.L  param3(A6),A0
 MOVE.L D5,D2
 MOVE.L D2,D3
 MULU #12,D2
 SWAP D3
 MULU #12,D3
 SWAP D3
 CLR  D3
 ADD.L  D3,D2
 ADD.L  D7,D2
 FMOVE.X  0(A4,D1.L),FP0
 FMUL.X 0(A0,D2.L),FP0
 FADD.X 0(A3,D0.L),FP0
 MOVE.L D5,D0
 MOVE.L D0,D1
 MULU #12,D0
 SWAP D1
 MULU #12,D1
 SWAP D1
 CLR  D1
 ADD.L  D1,D0
 ADD.L  D6,D0
 FMOVE.X FP0,0(A3,D0.L)
 ADDQ.L #1,D7
lao_4 CMP.L D7,D4
 BGE  lao_3

Fortran, optimized
lah_3 MOVE-172(A6),D2
 EXT.L  D2
 EXT.L  D2
 SUB.L  -142(A6),D2
 MULS.L #12,D2 
 MOVE.L D2,D0
 MOVE -170(A6),D2
 EXT.L  D2
 EXT.L  D2
 SUB.L  -130(A6),D2
 MULS.L -134(A6),D2 
 ADD.L  D0,D2
 MOVEA.L  32(A6),A0
 ADDA.L D2,A0
 FMOVE.X  (A0),FP7
 MOVE -170(A6),D2
 EXT.L  D2
 EXT.L  D2
 SUB.L  -118(A6),D2
 MULS.L #12,D2 
 MOVE.L D2,D1
 MOVE -168(A6),D2
 EXT.L  D2
 EXT.L  D2
 SUB.L  -106(A6),D2
 MULS.L -110(A6),D2 
 ADD.L  D1,D2
 MOVEA.L  24(A6),A1
 ADDA.L D2,A1
 FMUL.X (A1),FP7
 FADD.X -94(A6),FP7
 FMOVE.X  FP7,-94(A6)
 ADDQ #1,-170(A6)
 SUBQ.L #1,D5
 BGT  lah_3

Fortran, plain
lae_3 MOVE-164(A6),D2
 EXT.L  D2
 EXT.L  D2
 SUB.L  -134(A6),D2
 MULS.L #12,D2 
 MOVE.L D2,D0
 MOVE -162(A6),D2
 EXT.L  D2
 EXT.L  D2
 SUB.L  -122(A6),D2
 MULS.L -126(A6),D2 
 ADD.L  D0,D2
 MOVEA.L  32(A6),A0
 ADDA.L D2,A0
 FMOVE.X  (A0),FP7 ; get a(i,k)
 MOVE -162(A6),D2
 EXT.L  D2
 EXT.L  D2
 SUB.L  -110(A6),D2
 MULS.L #12,D2 
 MOVE.L D2,D1
 MOVE -160(A6),D2
 EXT.L  D2
 EXT.L  D2
 SUB.L  -98(A6),D2
 MULS.L -102(A6),D2 
 ADD.L  D1,D2
 MOVEA.L  24(A6),A1
 ADDA.L D2,A1
 FMUL.X (A1),FP7 ; multiply by b(i,k)
 MOVE -164(A6),D2
 EXT.L  D2
 EXT.L  D2
 SUB.L  -158(A6),D2
 MULS.L #12,D2 
 MOVE.L D2,D1
 MOVE -160(A6),D2
 EXT.L  D2
 EXT.L  D2
 SUB.L  -146(A6),D2
 MULS.L -150(A6),D2 
 ADD.L  D1,D2
 MOVEA.L  40(A6),A1
 ADDA.L D2,A1
 FADD.X (A1),FP7 ; add c(i,k)
 MOVE -164(A6),D2; this
 EXT.L  D2; whole
 EXT.L  D2; stuff
 SUB.L  -158(A6),D2; is
 MULS.L #12,D2  ;
 MOVE.L D2,D1  ; R
 MOVE -160(A6),D2; E
 EXT.L  D2; D
 EXT.L  D2; U
 SUB.L  -146(A6),D2; N
 MULS.L -150(A6),D2; D
 ADD.L  D1,D2  ; A
 MOVEA.L  40(A6),A1; N
 ADDA.L D2,A1  ; T !!!!
 FMOVE.X  FP7,(A1) ; put back c(i,k)
 ADDQ #1,-162(A6)
 SUBQ.L #1,D5
 BGT  lae_3