为什么c ++ std :: max_element这么慢？

Question

我需要找到向量中的max元素,所以我正在使用std::max_element,但我发现它是一个非常慢的函数,所以我编写了自己的版本并设法获得x3更好的性能,这里是代码:

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

#include <sys/time.h>

double getRealTime()
{
    struct timeval tv;
    gettimeofday(&tv, 0);
    return (double) tv.tv_sec + 1.0e-6 * (double) tv.tv_usec;
}

inline int my_max_element(const std::vector<int> &vec, int size)
{
    auto it = vec.begin();
    int max = *it++;
    for (; it != vec.end(); it++)
    {
        if (*it > max)
        {
            max = *it;
        }
    }
    return max;
}

int main()
{
    const int size = 1 << 20;
    std::vector<int> vec;
    for (int i = 0; i < size; i++)
    {
        if (i == 59)
        {
            vec.push_back(1000000012);
        }
        else
        {
            vec.push_back(i);
        }
    }

    double startTime = getRealTime();
    int maxIter = *std::max_element(vec.begin(), vec.end());
    double stopTime = getRealTime();
    double totalIteratorTime = stopTime - startTime;

    startTime = getRealTime();
    int maxArray = my_max_element(vec, size);
    stopTime = getRealTime();
    double totalArrayTime = stopTime - startTime;

    std::cout << "MaxIter = " << maxIter << std::endl;
    std::cout << "MaxArray = " << maxArray << std::endl;
    std::cout << "Total CPU time iterator = " << totalIteratorTime << std::endl;
    std::cout << "Total CPU time array = " << totalArrayTime << std::endl;
    std::cout << "iter/array ratio: = " << totalIteratorTime / totalArrayTime << std::endl;
    return 0;
}

输出:

MaxIter = 1000000012
MaxArray = 1000000012
Total CPU time iterator = 0.000989199
Total CPU time array = 0.000293016
iter/array ratio: = 3.37592

平均std::max_element花费x3的时间my_max_element.那么为什么我能够如此轻松地创建更快的std函数呢？我应该停止使用std并编写自己的函数,因为std太慢了吗？

注意:起初我虽然是因为我i在for循环而不是迭代器中使用和整数,但是接缝现在无关紧要.

编译信息:

g ++(GCC)4.8.2

g ++ -O3 -Wall -c -fmessage-length = 0 -std = c ++ 0x

Answer 1

在对这个答案进行投票之前,请在您的机器上测试(并验证)这个并评论/添加结果.请注意,我的测试使用了1000*1000*1000的矢量大小.目前,这个答案有19个upvotes但只有一个发布的结果,这些结果没有显示下面描述的效果(虽然使用不同的测试代码获得,请参阅注释).

似乎有一个优化器bug /工件.比较时间:

template<typename _ForwardIterator, typename _Compare>
_ForwardIterator
my_max_element_orig(_ForwardIterator __first, _ForwardIterator __last,
_Compare __comp)
{
  if (__first == __last) return __first;
  _ForwardIterator __result = __first;

  while(++__first != __last)
    if (__comp(__result, __first))
      __result = __first;

  return __result;
}

template<typename _ForwardIterator, typename _Compare>
_ForwardIterator
my_max_element_changed(_ForwardIterator __first, _ForwardIterator __last,
_Compare __comp)
{
  if (__first == __last) return __first;
  _ForwardIterator __result = __first;
  ++__first;

  for(; __first != __last; ++__first)
    if (__comp(__result, __first))
      __result = __first;

  return __result;
}

第一个是原始的libstdc ++实现,第二个应该是一个没有任何行为或要求变化的转换.Clang ++为这两个函数生成非常相似的运行时间,而g ++ 4.8.2比第二个版本快四倍.

根据Maxim的建议,将矢量更改int为int64_t,更改后的版本不是4,但只比原始版本快了1.7倍(g ++ 4.8.2).

不同之处在于预测共性*result,即存储当前max元素的值,以便每次都不必从内存重新加载.这提供了更清晰的缓存访问模式:

w/o commoning     with commoning
*                 *
**                 *
 **                 *
  **                 *
  * *                 *
  *  *                 *
  *   *                 *

这是用于比较的asm(rdi/分别rsi包含第一个/最后一个迭代器):

使用while循环(2.88743 ms; gist):

    movq    %rdi, %rax
    jmp .L49
.L51:
    movl    (%rdi), %edx
    cmpl    %edx, (%rax)
    cmovl   %rdi, %rax
.L49:
    addq    $4, %rdi
    cmpq    %rsi, %rdi
    jne .L51

使用for循环(1235.55μs):

    leaq    4(%rdi), %rdx
    movq    %rdi, %rax
    cmpq    %rsi, %rdx
    je  .L53
    movl    (%rdi), %ecx
.L54:
    movl    (%rdx), %r8d
    cmpl    %r8d, %ecx
    cmovl   %rdx, %rax
    cmovl   %r8d, %ecx
    addq    $4, %rdx
    cmpq    %rdx, %rsi
    jne .L54
.L53:

如果我通过在开始时显式存储*result到变量prev并且每当result更新时强制进行通用,并且使用prev而不是*result在比较中,我得到更快的循环(377.601μs):

    movl    (%rdi), %ecx
    movq    %rdi, %rax
.L57:
    addq    $4, %rdi
    cmpq    %rsi, %rdi
    je  .L60
.L59:
    movl    (%rdi), %edx
    cmpl    %edx, %ecx
    jge .L57
    movq    %rdi, %rax
    addq    $4, %rdi
    movl    %edx, %ecx
    cmpq    %rsi, %rdi
    jne .L59
.L60:

这比for循环更快的原因是cmovl上面的条件move ()是一个悲观,因为它们很少执行(Linus说如果分支是不可预测的,cmov只是一个好主意).注意,对于随机分布的数据,预期分支将花费H _n次,这是可忽略的比例(H _n以对数方式增长,因此H _n/n快速接近0).条件移动代码仅在病理数据上更好,例如[1,0,3,2,5,4,...].

Answer 2

您可能正在以64位模式运行测试sizeof(int) == 4,但是sizeof(std::vector<>::iterator) == 8,这样,循环中的赋值int(my_max_element更确切地说)比std::vector<>::iterator(这是什么std::max_element)更快.

如果您更改std::vector<int>为std::vector<long>结果更改有利于std::max_element:

MaxIter = 1000000012
MaxArray = 1000000012
Total CPU time iterator = 0.00429082
Total CPU time array = 0.00572205
iter/array ratio: = 0.749875

一个重要的注意事项:当基准测试禁用CPU频率缩放时,CPU不会在基准测试中间切换齿轮.

但我认为别的东西在这里打球,因为距离改变循环变量int,以long不改变结果...