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

我需要找到向量中的最大元素，所以我使用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;
}

Output:

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 并编写自己的函数吗？

注意：起初我以为这是因为我正在使用 and 整数i在 for 循环而不是迭代器中，但这现在似乎并不重要。

编译信息：

g++（海湾合作委员会）4.8.2

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

在对此答案进行投票之前，请在您的计算机上测试（并验证）并评论/添加结果。请注意，我在测试中使用的向量大小为 1000*1000*1000。目前，该答案有 19 条赞成票，但只有 1 条发布结果，并且这些结果没有显示出下面描述的效果（虽然是通过不同的测试代码获得的，请参阅评论）。

似乎存在优化器错误/工件。比较以下时间：

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++ 实现 https://gcc.gnu.org/onlinedocs/gcc-4.9.1/libstdc++/api/a01499_source.html#l05478，第二个应该是一种没有任何行为或要求变化的转变。 Clang++ 为这两个函数生成非常相似的运行时间，而 g++4.8.2 的第二个版本快了四倍。

根据Maxim的建议，将矢量从int to int64_t，改变后的版本不是4，只是比原始版本（g++4.8.2）快1.7倍。

区别在于预测的共同点*result，即存储当前最大元素的值，这样就不必每次都从内存中重新加载。这提供了更清晰的缓存访问模式：

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

这是用于比较的汇编（rdi/rsi分别包含第一个/最后一个迭代器）：

使用 while 循环（2.88743 ms；gist https://gist.github.com/ecatmur/8c0b50dc4e30e1206a98#file-max_element-c):

    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:

The reason this is faster than the for loop is that the conditional moves (cmovl) in the above are a pessimisation as they are executed so rarely (Linus says http://yarchive.net/comp/linux/cmov.html that cmov is only a good idea if the branch is unpredictable). Note that for randomly distributed data the branch is expected to be taken Hn http://en.wikipedia.org/wiki/Harmonic_number times, which is a negligible proportion (H_n grows logarithmically, so H_n/n rapidly approaches 0). The conditional-move code will only be better on pathological data e.g. [1, 0, 3, 2, 5, 4, ...].