随机访问迭代器的GCC find/find_if超载有什么用处？

我发现这个片段，而在寻找<algorithm>实现：随机访问迭代器的GCC find/find_if超载有什么用处？

/** 
* @if maint 
* This is an overload used by find() for the RAI case. 
* @endif 
*/ 
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; 
} 
}

对于我的理解唯一的“绝招”这里是四if(...) return; ++和同样用switch内剩余distance % 4项目执行distance/4迭代。正如预期的那样，执行完全相同数量的比较和增量，理论上的复杂性是相同的。它是如何比平凡的输入迭代器实现更好的优化？减少循环迭代次数是否是一种微型优化，还是有一些我不明白的东西？

来源

2014-06-18 FredericS

我把它叫做为什么你应该使用这些，而不是滚动您自己一个最好的例子。这并不是说我知道为什么要这样写，但是CPU很复杂，这可能会引起一个特定的方面，就像分支预测失败可能会使相同复杂度的算法失败一样。 – ghostofstandardspast

它是手动展开循环。据推测，实施者做了一些测试，发现这是有益的，相比之下，有一个单一的“for”语句遍历整个范围。 – Praetorian

谷歌“达芙的装置”。 – Jon

这种技术被称为loop unrolling，以避免每次迭代检查条件的代价与二进制大小（和空间）的折衷。

加速还取决于您的体系结构，但通常一个super-scalar cpu可以利用此优势，通过打破潜在危险的依赖链，可能会在缓存缺失时使您的cpu停滞。

尽管理论上的复杂性是相同的（如果您考虑比较主要操作），算法（在我描述的CPU上）可以执行得更快。就复杂性约束而言，任何STL库都可以实现它自己的版本。

来源

2014-06-18 22:33:39

的确，这个实现方法将'n'循环结束测试替换为两个减法，并且'n/4'是一个整数的正测试。 – FredericS

积极循环展开也是大规模并行体系结构（如CUDA）的一个着名的优化，但其他因素也会发挥作用，如寄存器压力和不同类型的高速缓存 –

随机访问迭代器的GCC find/find_if超载有什么用处？

回答

相关问题