如果没有if,std :: count_if会更快吗？

Question

这是gcc std::count_if代码

template<typename _InputIterator, typename _Predicate>
  typename iterator_traits<_InputIterator>::difference_type
  count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
 {
  [snip]
  typename iterator_traits<_InputIterator>::difference_type __n = 0;
  for (; __first != __last; ++__first)
    if (__pred(*__first))
      ++__n;
  return __n;
}

我的问题:使用它会更好(即更快)

__n += __pred(*__first); // instead of the if statement

此版本始终执行添加,但不执行分支.

Answer 1

您提供的替换不等同,因为对谓词的限制远远少于您的想法:

• 可以在条件上下文中使用的任何内容(可以在上下文中转换为bool)是谓词的有效返回类型(explicit转换bool为足够).
• 返回类型可以很有趣地添加到迭代器差异类型.

25算法库 [algorithms]

25.1一般 [algorithms.general]

8 Predicate只要算法需要一个函数对象(20.9),当应用于取消引用相应迭代器的结果时,就会返回一个值为testable的值true.换句话说,如果算法Predicate pred作为其参数和first迭代器参数,它应该在pred(*first)上下文转换为bool _(第4条)的构造中正常工作.函数对象pred不应通过解除引用的迭代器应用任何非常量函数.

给予替代消化不良的最可能的回报是标准整数类型,并且值既不是0也不是1.

另外,请记住编译器现在实际上可以真正优化(特别是C++需要,所有模板 - 东西分层深).

Answer 2

所以,首先,您建议的代码是不同的.那么让我们看看两个等价的代码:

template<typename _InputIterator, typename _Predicate>
typename iterator_traits<_InputIterator>::difference_type
count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
    typename iterator_traits<_InputIterator>::difference_type __n = 0;
    for (; __first != __last; ++__first)
        if (__pred(*__first))
            ++__n;
    return __n;
}

和:

template<typename _InputIterator, typename _Predicate>
typename iterator_traits<_InputIterator>::difference_type
count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
    typename iterator_traits<_InputIterator>::difference_type __n = 0;
    for (; __first != __last; ++__first)
        __n += (bool) __pred(*__first);
    return __n;
}

然后,我们可以使用编译器编译它并查看程序集.在我尝试过的一个编译器(os x on clax)下,这些编译器产生了相同的代码.

也许你的编译器也会生成相同的代码,或者它可能产生不同的代码.

Answer 3

从技术上讲,它会,但请记住,所有的价值都高于0评价true.因此被调用的函数可能会返回一个除了之外的值1,这会使结果产生偏差.此外,编译器还具有将分支优化为条件移动的方法.

为了扩展,有一些方法可以在代码中优化分支,但这会降低可读性和可维护性,以及通过例如调试代码的能力.把断点放下来,并且获得很少,因为编译器非常善于自己优化这些东西.