Optimising std::find on x86 and PPC

[Paolo Carlini]

Chris Jefferson wrote:

> I recently tried changing the std::find random_access overload to 
> change the main loop from:
>
> difference_type __trip_count = (__last - __first) >> 2;
> for(; __trip_count > 0 ; --__trip_count) { if(*__first = __val) return 
> __first; ++__first; (4 times)  }
>
> to:
>
> Iterator __newlast = __last - (__last - __first) % 4;
> for( ; __first < __newlast;){ if(*__first = __val) return __first; 
> ++__first; (4 times)  }
>
> This knocked about 30% off the time taken on x86

You are not giving many details: for instance whether you are seeing the 
improvement with/without -funroll-loops, which other optimization 
options (loop-unrolling related, in particular) you are using. 
Certainly, naively, the first form seems easier to analyze for the loop 
unroller.

If we can isolate a specific loop unrolling problem we can certainly ask 
Zdenek, Sebastian, Daniel and the others gurus of that area to work on 
it, and most probably will be fixed relatively soon.

Paolo.