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

なぜこのように行われたのかわかりません。いくつかの最適化のように見えます。しかし、私はこれがマルチコアを簡単に利用できるとは思わない。これはとにかく1つのスレッドにあります。

アイデア？

Answer 1

loop unwinding（ループアンローリングとも呼ばれます）のように見えます。

Answer 2

ループアンローリングです。結果は同じですが、プロセッサにとってはより親切です。

しかし、漸近的複雑さは同じです。

Answer 3

これはDuff's deviceです。それは古い最適化技術 であり、whileとswitch文を特別な方法で組み合わせています。ループのアンロールが使用されます。アセンブラでは、アンロールされたループの中ですぐにジャンプします。

Answer 4

これは完全にはわかりませんが、これはループ展開のようなものだと思います。

ループのアンローリングを参照してください。http://www.codeproject.com/Articles/6154/Writing-Efficient-C-and-C-Code-Optimization