Thread: [Dev-C++] Optimizing C code, what is best??
Open Source C & C++ IDE for Windows
Brought to you by:
claplace
Menu
▾
▴
dev-cpp-users
|
From: Zodiaq <zo...@ac...> - 2003-05-30 15:16:30
|
Hello All Dev-cpp-users,
there is one function in my program that needs some optimization...
the problem is about computing distance between parts of two
vectors... currently it is done like this:
DWORD64 computeDistance( short *src, const WORD &wRow, const WORD
&wColFrom, const WORD &wColTo ) const
{
DWORD dwDist = 0;
INT iA;
short *sP = sData[ wRow ];
for( WORD wCol = wColFrom; wCol <= wColTo; ++wCol )
{
iA = src[ wCol ] - sP[ wCol ];
dwDist += iA * iA;
}
return dwDist;
}
src is element I want to compute distance from specified element of
big array of rows... gprof shows that this function takes over 90% of
total program time...
well, I know it is not about DevC++, but since I made progs under it
and this is quite simple problem, I hope that someone can and will
help me...
The best solution for me would be ASM code optimized for AMD Athlon
processor (for my computer, which as only one will run this code). For
someone with good knowledge of ASM this is only few moments, and for
me great deal of work - I don't know ASM a bit... so please someone
help me... thank you in advance!
--
regards, Zodiaq...
|
|
From: Per W. <pw...@ia...> - 2003-05-30 18:13:29
|
Some sugestions:
1 - you are summing 16-bit numbers into 32-bit, but returning 64-bit.
2 - you are sending in wRow,wColFrom,wColTo as references, despite not
having any intention of sending back any change.
3 - you are using a lot of variables in the loop.
4 - you are using a lot of indexing in the loop.
A suggested change might be:
DWORD CMyClass::computeDistSquare(const short *src,
const WORD wRow,
const WORD wColFrom,const
WORD wColTo) const
{
DWORD dwDist2 = 0;
int iA;
short *sp = sData[wRow] + wColFrom;
short *end = src + wColTo;
src += wColFrom;
while (src <= end) {
iA = *src++ - *sp++;
dwDist2 += iA*iA;
}
return dwDist2;
}
Now the loop uses 5 variables instead of 7 - each variable just 32-bit
large and fitting in a single register.
/Per W
On Fri, 30 May 2003, Zodiaq wrote:
> Hello All Dev-cpp-users,
>
> there is one function in my program that needs some optimization...
> the problem is about computing distance between parts of two
> vectors... currently it is done like this:
>
> DWORD64 computeDistance( short *src, const WORD &wRow, const WORD
> &wColFrom, const WORD &wColTo ) const
> {
> DWORD dwDist = 0;
> INT iA;
> short *sP = sData[ wRow ];
> for( WORD wCol = wColFrom; wCol <= wColTo; ++wCol )
> {
> iA = src[ wCol ] - sP[ wCol ];
> dwDist += iA * iA;
> }
> return dwDist;
> }
>
> src is element I want to compute distance from specified element of
> big array of rows... gprof shows that this function takes over 90% of
> total program time...
>
> well, I know it is not about DevC++, but since I made progs under it
> and this is quite simple problem, I hope that someone can and will
> help me...
>
> The best solution for me would be ASM code optimized for AMD Athlon
> processor (for my computer, which as only one will run this code). For
> someone with good knowledge of ASM this is only few moments, and for
> me great deal of work - I don't know ASM a bit... so please someone
> help me... thank you in advance!
>
> --
> regards, Zodiaq...
>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: eBay
> Get office equipment for less on eBay!
> http://adfarm.mediaplex.com/ad/ck/711-11697-6916-5
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www.noicys.cjb.net/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>
|
|
From: Daniel K. O. <dan...@ya...> - 2003-05-30 20:01:23
|
From Per:
> while (src <= end) {
> iA = *src++ - *sp++;
> dwDist2 += iA*iA;
> }
From Zodiaq:
> > for( WORD wCol = wColFrom; wCol <= wColTo; ++wCol )
> > {
> > iA = src[ wCol ] - sP[ wCol ];
> > dwDist += iA * iA;
> > }
It was really funny those recent comments about "the best way to write C
code for optimization".
Yeah, some years ago most compilers were just "smart assemblers". But
nowadays, worrying about stuffs like 'array[i++]' vs. '*pointer++' trying to
make it "easier" to the compiler doesn't make much sense. If your compiler
can't figure obvious stuffs - like iterating throgh an array - and make the
best code for it, the best way is to find a better compiler.
And GCC is a mature compiler; comments like "it can optimize in a way it
won't work" without any test-case that proves it has a *serious* bug, is a
little malicious.
Just before writing this mail, I tried with a small sample:
---
int foo2(int vet1[], int vet2[], int n)
{
int* i1 = vet1, *i2 = vet2, *j = vet1+n;
int c;
while(i1!=j)
c += *i1++ + *i2++;
return c;
}
int foo1(int vet1[], int vet2[], int n)
{
int i, c;
for (i=0; i<n; i++)
c += vet1[i] + vet2[i];
return c;
}
---
And compiled it with:
-S -march=pentium3 -O2
The results:
foo1 -- 30 lines
foo2 -- 29 lines
With just 1 instruction less (for this small example), I don't see the point
in rewriting the code to make it faster. If I want to spend my time making
it faster, better do it directly in assembly, not through C.
So, my question: do you guys think that really worth being so "paranoic"
about such details? I mean, obviously the algorithm design is important, but
is really needed to even care about the different ways to write the same
command, to see "which one is faster"?
Daniel K. O.
|
|
From: Per W. <pw...@ia...> - 2003-05-30 22:40:58
|
It is nice that you can laugh at my code. However, I DID benchmark
the code before writing the previous mail...
Don't stare yourself blind at number of instructions in the assembler
file.
Machine 1: Pentium II, 2*400MHz, 512MB PC100, W2K Pro
Machine 2: AMD Athlon 1300MHz, 1GB PC133, WinXP Pro
Machine 3: AMD XP2600+, 1GB 400MHz CL2.5, WinXP Pro
Machine 4: Celeron 2*566MHz, 512MB PC100, GNU/Linux Debian 3.0
Test 1: Loop from original mail
Test 2: Optimization 1
Test 3: Optimization 2 - the one I sent in mail
Test 4: Loop unrolling - failed because of code size/complexity
All times are in seconds calendar time, with the test program running at
>= 98% (except of course for the two dual-processor machines).
Machine 1: 2: 3: 4: Note:
Test 1: 198 60 32 193 (compiler inlined code)
Test 2: 233 54 29 223 (compiler inlined code)
Test 3: 100 24 12 168 (compiler inlined code)
Test 4: 198 71 37 132 (compiler unrolled loop 10 times)
The big loss for Test 4 was that it wasn't inlined, and since I made 1
billion calls with vector length 7, the method call time was significant.
Machine 1-3 used gcc 3.2 with -O3, -march=pentium3
Machine 4 used gcc 2.95 with -O3, -march=pentium
---
Same tests as above, but with -O2, i.e. no inlining
Machine 1: 2: 3: 4:
Test 1: 263 84 45 298
Test 2: 303 72 39 304
Test 3: 233 68 36 255
Test 4: 199 71 37 231
---
Conclusion: Loop alternative 3 was always advantageous for all
processors, with or without inlining. With inlining off, the manual
inlining of alternative 4 gave a further improvement for the P2 and
Celeron machines, while being just a bit slower for the AMD machines.
As can be seen, the different constructs did make a significant
difference, especially when inlining. Are you really sure that the above
results are just a laugh, and that nowadays, you don't have to bother
about your code anymore? If such a quick rewrite can be made to a
function consuming 50% of the total runtime, I'd say it is work
looking at the function.
---
#include <time.h>
#include <stdio.h>
typedef unsigned __int64 DWORD64;
typedef unsigned short WORD;
class CTestClass {
public:
enum {
rows = 20,
cols = 7
};
short *sData[rows];
CTestClass();
DWORD64 computeDistance1(short *src,const WORD &wRow,const WORD
&wColFrom,const WORD &wColTo) const;
DWORD64 computeDistance2(short *src,const WORD wRow,const WORD
wColFrom,const WORD wColTo) const;
DWORD64 computeDistance3(short *src,const WORD wRow,const WORD
wColFrom,const WORD wColTo) const;
DWORD64 computeDistance4(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::computeDistance1(short *src,const WORD &wRow,const
WORD &wColFrom,const WORD &wColTo) const {
DWORD64 qwDist = 0;
int iA;
short *sp = sData[wRow];
for (WORD wCol = wColFrom; wCol <= wColTo; ++wCol) {
iA = src[wCol] - sp[wCol];
qwDist += iA*iA;
}
return qwDist;
}
DWORD64 CTestClass::computeDistance2(short *src,const WORD wRow,WORD
wColFrom,const WORD wColTo) const {
DWORD64 qwDist = 0;
int iA;
short *sp = sData[wRow] + wColFrom;
src += wColFrom;
while (wColFrom++ <= wColTo) {
iA = *src++ - *sp++;
qwDist += iA*iA;
}
return qwDist;
}
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;
}
DWORD64 CTestClass::computeDistance4(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;
if (src > end) break;
iA = *src++ - *sp++;
qwDist += iA*iA;
if (src > end) break;
iA = *src++ - *sp++;
qwDist += iA*iA;
if (src > end) break;
iA = *src++ - *sp++;
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,t3,t4;
DWORD64 r1,r2,r3,r4;
t0 = time(NULL);
printf("start\n");
for (i = 0; i < 1000000000; i++) {
r1 = tst.computeDistance1(v,5,0,tst.cols-1);
}
t1 = time(NULL);
printf("1 (%u) %I64u\n",(unsigned)(t1-t0),r1);
for (i = 0; i < 1000000000; i++) {
r2 = tst.computeDistance2(v,5,0,tst.cols-1);
}
t2 = time(NULL);
printf("2 (%u) %I64u\n",(unsigned)(t2-t1),r2);
for (i = 0; i < 1000000000; i++) {
r3 = tst.computeDistance3(v,5,0,tst.cols-1);
}
t3 = time(NULL);
printf("3 (%u) %I64u\n",(unsigned)(t3-t2),r3);
for (i = 0; i < 1000000000; i++) {
r4 = tst.computeDistance4(v,5,0,tst.cols-1);
}
t4 = time(NULL);
printf("4 (%u) %I64u\n",(unsigned)(t4-t3),r4);
}
/Per W
On Fri, 30 May 2003, Daniel K. O. wrote:
>
> >From Per:
> > while (src <= end) {
> > iA = *src++ - *sp++;
> > dwDist2 += iA*iA;
> > }
>
> >From Zodiaq:
> > > for( WORD wCol = wColFrom; wCol <= wColTo; ++wCol )
> > > {
> > > iA = src[ wCol ] - sP[ wCol ];
> > > dwDist += iA * iA;
> > > }
>
>
>
>
> It was really funny those recent comments about "the best way to write C
> code for optimization".
> Yeah, some years ago most compilers were just "smart assemblers". But
> nowadays, worrying about stuffs like 'array[i++]' vs. '*pointer++' trying to
> make it "easier" to the compiler doesn't make much sense. If your compiler
> can't figure obvious stuffs - like iterating throgh an array - and make the
> best code for it, the best way is to find a better compiler.
> And GCC is a mature compiler; comments like "it can optimize in a way it
> won't work" without any test-case that proves it has a *serious* bug, is a
> little malicious.
>
> Just before writing this mail, I tried with a small sample:
>
> ---
> int foo2(int vet1[], int vet2[], int n)
> {
> int* i1 = vet1, *i2 = vet2, *j = vet1+n;
> int c;
> while(i1!=j)
> c += *i1++ + *i2++;
> return c;
> }
>
> int foo1(int vet1[], int vet2[], int n)
> {
> int i, c;
> for (i=0; i<n; i++)
> c += vet1[i] + vet2[i];
> return c;
> }
> ---
>
>
> And compiled it with:
>
> -S -march=pentium3 -O2
>
>
> The results:
> foo1 -- 30 lines
> foo2 -- 29 lines
>
> With just 1 instruction less (for this small example), I don't see the point
> in rewriting the code to make it faster. If I want to spend my time making
> it faster, better do it directly in assembly, not through C.
> So, my question: do you guys think that really worth being so "paranoic"
> about such details? I mean, obviously the algorithm design is important, but
> is really needed to even care about the different ways to write the same
> command, to see "which one is faster"?
>
>
>
>
>
>
> Daniel K. O.
>
>
>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: eBay
> Get office equipment for less on eBay!
> http://adfarm.mediaplex.com/ad/ck/711-11697-6916-5
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www.noicys.cjb.net/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>
|
|
From: Daniel K. O. <dan...@ya...> - 2003-05-31 06:33:49
|
> 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.
|
|
From: Per W. <pw...@ia...> - 2003-05-31 11:38:17
|
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.
>
>
>
|
|
From: Per W. <pw...@ia...> - 2003-05-31 11:28:52
|
Forgot timing for one machine.
Also - as can be seen, there is seldom (just about never) any real use for
assembler optimization. With a little help and optimization tweaking, gcc
will generate optimal or nearly optimal code.
/Per W
On Sat, 31 May 2003, Per Westermark wrote:
> 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
PWM --> Corrected table.
> Machine: 1 3
> Loop 1 412 76
> Loop 2 425 75
> Loop 3 380 67
> Loop 3b 360 66
> Loop 4 370 73
>
> 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.
> >
> >
> >
>
>
|
