From: bjj@ecl.psu.edu (Bryan J. Jensen)
Newsgroups: alt.folklore.computers,comp.unix.misc
Subject: Re: The need for an assembler (was: Favorite CPU)
Date: 13 Aug 92 01:04:31 EDT
Organization: Engineering Computer Lab, Pennsylvania State University

In article <1992Aug9.162439.7517W@lumina.edb.tih.no>, ketil@edb.tih.no (Ketil Albertsen,TIH) writes:

> Jensen continues:
> 
>>Those who optimize by tweaking the HLL source face a problem with
>>globally optimizing compilers - each time they make a small change
>>they have to check the entire program to make sure something unrelated
>>didn't break (in terms of performance).
> 
> This sounds as if it comes from someone who has never ever taken a close
> look at what modern compilers do today - most certainly not run timings
> on various optimization methods on the same problem. That a global
> optimization could cause a "small change" to "break (in terms of 
> performance)" "something unrelated" is just too far off. First: Global
> optimization is very rarely concerned with "small changes" (that is,
> local changes - most small changes are local; changes affecting interfaces
> are not small!). Second: Even if a global (interface) change caused the
> compiler to erroneously select the second best alternative (which is fully
> possible) in one single case, I cannot imagine a real-life situation where
> the difference between the very best and second best would be at all
> noticable on the system as a whole - and certainly not "break" the
> performance. Third: How could something unrelated be affected by a small
> or local change? The only way it could be affected is if it was related!
> 
> If Jensen (or anyone else) can bring up a case showing such a behaviour 
> due to global optimization and one small change (obviously by documenting
> the execution times for the same input data before and after), I will
> believe that it is possible, but you won't make me believe that it is
> the normal case, and not that it is a good reason for switching from HLL
> to assembler. 

Here is a real program used by lots of people.  This is one of those
problems which needs as much time as is available to solve.  There will
never be a computer fast enough to satisfy these people.  In addition,
there are millions of dollars being spent solving this class problem.
Speed is important.

I have included only the subroutine which requires significant time.
The part of concern is the 3 statements, KK = K, JJ = J, and II = I.
Adding them, and changing function calls to use KK,JJ,II instead of
K,J,I increased speed (by a factor of two I think).

C     PENN STATE UNIVERSITY FINITE DIFFERENCE TIME DOMAIN
C     ELECTROMAGNETIC ANALYSIS COMPUTER CODE

      SUBROUTINE EXSFLD
C
      INCLUDE   'COMMON.FOR'
C
      DO 100 K=2,NZ1
      KK = K
      DO 100 J=2,NY1
      JJ = J
      DO 100 I=1,NX1
C
C     DETERMINE MATERIAL TYPE
C
      IF(IDONE(I,J,K).EQ.0) GO TO 110
      IF(IDONE(I,J,K).EQ.1) GO TO 120
      IF(IDONE(I,J,K).GT.9) GO TO 110
      GOTO 130
C
  110   CONTINUE
C
C     VACUUM
C
      EXS(I,J,K)=EXS(I,J,K)+(HZS(I,J,K)-HZS(I,J-1,K))*DTEDYI(J)
     1                       -(HYS(I,J,K)-HYS(I,J,K-1))*DTEDZI(K)
C
      GO TO 100
C
  120 CONTINUE
C
C     PERFECT CONDUCTOR
C
      II = I
      EXS(I,J,K)=-EXI(II,JJ,KK)
C
      GO TO 100
C
  130 CONTINUE
C
C     LOSSY DIELECTRIC
C
      II = I
      EXS(I,J,K)=EXS(I,J,K)*ESCTC(IDONE(I,J,K))
     1    -EINCC( IDONE(I,J,K))*EXI(II,JJ,KK)
     2    -EDEVCN(IDONE(I,J,K))*DEXI(II,JJ,KK)
     3    +(HZS(I,J,K)-HZS(I,J-1,K))*ECRLY(J,IDONE(I,J,K))
     4    -(HYS(I,J,K)-HYS(I,J,K-1))*ECRLZ(K,IDONE(I,J,K))
C
  100 CONTINUE
C
      RETURN
      END
C     ********************************************************

The performance problem arose when function calls were added which
used the do-loop indices as arguments.  These functions were called
only a few times during the loop (as determined by the IDONE flags),
so they should not have changed the speed of the overall problem.
But, they did.  Looking at the code generated by the conditional
statements and functional calls would not have revealed a problem -
the problem was to be found in the unmodified code.

The 3 dimensional arrays above are accessed sequentially.  Thus,
array subscript calculations are not required.  A simple addition
during each loop pass is sufficient to calculate the next location.
The compiler knew this.

FORTRAN passes variables by reference (pass pointer to the value),
thus, a function is always free to change its arguments.

When the function arguments are the do-loop indices, the compiler
has no way of knowing that the function won't change the indices.
Thus, all the optimization it had done assuming sequential access
can no longer be done.  The result requires two additional multiplications
during each loop pass to calculate the array index.  This adds two
integer multiplys to the two floating point multiplys for each pass
through the loop (integer multiplys take longer on slow machines
since there's more bits to multiply).  Plus there are two extra additions.

The solution, of course, is to never pass do-loop indices to functions
or subroutines.

> Yes, there are optimizations that a human can see that a
> given compiler doesn't see, but there are ten times as many that a compiler
> sees but passes a human by - even though he in principle could see them,
> too. Optimizing compilers *are* smart today. From what Jensen writes,

>>Most C programmers lack the ability or initiative to add optimizations
>>to their C compiler.  More important, how is the C programmer to know
>>that his executable is wretchedly optimized?
> 
> it looks as if the C programmer must be concerned about the optimizations.
> Why? Usually, he must set some compiler switch, but that's all. Then he
> can benchmark his system before and after and enjoy the improvement. If 
> there was little or none, there is a great probability that hand asm
> would't do very much good either (ref. my first Prolog kernel translation).

A long time ago, someone paid a programmer to optimize this code.
Presumably this programmer used all the typical high level language
optimization techniques you mentioned (just one I think - the stopwatch).
Either the programmer missed the obvious, or the compiler changed after
the optimization was done, because he missed the problem with the indices
and functions.  But, now the word was out, this code had been
"professionally" optimized, so that's the way it stayed for years.

Most any assembly language programmer would have written this optimally
first time, and if he blew it, it would have been obvious.

You, however, favor giving an abstract description of the program
to a compiler, tinkering with compiler switches to see if it gets
any better, then declaring it perfection.
Newsgroups: alt.folklore.computers