internal implementation std::find in C++

Question

I noticed something in the internally implemented std::find that perplexed me; why did they do that?

std::find(begin,end,...) Assume this line , so in the internal implementation in the file stl_algobase.h , Line:2064 is:

      typename iterator_traits<_RandomAccessIterator>::difference_type
    __trip_count = (__last - __first) >> 2;

What happened here? Why did they subtract together and then use the shift operator? I can't understand why they did this? (Sorry if this is a beginner's question.)

Peracid

Usually compilers are capable of optimising x / 4 to x >> 2 ... so it is just copy-paste from legacy optimisation or deliberate obfuscation by author. – Steed

As a side note: the standard library is optimized so our sloppy code runs with decent performance. Take the tour and have a look but you can use it even if you don't understand everything. – Imprimatur

Answer 1

It's a loop unrolling optimization of sorts.

auto size = __last - __first;
__trip_count = size / 4; // Instead of >> 2

for(;__trip_count>0; __trip_count--){
  // do 4 sequential tests
  ++first;      ++first;      ++first;      ++first;
}

// The switch takes care of the remaining 0, 1, 2 or 3 checks.

The entire implementation is

template<typename _RandomAccessIterator, typename _Predicate>
    _GLIBCXX20_CONSTEXPR
    _RandomAccessIterator
    __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
          _Predicate __pred, random_access_iterator_tag)
    {
      typename iterator_traits<_RandomAccessIterator>::difference_type
    __trip_count = (__last - __first) >> 2;

      for (; __trip_count > 0; --__trip_count)
    {
      if (__pred(__first))
        return __first;
      ++__first;

      if (__pred(__first))
        return __first;
      ++__first;

      if (__pred(__first))
        return __first;
      ++__first;

      if (__pred(__first))
        return __first;
      ++__first;
    }

      switch (__last - __first)
    {
    case 3:
      if (__pred(__first))
        return __first;
      ++__first;
      // FALLTHRU
    case 2:
      if (__pred(__first))
        return __first;
      ++__first;
      // FALLTHRU
    case 1:
      if (__pred(__first))
        return __first;
      ++__first;
      // FALLTHRU
    case 0:
    default:
      return __last;
    }
    }

From https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algobase.h#L2059

Fireboat

thanks for the answer, the number of steps(magic number 4) is dependent? – Peracid

@AnotherHM The value 4 is just a compromise between code size and less jumping. 8 is another often used number. They have quite likely tested it and found 4 to be well balanced. – Fireboat

Sorry for the question extending in the comment , Thank you so much. – Peracid