Почему итерация std :: array выполняется намного быстрее, чем итерация std :: vector?

Примечание редактора:
Последующий вопрос с включенной оптимизацией, которая учитывает только цикл:
Почему итерация через` std :: vector` быстрее, чем итерация через `std :: array`?
где мы можем увидеть эффект сбои страницы ленивого выделения при чтении неинициализированной памяти BSS по сравнению с динамически выделенной + записанной памятью, которая инициализируется вне временного цикла.

Я пробовал профилировать этот код:

#include <vector>
#include <array>
#include <stdio.h>

using namespace std;

constexpr int n = 400'000'000;
//vector<int> v(n);
array<int, n> v;

int main()
{
    int res = 0;
    for(int x : v)
        res += x;
    printf("%d\n", res);
}

На моей машине версия array быстрее, чем vector.

Выделение памяти в этом случае не имеет значения, так как оно выполняется только один раз.

$ g++ arrVsVec.cpp -O3
$ time ./a.out
0

real    0m0,445s
user    0m0,203s
sys 0m0,238s

$ g++ arrVsVec.cpp -O3
$ time ./a.out
0

real    0m0,749s
user    0m0,273s
sys 0m0,476s

Я обнаружил, что разборка для std::vector намного сложнее: https://godbolt.org/z/111L5G


c++ linux performance microbenchmark
person tuket    schedule 20.07.2019    source источник
comment
Какая ОС, версия компилятора? Что вы подразумеваете под режимом выпуска, какие флаги компиляции вы использовали? Самое главное, как вы измеряете время?   -  person rustyx    schedule 20.07.2019
comment
Вы измеряете время, необходимое для выделения вектора, что немаловажно. Выделение std::array бесплатно (занимает нулевое время).   -  person Galik    schedule 20.07.2019
comment
компилировать с g++ -O3 arrVsVec.cpp. Неоптимизированные тесты совершенно бесполезны   -  person M.M    schedule 20.07.2019
comment
Вы хоть вопрос читали? Я упомянул, что выделение памяти не имеет значения. Только один раз. reserve в этом примере не имеет смысла, так как я уже выделяю всю память сразу   -  person tuket    schedule 20.07.2019
comment
Это хороший тест   -  person BiagioF    schedule 20.07.2019
comment
Выполнение стендовых испытаний может быть непростым делом. Лучше рассчитать время для конкретного кода в самой программе, и вам нужно убедиться, что вы используете результаты (или результат некоторого теста, основанного на тестируемом коде), чтобы компилятор не оптимизировал код. Вам также необходимо выполнить компиляцию с включенной оптимизацией. Вот пример stackoverflow.com/questions/33333363/   -  person Galik    schedule 20.07.2019
comment
@tuket Откуда вы знаете, что выделение памяти не имеет значения? Вы измерили, сколько времени это займет?   -  person Galik    schedule 20.07.2019
comment
@Galik Да, я сделал   -  person tuket    schedule 20.07.2019

Ответы (3)


arrow_upward
7
arrow_downward

Ответ по оптимизации на (g++ -O2):

Вы не используете конечный результат, поэтому компилятор может оптимизировать весь цикл.

Именно это происходит в array случае.

main:
        xor     eax, eax
        ret

Но vector выделяет и освобождает динамическую память, что усложняет оптимизацию, и компиляторы стараются перестраховаться и оставляют ее в место:

main:
        xor     eax, eax
        ret
_GLOBAL__sub_I_v:
        sub     rsp, 8
        mov     edi, 400000000
        mov     QWORD PTR v[rip], 0
        mov     QWORD PTR v[rip+8], 0
        mov     QWORD PTR v[rip+16], 0
        call    operator new(unsigned long)
        lea     rdx, [rax+400000000]
        mov     QWORD PTR v[rip], rax
        mov     QWORD PTR v[rip+16], rdx
.L6:
        mov     DWORD PTR [rax], 0
        add     rax, 4
        cmp     rdx, rax
        jne     .L6
        mov     QWORD PTR v[rip+8], rdx
        mov     esi, OFFSET FLAT:v
        mov     edx, OFFSET FLAT:__dso_handle
        mov     edi, OFFSET FLAT:_ZNSt6vectorIiSaIiEED1Ev
        add     rsp, 8
        jmp     __cxa_atexit

Вот почему в данном конкретном случае версия array быстрее. В более реальном приложении разница не будет такой существенной и в основном будет зависеть от времени выделения / освобождения кучи для случая vector.

Ответ на отключение оптимизации (g++):

Не проверяйте результаты, скомпилированные без оптимизации.

Разница, вероятно, связана с тем, что итератор vector не встроен. Таким образом, доступ к векторным элементам при отладке влечет за собой дополнительное косвенное обращение по сравнению с доступом к массиву.

person rustyx    schedule 20.07.2019
comment
Дело в том, что версия с std::array на самом деле является неопределенным поведением. Вы (OP) суммируете кучу неинициализированных значений. В результате этот тест совершенно бесполезен. - person BiagioF; 20.07.2019
comment
@BiagioFesta на самом деле нет. Он имеет статическое хранилище и поэтому инициализирован нулем. - person eerorika; 20.07.2019
comment
Вы правы, при разборке было показано, что функции не встроены. - person tuket; 20.07.2019
comment
@tuket и rustyx: clang ++ с -stdlib=libc++ вместо libstdc++ по умолчанию могут оптимизировать новый / удалить или создать / уничтожить std :: vector. Не уверен, что это будет для вектора в глобальном масштабе. В любом случае это сложная оптимизация, потому что new можно заменить в ISO C ++, поэтому new можно рассматривать как видимый побочный эффект, если язык стандарта не устраняет эту возможность. Но да, +1 за то, что не тестировал режим отладки. Стандартные библиотеки C ++ сильно зависят от агрессивного встраивания оптимизирующих компиляторов. - person Peter Cordes; 20.07.2019

arrow_upward
6
arrow_downward

Как я компилирую:

g++ arrVsVec.cpp

Почему итерация std :: array выполняется намного быстрее, чем итерация std :: vector?

Потому что вы не компилировали с включенной оптимизацией.

Кроме того, вы не используете результат итерации ни для чего, и все вычисления используют входные данные константы времени компиляции, поэтому даже если вы включили оптимизацию, цикл, вероятно, будет оптимизирован, и тогда вы будете измерять только динамическое распределение по сравнению с не динамическим распределением. Подсказка: выполнение динамического распределения бесконечно медленнее, чем бездействие.

Итак, в заключение:

  • Неоптимизированные двоичные файлы работают медленно из-за отсутствия оптимизации; Измеряйте оптимизированные двоичные файлы
  • Если вы намереваетесь измерить скорость итерации, измерьте только итерацию; Не измеряйте выделение памяти.
  • Предпочитайте избегать ввода постоянной времени компиляции.
  • Используйте результат измеренного кода, чтобы его нельзя было оптимизировать.
person eerorika    schedule 20.07.2019

arrow_upward
6
arrow_downward

Вы не используете результат, вы инициализируете вектор нулями и не включаете оптимизацию. Как только вы это сделаете:

int main()
{
    unsigned int res = 0;
    for(int &x : v)
        x = rand();

    for(int i = 0; i < 128; ++i) {
        for(int x : v)
            res += (unsigned int)x;
    }
    std::cout << res;
}

времена идентичны:

Success #stdin #stdout 0.62s 54296KB
-2043861760
Success #stdin #stdout 0.62s 54296KB
-2043861760

РЕДАКТИРОВАТЬ: изменен тип res на unsigned int, чтобы избежать неопределенного поведения.

person Radosław Cybulski    schedule 20.07.2019
comment
Арифметическое переполнение имеет неопределенное поведение. Это возможность с вашими случайными значениями. - person eerorika; 20.07.2019
comment
Вы правы насчет неопределенного поведения, но при изменении на unsigned int результаты остаются прежними. - person Radosław Cybulski; 20.07.2019