性能差异:std :: accumulate vs std :: inner_product vs Loop

Question

今天,当我尝试实现这个简单的操作时,我想分享一些让我头脑发热的东西:

我发现了执行相同操作的不同方法:

1. 通过使用std::inner_product.
2. 实现谓词并使用该std::accumulate函数.
3. 使用C风格的循环.

我想通过使用Quick Bench并启用所有优化来执行一些基准测试.

首先,我将两个C++替代品与浮动值进行了比较.这是使用的代码std::accumulate:

const auto predicate = [](const double previous, const double current) {
    return previous + current * current;
};
const auto result = std::accumulate(input.cbegin(), input.cend(), 0, predicate);

通过使用以下std::inner_product功能与此代码:

const auto result = std::inner_product(input.cbegin(), input.cend(), input.cbegin(), 1);

在启用所有优化的情况下运行基准测试后,我得到了以下结果:

两种算法似乎都达到了相同的性能.我确实想进一步尝试C实现:

double result = 0;
for (auto i = 0; i < input.size(); ++i) {
  result += input[i] * input[i];
}

令人惊讶的是,我发现:

我没想到这个结果.我确定有什么问题所以我确实检查了GCC的实现:

template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
inline _Tp
inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
      _InputIterator2 __first2, _Tp __init)
{
  // concept requirements
  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
  __glibcxx_requires_valid_range(__first1, __last1);

  for (; __first1 != __last1; ++__first1, (void)++__first2)
__init = __init + (*__first1 * *__first2);
  return __init;
}

我发现它与C实现一样.在查看了实现之后,我发现了一些奇怪的东西,(或者至少我没想到会产生那么大的影响):在所有内部累积中,它都是从迭代器value_type到初始值的类型进行转换.

在我的例子中,我将初始值初始化为0或1,值被认为是整数,并且在每次累积中,编译器都在进行转换.在不同的测试用例中,我的输入数组存储截断的浮点数,因此结果没有改变.

将初始值更新为double类型后:

const auto result = std::accumulate(input.cbegin(), input.cend(), 0.0, predicate);

和:

const auto result = std::inner_product(input.cbegin(), input.cend(), input.cbegin(), 0.0);

我得到了预期的结果:

现在,我理解将初始值保留为迭代器的基础类型的独立类型可以使函数更灵活并允许执行更多操作.但,

如果我正在累积数组的元素,我希望得到与结果相同的类型.同样适用于内在产品.

它应该是默认行为吗？

为什么标准决定以这种方式执行它？

Answer 1

如果我正在累积数组的元素，我希望得到相同类型的结果。

您的期望是错误的（尽管不太清楚“与结果相同的类型”是什么意思），正如您可以从std::accumulate文档中清楚地看到的那样：

template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );

template< class InputIt, class T, class BinaryOperation >
T accumulate( InputIt first, InputIt last, T init,
              BinaryOperation op );

返回类型与您用于初始值的类型完全相同。您可以在循环中获得相同的效果：

auto result = 0; // vs auto result = 0.0;
for (auto i = 0; i < input.size(); ++i) {
  result += input[i] * input[i];
}

为什么标准决定以这种方式执行？

因为这样你就可以决定使用什么类型来聚合。Notestd::accumulate可用于左折叠和T不等于std::iterator_traits<InputIt>::value_type不低于（可能甚至更多）匹配时的情况。