Производительность С++: std :: array vs std :: vector
4 MFnx [2019-02-05 23:52:00]
Добрый вечер.
Я знаю, что массивы в стиле C или std :: array не быстрее векторов. Я все время использую векторы (и использую их хорошо). Тем не менее, у меня есть ситуация, в которой использование std :: array работает лучше, чем с std :: vector, и я понятия не имею, почему (протестировано с clang 7.0 и gcc 8.2).
Позвольте мне поделиться простым кодом:
#include <vector>
#include <array>
// some size constant
const size_t N = 100;
// some vectors and arrays
using vec = std::vector<double>;
using arr = std::array<double,3>;
// arrays are constructed faster here due to known size, but it is irrelevant
const vec v1 {1.0,-1.0,1.0};
const vec v2 {1.0,2.0,1.0};
const arr a1 {1.0,-1.0,1.0};
const arr a2 {1.0,2.0,1.0};
// vector to store combinations of vectors or arrays
std::vector<double> glob(N,0.0);
Все идет нормально. Приведенный выше код, который инициализирует переменные, не включен в тест. Теперь давайте напишем функцию для объединения элементов (double) из v1 и v2 или из a1 и a2:
// some combination
auto comb(const double m, const double f)
{
return m + f;
}
И эталонные функции:
void assemble_vec()
{
for (size_t i=0; i<N-2; ++i)
{
glob[i] += comb(v1[0],v2[0]);
glob[i+1] += comb(v1[1],v2[1]);
glob[i+2] += comb(v1[2],v2[2]);
}
}
void assemble_arr()
{
for (size_t i=0; i<N-2; ++i)
{
glob[i] += comb(a1[0],a2[0]);
glob[i+1] += comb(a1[1],a2[1]);
glob[i+2] += comb(a1[2],a2[2]);
}
}
Я пробовал это с Clang 7.0 и GCC 8.2. В обоих случаях версия массива работает почти вдвое быстрее, чем векторная версия.
Кто-нибудь знает почему? Спасибо!
c++ performance benchmarking stdvector stdarray
3 ответа
5 Xirema [2019-02-06 00:24:00]
GCC (и, вероятно, Clang) оптимизируют массивы, но не векторы
Ваше базовое предположение, что массивы обязательно медленнее векторов, неверно. Поскольку векторы требуют, чтобы их данные были сохранены в выделенной памяти (которая с распределителем по умолчанию использует динамическую память), значения, которые необходимо использовать, должны храниться в памяти кучи и иметь постоянный доступ во время выполнения этой программы. И наоборот, значения, используемые массивом, могут быть полностью оптимизированы и просто напрямую указаны в сборке программы.
Ниже то, что GCC выплюнуть как сборку для assemble_vec и assemble_arr функций сразу оптимизации были включены:
[-snip-]
//==============
//Vector Version
//==============
assemble_vec():
mov rax, QWORD PTR glob[rip]
mov rcx, QWORD PTR v2[rip]
mov rdx, QWORD PTR v1[rip]
movsd xmm1, QWORD PTR [rax+8]
movsd xmm0, QWORD PTR [rax]
lea rsi, [rax+784]
.L23:
movsd xmm2, QWORD PTR [rcx]
addsd xmm2, QWORD PTR [rdx]
add rax, 8
addsd xmm0, xmm2
movsd QWORD PTR [rax-8], xmm0
movsd xmm0, QWORD PTR [rcx+8]
addsd xmm0, QWORD PTR [rdx+8]
addsd xmm0, xmm1
movsd QWORD PTR [rax], xmm0
movsd xmm1, QWORD PTR [rcx+16]
addsd xmm1, QWORD PTR [rdx+16]
addsd xmm1, QWORD PTR [rax+8]
movsd QWORD PTR [rax+8], xmm1
cmp rax, rsi
jne .L23
ret
//=============
//Array Version
//=============
assemble_arr():
mov rax, QWORD PTR glob[rip]
movsd xmm2, QWORD PTR .LC1[rip]
movsd xmm3, QWORD PTR .LC2[rip]
movsd xmm1, QWORD PTR [rax+8]
movsd xmm0, QWORD PTR [rax]
lea rdx, [rax+784]
.L26:
addsd xmm1, xmm3
addsd xmm0, xmm2
add rax, 8
movsd QWORD PTR [rax-8], xmm0
movapd xmm0, xmm1
movsd QWORD PTR [rax], xmm1
movsd xmm1, QWORD PTR [rax+8]
addsd xmm1, xmm2
movsd QWORD PTR [rax+8], xmm1
cmp rax, rdx
jne .L26
ret
[-snip-]
Есть несколько различий между этими разделами кода, но критическое различие заключается после .L23 и .L26 соответственно, где для векторной версии числа складываются вместе с помощью менее эффективных кодов операций по сравнению с версией массива, которая использует (больше) инструкции SSE. Векторная версия также включает в себя больше обращений к памяти по сравнению с версией массива. Эти факторы в сочетании друг с другом приведут к тому, что код будет выполняться быстрее для версии кода std::array чем для версии std::vector.
2 Peter Cordes [2019-02-06 12:25:00]
C++ правила наложения имен не позволяют компилятору доказать, что glob[i] += stuff не изменяет один из элементов const vec v1 {1.0,-1.0,1.0}; или v2.
const на std::vector означает, что указатели "управляющего блока" могут быть предположительно не изменены после того, как они сконструированы, но память все еще распределяется динамически, и все, что знает компилятор, - это то, что он эффективно имеет const double * в статическом хранилище.
Ничто в реализации std::vector позволяет компилятору исключать какой-либо другой non-const указатель, указывающий на это хранилище. Например, double *data в блоке управления glob.
C++ не предоставляет реализаторам библиотеки возможность предоставить компилятору информацию о том, что хранилище для разных std::vector не перекрывается. Они не могут использовать __restrict (даже на компиляторах, которые поддерживают это расширение), потому что это может сломать программы, которые принимают адрес векторного элемента. См. Документацию C99 для restrict.
Но с const arr a1 {1.0,-1.0,1.0}; и a2, сами двойники могут помещаться в статическое хранилище только для чтения, и компилятор это знает. Поэтому он может оценивать comb(a1[0],a2[0]); и так далее во время компиляции. В ответе @Xirema вы можете увидеть константы .LC1 asm .LC1 и .LC2. (Только две константы, потому что a1[0]+a2[0] и a1[2]+a2[2] равны 1.0+1.0. Тело цикла использует xmm2 в качестве операнда источника для addsd дважды, а другую константу - один раз.)
Но разве компилятор не может делать суммы однажды вне цикла во время выполнения?
Нет, опять же из-за потенциального алиасинга. Он не знает, что хранилища в glob[i+0..3] не изменят содержимое v1[0..2], поэтому он перезагружается из v1 и v2 каждый раз через цикл после сохранения в glob.
(Однако нет необходимости перезагружать указатели блока управления vector<>, потому что строгие правила псевдонимов на основе типов позволяют предположить, что сохранение double не изменяет double*.)
Компилятор мог проверить, что glob.data() + 0.. N-3 не перекрывается ни с одним из v1/v1.data() + 0.. 2, и сделать другую версию цикла для этого случая, вывод трех результатов comb() из цикла.
Это полезная оптимизация, которую делают некоторые компиляторы при автоматической векторизации, если они не могут доказать отсутствие псевдонимов; в вашем случае это явно пропущенная оптимизация, поскольку gcc не проверяет перекрытие, потому что это заставит функцию работать намного быстрее. Но вопрос в том, может ли компилятор разумно догадаться, что стоило испускать asm, который проверяет во время выполнения на перекрытие и имеет 2 разные версии одного и того же цикла. При оптимизации по профилю он знал бы, что цикл горячий (работает много итераций), и на него стоит потратить дополнительное время. Но без этого компилятор, возможно, не захочет слишком рисковать вздутием кода.
ICC19 (Intel компилятор) фактически делает что - то подобное здесь, но это странно: если вы посмотрите на начало assemble_vec (на компилятор исследователя Godbolt), это загрузить указатель данных от glob, а затем добавляет 8 и снова вычитает указатель, производя константу 8. Затем он разветвляется во время выполнения 8 > 784 (не -8 < 784), а затем -8 < 784 (-8 < 784). Похоже, это должна была быть проверка на перекрытие, но, возможно, он использовал один и тот же указатель дважды вместо v1 и v2? (784 = 8*100 - 16 = sizeof(double)*N - 16)
Как бы то ни было, он заканчивает тем, что ..B2.19 цикл ..B2.19 который поднимает все 3 вычисления comb(), и, что интересно, выполняет 2 итерации сразу с 4 скалярными нагрузками и сохраняет в glob[i+0..4], и 6 addsd (скалярный двойной) добавить инструкции.
В другом месте в теле функции есть векторизованная версия, которая использует 3x addpd (упакованный double), просто сохраняя/перезагружая 128-битные векторы, которые частично перекрываются. Это приведет к остановке пересылки в хранилище, но выполнение по порядку может скрыть это. Просто очень странно, что он выполняет ветвление во время выполнения вычисления, которое будет каждый раз давать один и тот же результат, и никогда не использует этот цикл. Пахнет как ошибка.
Если бы glob[] был статическим массивом, у вас все равно была бы проблема. Потому что компилятор не может знать, что v1/v2.data() не указывает на этот статический массив.
Я думал, что если вы получили к нему доступ через double *__restrict g = &glob[0]; , не было бы проблемы вообще. Это обещает компилятору, что g[i] +=... не повлияет на значения, к которым вы обращаетесь через другие указатели, такие как v1[0].
На практике это не позволяет поднять comb() для gcc, clang или ICC -O3. Но это для MSVC. (Я читал, что MSVC не выполняет строгую оптимизацию псевдонимов на основе типов, но он не перезагружает glob.data() внутри цикла, поэтому он каким-то образом выяснил, что хранение double не изменит указатель. Но MSVC делает определить поведение *(int*)my_float для определения типов, в отличие от других реализаций C++.)
Для тестирования я положил это на Godbolt
//__attribute__((noinline))
void assemble_vec()
{
double *__restrict g = &glob[0]; // Helps MSVC, but not gcc/clang/ICC
// std::vector<double> &g = glob; // actually hurts ICC it seems?
// #define g glob // so use this as the alternative to __restrict
for (size_t i=0; i<N-2; ++i)
{
g[i] += comb(v1[0],v2[0]);
g[i+1] += comb(v1[1],v2[1]);
g[i+2] += comb(v1[2],v2[2]);
}
}
Мы получаем это от MSVC вне цикла
movsd xmm2, QWORD PTR [rcx] # v2[0]
movsd xmm3, QWORD PTR [rcx+8]
movsd xmm4, QWORD PTR [rcx+16]
addsd xmm2, QWORD PTR [rax] # += v1[0]
addsd xmm3, QWORD PTR [rax+8]
addsd xmm4, QWORD PTR [rax+16]
mov eax, 98 ; 00000062H
Тогда мы получим эффектно выглядящий цикл.
Так что это пропущенная оптимизация для gcc/clang/ICC.
0 Dmytro Dadyka [2019-02-06 00:16:00]
Я думаю, дело в том, что вы используете слишком маленький размер хранилища (шесть двойных), это позволяет компилятору в случае std::array полностью исключать хранение в ОЗУ путем помещения значений в регистры. Компилятор может хранить переменные стека в регистрах, если это более оптимально. Это уменьшает доступ к памяти вдвое (остается только запись в glob). В случае std::vector компилятор не может выполнить такую оптимизацию, поскольку используется динамическая память. Попробуйте использовать значительно большие размеры для a1, a2, v1, v2