Author: Mathieu Pagé
Date: 07:32:02 07/21/04
Go up one level in this thread
On July 20, 2004 at 19:12:36, Álvaro Begué wrote:
>By keeping several different max_value variables, you can break the dependency
>chain between iterations of the loop.
>
>
>int find_max_original(int const *values){
> int max_value = 0, i;
>
> for (i=0; i<= 99; i++) {
> if (values[i] > max_value) max_value = values[i];
> }
>
> return max_value;
>}
>
>int find_max_faster(int const *values){
> int max_value_0=values[0];
> int max_value_1=values[1];
> int max_value_2=values[2];
> int max_value_3=values[3];
> int const *end = values+100;
> for(values+=4;values!=end;values+=4){
> if(max_value_0<values[0])
> max_value_0=values[0];
> if(max_value_1<values[1])
> max_value_1=values[1];
> if(max_value_2<values[2])
> max_value_2=values[2];
> if(max_value_3<values[3])
> max_value_3=values[3];
> }
> if(max_value_0<max_value_1)
> max_value_0=max_value_1;
> if(max_value_2<max_value_3)
> max_value_2=max_value_3;
> if(max_value_0<max_value_2)
> max_value_0=max_value_2;
>
> return max_value_0;
>}
>
>
>find_max_faster() is more than twice as fast as find_max_original(). I'm using
>gcc 3.4.0 with options -O3 and -mpentium4.
>
>Can other people, please, test it with other compilers?
Hi I tested your find_max_faster with MSVC++ and it is 2.7 times faster than
find_max_original. However I modified it a little bit to create
find_max_faster_with_bit_hack to get this :
<code>
__forceinline int max(int x, int y)
{
return x - ((x - y) & ((x - y) >> (sizeof(int) * 8 - 1))); // max(x, y)
}
int find_max_faster_with_bit_hack(int const *values){
int max_value_0=values[0];
int max_value_1=values[1];
int max_value_2=values[2];
int max_value_3=values[3];
int const *end = values+NB;
for(values+=4;values!=end;values+=4){
max_value_0 = max(max_value_0,values[0]);
max_value_1 = max(max_value_1,values[1]);
max_value_2 = max(max_value_2,values[2]);
max_value_3 = max(max_value_3,values[3]);
}
if(max_value_0<max_value_1)
max_value_0=max_value_1;
if(max_value_2<max_value_3)
max_value_2=max_value_3;
if(max_value_0<max_value_2)
max_value_0=max_value_2;
return max_value_0;
}
</code>
This on my laptop at work is 5.36 time faster than find_max_original it is
pretty fast for an algorithm I first thought was optimal.
Mathieu P.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.