Author: Mathieu Pagé
Date: 07:54:14 07/21/04
Go up one level in this thread
On July 21, 2004 at 10:32:02, Mathieu Pagé wrote:
>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.