Perché std :: find è implementato in questo modo?

Question

Mi capita di imbattersi nella fonte di std::find e trovarlo confuso da me. In sostanza si divide il numero di elementi da 4 e fare il confronto 4 in ogni turno:

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

Non ho idea del motivo per cui è fatto in questo modo. Sembra un po 'di ottimizzazione. Ma non penso che questo avvantaggi il multi-core così facile. Questo è in una singola discussione comunque.

Qualche idea?

Answer 1

Sembra loop unwinding, noto anche come srotolamento del ciclo.

Answer 2

È lo srotolamento del ciclo. Il risultato è lo stesso, ma è più amichevole per il processore.

La complessità asintotica è la stessa però.

Answer 3

È Duff's device. È una vecchia tecnica di ottimizzazione che mescola mentre e cambia le istruzioni in un modo speciale. Utilizza il ciclo di annullamento. In assembler si saltava all'interno di un loop srotolato.

Answer 4

Non essendo completamente sicuro, penso che si tratti di un ciclo di srotolamento.

See Loop svolgimento in: http://www.codeproject.com/Articles/6154/Writing-Efficient-C-and-C-Code-Optimization