Re: Performance of Integer Multiplication on PIII (Results forgcc-2.95 & Athlon)

[pete at ltoi dot iap dot physik dot tu-darmstadt dot de]

Hi,

meanwhile i played a bit with Kevin's source on my Athlon.

As a (first) summary, i could say, that the problem is twofold:

  - 1.: a severe alignmend problem
  - 2.: the new 3.0 x86-backend performs poorer than in the gcc-2.95
        series

Just an excert from the attached tar file (bzip2 compressed)

Some results for AMD K7 (Athlon) Model 1, 600 Mhz

{Note: static const double   cpu_speed not changed }  (sorry)

 [h]gcc -O2 -march=i686 -s -o imul imul.c read_empty.c read.c

gcc-2.95.2,3 (haifa):
 Loop: 1.01, Code: 2.57
 Clocks: 19.15

gcc-2.95.2: (normal scheduler)
 Loop: 1.01, Code: 3.02
 Clocks: 22.50

gcc-3.0.2 & gcc-3.0-haifa
 Loop: 0.90, Code: 3.35
 Clocks: 24.96

gcc-295.2 (haifa) -O2 -march=i686 -s -o imul imul.c read_empty.c read_asm.s
  Loop: 1.01, Code: 3.02
  Clocks: 22.50

gcc-295.2 (haifa) -O2 -march=i686 -s -o imul imul.c read_empty.c read_iasm.s
 Loop: 1.00, Code: 2.24
 Clocks: 16.69

gcc3.0.2 -O2 -march=i686 -s -o imul imul.c read_empty.c read_iasm.s
 Loop: 0.90, Code: 2.46
 Clocks: 18.33

 ... some more results ...

so far, so bad, but now look, if i exchanged read.c with read2.c

read2.c:

unsigned read(const unsigned * spl)
{
   return
    (((((( spl[7]*6+spl[6])*6+spl[5])*6
                   +spl[4])*7+spl[3])*7+spl[2])*7+spl[1])*7+spl[0];
}

the following results show up

gcc-2.95.2 -O2 -march=i686
 Loop: 1.01, Code: 2.35
 Clocks: 17.51

gcc-2.95.2 (haifa) -O2 -march=i686
 Loop: 1.01, Code: 2.35
 Clocks: 17.51

gcc-2.95.2 (haifa) -O2 -march=i586
 Loop: 1.01, Code: 2.35
 Clocks: 17.51

gcc3.0.2 -O2 -march=i586
 Loop: 0.90, Code: 2.92
 Clocks: 21.75

gcc3.0.2 -O2 -march=i686
 Loop: 0.90, Code: 2.92
 Clocks: 21.75

gcc3.0.2 -O2 -march=k6
 Loop: 0.90, Code: 4.03
 Clocks: 30.02

gcc3.0.2 -O2 -march=athlon
 Loop: 0.90, Code: 2.57
 Clocks: 19.15

And now we outperform (again) the famous Intel compilers with gcc!

-ffplfj=2:= -fomit-frame-pointer -malign-loops=2 -malign-functions=2
            -malign-jumps=2

gcc3.0.2 -O2 -march=athlon -ffplfj=2
 Loop: 2.35, Code: 0.90
 Clocks: 6.70

gcc3.0.2 -O2 -march=[i686,i586] -ffplfj=2
 Loop: 0.79, Code: 2.45
 Clocks: 18.25

gcc3.0.2 -O2 -march=k6 -ffplfj=2
 Loop: 2.35, Code: 2.57
 Clocks: 19.15

gcc-2.95.2 (haifa) -O2 -march=[i686,i586,k6] -ffplfj=2
 Loop: 2.46, Code: 0.90
 Clocks: 6.70

Now again read.c

gcc3.0.2 -O2 -march=athlon -ffplfj=2
 Loop: 2.36, Code: 1.78
 Clocks: 13.26

gcc-2.95.2 (haifa) -O2 -march=i686 -ffplfj=2
 Loop: 2.46, Code: 1.35
 Clocks: 10.06

Now with read_asm.s

gcc-2.95.2 (haifa) -O2 -march=i686 -ffplfj=2
 Loop: 2.47, Code: 1.56
 Clocks: 11.62

Now with read_iasm.s

gcc-2.95.2 (haifa) -O2 -march=i686 -ffplfj=2
 Loop: 2.47, Code: 0.89
 Clocks: 6.63
(... Intel's icc not _that_ bad ... but gcc too!)


Thus, it's both, an alignmend issue & an optimization issue ...

I may add, that this system was SuSE-6.2 (glibc-2.1.1) & it had the
new binutils (2.11.2) in the usr/local path.

On Mon, 5 Nov 2001, Jan Hubicka wrote:

> > On Sat, 3 Nov 2001, Tim Prince wrote:
> >
> > > >  Form Agner Fog (http://www.agner.org/assem/) pentopt.zip
> > > >
> > > >                  PPlain      PMMX    PPro    PII   PIII
> > > >  IMUL latency       9          9       4      4      4
> > > >  IMUL throughput   1/9        1/9     1/1    1/1    1/1
> > > >
> > > >  That means, imul is pipelined on i686 ...
> > > >
> > > > > So I guess the lesson here is that on PIII integer multiplication is
> > > fast
> > > > > enough that doing special tricks to avoid integer multiplication will
> > > hurt
> > > > > performs in stead of helping it.
> > > >
> > > Even on the P4, code which permits full pipelining will run well with
> > > imul, while the add and shift sequences are preferable in contexts where
> > > that is not possible.  I haven't seen any compiler which is able to
> > > distinguish those situations.
> >
> > The Intel compiler seams to be able to as it gets about the same results
> > as my hand coded assembly did.  It should not be two difficult to tell when
>
> Maybe it is because the gcc's algorithm is based purely on the instruction
> latencies, not the troughtput (as it is dificult to estimate the troughput of
> genrated sequence in early compilation passes).
>
> Perhaps we can aritifically lower the gcc's imul cost on Pentiums if it results
> in better code, but this needs some larger scale benchmark than your testcase.
>
> You can try to edit the config/i386/i386.c the pentiumpro_cost structure and
> see what happends.
>
> At the moment it says:
>
>   1,					/* cost of an add instruction */
>   1,					/* cost of a lea instruction */
>   1,					/* variable shift costs */
>   1,					/* constant shift costs */
>   4,					/* cost of starting a multiply */
>
> That is consistent with the numbers above.
>
> BTW
> probably I see the problem - gcc relies on fact that lea instruction has one
> cycle, while on pentiums IMO the lea is decomposed to primitive instructions.
> Perhaps all we need is to show this fact to gcc in RTX_COST.
>
> I will prepare patch shortly.
>
> Honza

... i think the above findings gives a new picture ...

>
> > imul is preferable.  It would seam to me this can be done by calculating
> > a dependency tree on a block of code and then see if the latency of the
> > imul will prevent anything else from calculating....
>

....

Peter

PS.:
Sorry for the delay, but my time-zone seems to 10h apart from yours, so
early response is unlikely ...

-- on the other topic: i586 and i686 are the gcc standard -march
   suboptions ... they are short & have clear meaning. They did, what
   they propose to do. Thus i don't understand dewar's statement.
   What did you prefer?

   For the other (i786): I can agree. It's just a matter of how
   gcc tells this architecture (pentium4, if i am remember right)
   It was only for not to intermix P4 issues with i686 (aka pentiumpro
   or P6 whatever you like more). I.e.: different arch &c.

- But then, the question remains: What will "umame -m" will give
  us on P4 systems? Since this may trigger special compiler option
  selection in (at least my) Makefiles. And if "they" alias it to
  i686, well, then the P4 must live with the wrong ...

> Robert Lipe:

> You mean, on i[3456] and P4 (we may call it i786 for convienience)?

> Let's please not.  We've already contrived two of the four names above
> that we have.  We don't run around making up names for Sparc, MIPS, or
> Power.

> RJL

dewar:

> <<Let's please not.  We've already contrived two of the four names above
> that we have.  We don't run around making up names for Sparc, MIPS, or
> Power.
> >>

> I definitely agree with this, the use of the terms 586 and 686 is bad
enough.

(source for crosschecks)