Внутренняя реализация std::find в C++
Я заметил кое-что во внутренней реализации std::find, что меня озадачило; почему они это сделали?
Std::find(begin,end,...) Предположим, что это строка, поэтому во внутренней реализации в файле stl_algobase.h строка: 2064:
typename iterator_traits<_RandomAccessIterator>::difference_type
__trip_count = (__last - __first) >> 2;
Что здесь случилось? Почему они вычитали вместе, а затем использовали оператор сдвига? Не могу понять, зачем они это сделали? (Извините, если это вопрос новичка.)
В качестве примечания: стандартная библиотека оптимизирована, поэтому наш небрежный код работает с приличной производительностью. Возьмите тур и посмотрите, но вы можете использовать его, даже если вы не все понимаете.
Ответы 1
Это своего рода циклическая оптимизация.
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.
Вся реализация есть
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;
}
}
Из https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algobase.h#L2059
Спасибо за ответ, количество шагов (магическое число 4) зависит?
@AnotherHM Значение 4 - это просто компромисс между размером кода и меньшим количеством прыжков. 8 — еще одно часто используемое число. Вполне вероятно, что они проверили его и обнаружили, что 4 хорошо сбалансированы.
Извините за вопрос, распространяющийся в комментарии, большое спасибо.
Обычно компиляторы способны оптимизировать x/4 до x >> 2... так что это просто копипаста из устаревшей оптимизации или преднамеренное запутывание автором.