为什么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要比my_max_element多花费x3个时间。那么为什么我能够这么容易地创建一个更快的std函数呢？既然std这么慢，我是不是应该停止使用std并编写自己的函数呢？

注意：一开始我以为这是因为我在for循环中使用了andintegerI而不是迭代器，但现在看来这并不重要。

正在编译信息：

G++-O3-Wall-C-FMessage-Length=0-Std=C++0x

Answer 1

在对此答案进行投票之前，请在您的机器上测试（并验证）并评论/添加结果。注意，我在测试中使用了1000*1000*1000的矢量大小。目前，这个答案有19个支持票，但只有一个公布的结果，这些结果并没有显示出下面描述的效果（尽管是用不同的测试代码获得的，请参见注释）。

似乎有一个优化器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在第二个版本中要快四倍。

不同之处在于*result的预测性共用，即存储当前max元素的值，这样它就不必每次都从内存中重新加载。这提供了一个更清晰的缓存访问模式：

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

下面是用于比较的asm(RDI/RSI分别包含第一个/最后一个迭代器）：

使用while循环(2.88743ms；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

    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:

    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)是一种悲观，因为它们很少执行（Linus说，只有在分支不可预测的情况下，cmov才是一个好主意）。注意，对于随机分布的数据，支路期望被取H_n次，这是一个可以忽略的比例(H_n成对数增长，因此H_n/n迅速接近0）。条件移动代码只适用于病理数据，例如[1,0,3,2,5,4,...]。