Geek asks and answers

Why is std :: find implemented this way?

I fall into the source std::findand find this confusing for me. It basically divides the number of items by 4 and makes a comparison of 4 in each round:

template<typename _RandomAccessIterator, typename _Tp>
_RandomAccessIterator
__find(_RandomAccessIterator __first, _RandomAccessIterator __last,
   const _Tp& __val, random_access_iterator_tag)
{
  typename iterator_traits<_RandomAccessIterator>::difference_type
__trip_count = (__last - __first) >> 2;

  for (; __trip_count > 0; --__trip_count)
{
  if (*__first == __val)
    return __first;
  ++__first;

  if (*__first == __val)
    return __first;
  ++__first;

  if (*__first == __val)
    return __first;
  ++__first;

  if (*__first == __val)
    return __first;
  ++__first;
}

  switch (__last - __first)
{
case 3:
  if (*__first == __val)
    return __first;
  ++__first;
case 2:
  if (*__first == __val)
    return __first;
  ++__first;
case 1:
  if (*__first == __val)
    return __first;
  ++__first;
case 0:
default:
  return __last;
}
}

I have no idea why this is. Sounds like some kind of optimization. But I don’t think it will be easy to use multi-core processors. It is anyway.

Any ideas?

+5
source share
4 answers

Similar to loop unwinding , also known as loop reversal.

+7
source

Loop deployment. The result is the same, but it is more processor friendly.

The asymptotic complexity is the same, though.

+4
source

This is a Duff device . This is an old optimization technique that mixes and switches applications in a special way. It uses a U-turn loop. In assembler, you have to jump directly into the expanded loop.

-2
source

More articles:


All Articles