Почему std :: find реализован таким образом?

Question

Я случайно столкнулся с источником std::find и считаю это сбивающим с толку. В основном он делит количество элементов на 4 и сделайте сравнение 4 в каждом раунде:

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; 
} 
} 

Я понятия не имею, почему это делается таким образом. Похоже на некоторую оптимизацию. Но я не думаю, что это будет легко использовать многоядерные процессоры. Это в любом случае.

Любые идеи?

Answer 1

Похож на loop unwinding, также известный как разворот цикла.

Answer 2

Это петля для разворота. Результат тот же, но он более дружелюбен для процессора.

Асимптотическая сложность такая же.

Answer 3

Это Duff's device. Это старая техника оптимизации , которая смешивает в то время как и переключает заявления особым образом. Он использует разворот цикла. В ассемблере вы прыгаете прямо в развернутом цикле.

Answer 4

Не совсем уверен, я думаю, что это своего рода разворот цикла.

См Петля разворачивая в: http://www.codeproject.com/Articles/6154/Writing-Efficient-C-and-C-Code-Optimization