Re: RES: RES: [Dev-C++] Optimizing C code, what is best??

What we could see was that the original loop didn't allow inlining. By
just touching it enough to get inlining, we get a 50% speed increase (for
all but the memory-choked Celeron machine that used an older compiler).

We didn't have to do much, it was just a 2-minute change to get gcc to fit
the loop within available registers.

One nice thing about newer x86 processors is that if the array elements is
sized 2^x, the processor can use it's built-in barrel-shifter and do a
constant-time multiply when loading values from the array, i.e. src[i],
where it i in this case gets automatically multiplied by 2 at each access.
Thank you Intel. This allows the removal of a src++ without any cost. But
it doesn't always work - depending on the array-element size. Besides,
with multiple integer pipes the processor might squeeze in the src++
operation somewhere anyway.

The previous post was without -fexpensive-optimizations.

The following is tests with your modified loop:
Compiler: gcc 3.2
Optimization: -O3, -march=pentium3, -fexpensive-optimizations.
Machine1 = Pentium II, 2*400MHz, PC100
Machine3 = AMD XP2600+, PC3200 CL2.5
Timing: In seconds wall-time.
CPU load: >= 98%

1 billion loops, 7 columns
Machine:  1     3
Loop 1    198   31
Loop 2    234   29
Loop 3    100   12
Loop 3b   157   28
Loop 4    199   38

100 milion loops, 200 columns
Machine:   1      3
Loop 1        87
Loop 2        93
Loop 3        65
Loop 3a       80
Loop 4        73
'
I must say that I am puzzles why I couldn't get similar results as your
PIII processor. However, with the expensive-opt on, the inlined code in
main() is very, very hard to read :-( while giving just about the same
times as from my previous mail without the flag.

However, it looks like the compiler fucked up to align the 3A loop when it
inlined it. The following is a test with -O2, i.e. no inlining - the
non-inlined methods do align the loop.

100 million loops, 200 columns
Machine:   3
Loop 1    412
Loop 2    425
Loop 3    380
Loop 3b   360
Loop 4    370

In this case I got an improvement from Loop 3b. However, let the numbers
talk. I would definitely recomment inlining...

/Per W

On Sat, 31 May 2003, Daniel K. O. wrote:

>
>
>  >  It is nice that you can laugh at my code. However, I DID benchmark
>  >  the code before writing the previous mail...
>
>
> Well, I didn't say that, sorry if you got pissed with what I said. I didn't
> said that optimizing coded is useless.
> You really did optimize some stuffs, and I didn't say that everything would
> be automagically optimized; I pointed out that there are some minor details
> that some people still think that can be "optimized" by just writing the
> same commands in a different way (not necessarily a different
> algorithm/order).
>
> I modified your code a little, to just show what I really said:
>
>
> ---
> #include <time.h>
> #include <stdio.h>
>
> #define MAX 100000000 // your code have an extra zero, I took it out so we
> won't measure the calling code, but the loop
>
>
> typedef unsigned __int64 DWORD64;
> typedef unsigned short WORD;
>
>
> class CTestClass {
>     public:
>         enum {
>             rows = 20,
>             cols = 200 // a some extra cols, so the loop can work more
>         };
>         short *sData[rows];
>         CTestClass();
>         DWORD64 computeDistance3(short *src,const WORD wRow,const WORD
> wColFrom,const WORD wColTo) const;
>         DWORD64 computeDistance3b(short *src,const WORD wRow,const WORD
> wColFrom,const WORD wColTo) const;
> };
>
> CTestClass::CTestClass() {
>     for (int r = 0; r < rows; r++) {
>         sData[r] = new short[cols];
>         for (int c = 0; c < cols; c++) {
>             sData[r][c] = r+c;
>         }
>     }
> }
>
> DWORD64 CTestClass::computeDistance3(short *src,const WORD wRow,WORD
> wColFrom,const WORD wColTo) const {
>     DWORD64 qwDist = 0;
>     int iA;
>     short *sp = sData[wRow] + wColFrom;
>     short *end = src + wColTo;
>     src += wColFrom;
>     while (src <= end) {
>         iA = *src++ - *sp++;
>         qwDist += iA*iA;
>     }
>     return qwDist;
> }
>
> // the same function, but with a for loop
> DWORD64 CTestClass::computeDistance3b(short *src,const WORD wRow,WORD
> wColFrom,const WORD wColTo) const {
>     DWORD64 qwDist = 0;
>     int iA;
>     short *sp = sData[wRow];
>
>     for (int i=wColFrom; i<=wColTo; ++i) {
>         iA =  src[i] - sp[i]; // not playing with pointers, but with indexes
>         qwDist += iA*iA;
>     }
>
>     return qwDist;
> }
>
> int main() {
>     CTestClass tst;
>     short v[CTestClass::cols] = {4,7,3,2,1,8,3};
>     int i;
>     time_t t0,t1,t2;
>     DWORD64 r1,r2;
>
>     t0 = time(NULL);
>     printf("start\n");
>     for (i = 0; i < MAX; i++)
>         r1 = tst.computeDistance3(v,5,0,tst.cols-1);
>
>     t1 = time(NULL);
>     printf("3 (%u) %I64u\n",(unsigned)(t1-t0),r1);
>     for (i = 0; i < MAX; i++)
>         r2 = tst.computeDistance3b(v,5,0,tst.cols-1);
>
>     t2 = time(NULL);
>     printf("3b (%u) %I64u\n",(unsigned)(t2-t1),r2);
> }
> ---
>
>
> My hardware: PIII 650 MHz
>
> Compiler options: -O3 -march=pentium3 -fexpensive-optimizations
>
> Output:
> ---
> start
> 3 (241) 2850410
> 3b (210) 2850410
> ---
>
>
>
> So, again: such details (like play with pointers vs. play with indexes)
> doesn't really matter. This is what I pointed out in the previous message.
> And I asked what you guys think; once you've found the bottleneck, if worth
> optimizing it in C going into minimum syntax details, or writing directly in
> assembly code.
>
>
>
>
> Daniel K. O.
>
>
>