Почему С++ std:: max_element так медленно?

Мне нужно найти элемент 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 занимает х3 больше времени, а затем my_max_element. Итак, почему я могу так легко создать намного более быструю функцию std? Должен ли я перестать использовать std и написать свои собственные функции, поскольку std настолько медленный?

Примечание: сначала это было потому, что я использовал и целое число i в цикле for вместо итератора, но эти швы теперь не имеют значения.

Информация о компиляции:

g++ (GCC) 4.8.2

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

Ответы

Ответ 1

Перед голосованием по этому вопросу, пожалуйста, проверьте (и проверьте) это на своем компьютере и прокомментируйте/добавьте результаты. Обратите внимание, что для моих тестов я использовал векторный размер 1000 * 1000 * 1000. В настоящее время этот ответ содержит 19 upvotes, но только один опубликованный результат, и эти результаты не показали эффект, описанный ниже (хотя полученный с другим тестовым кодом, см. Комментарии).

Кажется, что ошибка/артефакт оптимизатора. Сравните время:

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;
}

Первая - это оригинальная реализация libstdС++, вторая - преобразование без каких-либо изменений в поведении или требованиях. Clang++ производит очень похожие времена выполнения для этих двух функций, тогда как g++ 4.8.2 в четыре раза быстрее со второй версией.

Следуя предложению Максима, изменяя вектор от int до int64_t, измененная версия не 4, а только в 1,7 раза быстрее, чем исходная версия (g++ 4.8.2).

Разница заключается в прогностическом распространении *result, то есть при хранении значения текущего элемента max, так что его не нужно перезагружать из памяти каждый раз. Это дает гораздо более чистый доступ к кэшу:

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

Здесь asm для сравнения (rdi/rsi содержит первый и последний итераторы соответственно):

С циклом while (2.88743 мс; 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 мкс):

    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 мкс): </p> 

    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) в приведенном выше примере являются пессимизацией, поскольку они выполняются так редко (Линус говорит, что cmov - это только хорошая идея, если ветвь непредсказуема). Обратите внимание, что для случайно распределенных данных ожидается, что ветвь будет считаться H n, что является незначительной долей (H n логарифмически растет, поэтому H n/n быстро приближается к 0). Код условного перемещения будет только лучше на патологические данные, например. [1, 0, 3, 2, 5, 4,...].

Ответ 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 не переключает передачи в середине эталона.

Но я думаю, что здесь есть что-то другое, поскольку простое изменение переменной цикла от int до long не меняет результатов...

Ответ 3

Это простая проблема с кешем. Например, при первом загрузке памяти, в этом случае содержимое вектора, оно всегда значительно медленнее, чем если бы оно было недавно доступно. Я скопировал и вставил ваш код с помощью GCC 4.9.

Когда функции меняются на противоположные, соотношение равно 1. Когда они находятся в исходном порядке, отношение равно 1.6.

Это по-прежнему кажется фундаментальной misoptimization GCC в случае max_element для меня. Тем не менее, ваши временные функции настолько низки, что они будут доминировать из-за шума процессора, такого как вышеупомянутые эффекты кеша, вместо какого-либо значимого сравнения.

Обратный, Оригинал