gcc 为什么c++ std：：max_element这么慢？

2ic8powd 于 2022-11-13 发布在其他

关注(0)|答案(4)|浏览(392)

我需要找到向量中的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多花3倍的时间。那么为什么我可以如此轻松地创建一个更快的std函数呢？既然std太慢了，我应该停止使用std并编写自己的函数吗？
注：起初我以为这是因为我在for循环中使用了整数i，而不是迭代器，但现在看来这并不重要。

正在编译信息：

g++（通用条款）4.8.2
g++ -O3 -墙-c -f消息长度=0 -标准=c++0x

gcc

来源：https://stackoverflow.com/questions/25622109/why-is-c-stdmax-element-so-slow

4条答案

按热度按时间

vatpfxk51#

我针对我的特定用例对max_element进行了测试，并使用intrinsics进行了几个实现，这些实现可以在下面找到：https://github.com/XapaJIaMnu/maxelem_test
我的实现比普通的std::max_element至少提高了2倍，前提是数据不按升序排序（或几乎不按升序排序）。
这些是对随机大小的数组（最多2000个元素）的测试结果，这些数组包含从'[5：5]的均匀分布生成的浮点数，运行100000次。
| | 合同通用条款第11.2条|铿锵声14|国际商会2022.1.0|
| - -|- -|- -|- -|
| 标准：：最大元素| 2.6696s | 0.4221s | 0.4662s |
| 连续的| 1.0831s | 1.1924s | 1.1472s |
| AVX 512最大值+最大值_减少| 0.2412s | 0.2152s | 0.2142s |
| 仅AVX 512最大值_减少| 0.2570s | 0.2629s | 0.2325s |
| AVX 512 cmp_ps_掩码| 0.1884s | 0.1826s | 0.1833s |
| AVX 512 ^ +载体化突出端| 0.2097s | 0.2089s | 0.2072s |
| AVX cmp_ps +移动掩码| 0.2181s | 0.1697s | 0.1702s |
| SSE压缩_psp +移动掩码| 0.2692s | 0.2051s | 0.2221s |
我现在懒得去研究汇编，以获得更多可解释的结果。

赞(0）回复(0）举报 2022-11-13

whhtz7ly2#

在对这个答案投票之前，请在您的机器上测试（并验证）这个答案，并对结果进行注解/添加。注意，我在测试中使用了100010001000的矢量大小。目前，这个答案有19个赞成票，但只有一个张贴的结果，这些结果没有显示出下面描述的效果（尽管使用不同的测试代码获得，请参见注解）。
似乎存在优化程序错误/工件。比较以下时间：

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为这两个函数产生了非常相似的运行时间，而g4.8.2在第二个版本中快了四倍。
根据Maxim的建议，将向量从int改为int64_t，改变后的版本不是4，而是仅比原始版本（g4.8.2）快1.7倍。
不同之处在于*result的预测共享，即存储当前max元素的值，这样就不必每次都从内存中重新加载它，这给出了一个更干净的缓存访问模式：

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

下面是用于比较的asm（rdi/rsi分别包含第一个/最后一个迭代器）：
用while循环（2.88743ms;要点）：

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时，通过显式地将*result存储到变量prev中来强制共用，并在比较中使用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）是一个悲观的说法，因为它们很少被执行（Linus says，即cmov仅在分支不可预测时是个好主意）。注意，对于随机分布的数据，分支被期望执行Hn次，这是可忽略的比例（Hn以对数方式增长，因此Hn/n迅速接近0）。条件移动代码将仅在病理数据（例如，[1，0，3，2，5，4，...]）上更好。

赞(0）回复(0）举报 2022-11-13

t8e9dugd3#

您可能正在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并不会改变结果...

赞(0）回复(0）举报 2022-11-13

q5lcpyga4#

这是一个简单的缓存问题。也就是说，第一次加载内存时，在本例中是加载向量的内容，它总是比最近访问它要慢得多。我用GCC 4.9复制并粘贴了您的代码。
当功能颠倒时，比率为1。当它们处于原始顺序时，比率为1.6。
在我看来，这仍然像是GCC在max_element的情况下的根本性优化错误。然而，您的函数时间如此之短，它们将被CPU噪声（如上面的缓存效应）所支配，而不是任何有意义的比较。
Reversed，Original

赞(0）回复(0）举报 2022-11-13

我来回答

gcc 为什么c++ std：：max_element这么慢？

4条答案

相关问题

热门标签

最新问答