时间戳

首页 > 解决方案 > 为什么在源代码中 __find_if 的 __trip_cout 计算为 (__last-__first) >> 2

c++ - 为什么在源代码中 __find_if 的 __trip_cout 计算为 (__last-__first) >> 2

问题描述

我不明白为什么 stl 源代码__find_if" __trip_count = (__last - __first) >> 2;和在下一个 for 循环中调用四次 'if' 段。很难理解

template <typename _RandomAccessIterator, typename _Predicate>
  _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;
    case 2:
      if (__pred(__first))
        return __first;
      ++__first;
    case 1:
      if (__pred(__first))
        return __first;
      ++__first;
    case 0:
    default:
      return __last;
    }
  }

为什么不只是这样

__trip_count = __last - __first;
for(; __trip_count > 0; --__trip_count)
{
    if(__pred(__first))
        return __first;
    ++first;
}

像上面这样，我认为不需要switch段。谁能回答我的疑惑？

标签： c++

解决方案

我无法评论引入它的确切原因，但是，它看起来确实像一种经典的矢量化技术。代码的编写方式似乎是对 4 个连续元素进行谓词会更有效。

我可以推荐Understanding Compiler Optimization - Chandler Carruth - Opening Keynote Meeting C++ 2015作为编译器优化的背景信息，因为它更详细地解释了为什么这样做不是最好的主意。

一些要点（剧透）是：

  • 您的谓词可能是内联的，如果它是一个复杂的 lambda，则向量化可能没有用，并且循环体可能不适合执行缓存，这可能会减慢
  • 您的编译器知道矢量化和循环展开，如果您不手动执行，这将更容易应用

我建议写：

__trip_count = __last - __first;
for(; __trip_count > 0; --__trip_count)
{
    if(__pred(__first))
        return __first;
    ++first;
}

查看代码的git blame，它在 6 到 16 岁之间。最有可能的是，在那个时候，编译器的优化并没有比手工做得更好。它可能仍然存在，它可能不会。

推荐阅读