Производительность С++ std::array против std::vector
Добрый вечер.
Я знаю, что массивы в стиле 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. В обоих случаях версия с массивом работает почти в два раза быстрее, чем версия с вектором.
Кто-нибудь знает, почему? Спасибо!
У вас включены какие-то флаги оптимизации? Одна из возможностей заключается в том, что компилятор за кулисами творит какую-то внутреннюю магию.
... кроме того, ваш тест довольно восприимчив к оптимизации компилятора, только одно из назначений внутри цикла будет иметь наблюдаемый эффект. Я бы попытался свести к минимуму такие возможности для оптимизации компилятором при измерении и сравнении времени выполнения.
Массивы и векторы решают разные задачи. Я не вижу смысла сравнивать их выступления таким образом.
@Xirema Я слышал, что динамическая память выделение медленнее по сравнению с «выделением» памяти стека. Но я не слышал, чтобы стековая память работала быстрее, чем динамически выделяемая память. Это кеш-хит?
@Xirema, возможно, ты прав!
@NathanOliver N=100 не имеет ничего общего с эталоном, это просто размер вектора, который содержит комбинации. Я отредактирую вопрос, чтобы было понятно, спасибо. Флаг оптимизации O3 (@Gilad). Я запустил тест на веб-странице быстрых тестов
Причина различия в том, что a1 и a2 являются константами. Компилятор вычисляет их сумму за время компиляции. К сожалению, gcc и clang недостаточно умны, чтобы вывести comb(v1[0], v2[0]) из цикла (даже если их data() помещается в указатель __restrict — это пропущенная оптимизация).
@geza Я не понимаю твоего комментария. Действительно, производительность такая же при удалении констант. Не могли бы вы опубликовать полный ответ? Спасибо!
Вектор должен быть медленнее, чем массив, так как у него есть еще один уровень косвенности, и он должен почти все время проверять размеры, тогда как в массиве все статично.
@phuclv: ISO C++ требует проверки границ нет на std::vector::operator[] только для std::vector::at(). Псевдонимы на основе типов позволяют компилятору поднять уровень косвенности из цикла, загружая указатели только один раз перед циклом. (Поскольку можно предположить, что хранение double не изменяет членов double*glob.)
@MFnx: компилятор мог бы выполнить ту же оптимизацию, если бы понял, что v1 и v2 также являются константами. Или он мог бы провести оптимизацию, если бы понял, что v1 и v2 не пересекаются с glob. Таким образом, он может предварительно вычислить их сумму перед циклом. Но оно этого не осознает. Если я попытаюсь помочь, то получение внутреннего указателя данных вектора в локальную переменную указателя __restrict (в основном __restrict сообщает компилятору, что указатель ни с чем не пересекается) тоже не помогает. Это недостающая оптимизация со стороны компиляторов.
@geza Хорошо, я понимаю! Значит, ответ Xirema не будет точным?
@MFnx: в нем отсутствует ключевая часть, поэтому две версии скомпилированы по-разному, а версия массива имеет суммирование a1 и a2 во время компиляции.
Ответы 2
Я думаю, дело в том, что вы используете слишком маленький размер хранилища (шесть двойников), это позволяет компилятору, в случае с std::array, полностью исключить хранение в ОЗУ путем размещения значений в регистрах. Компилятор может хранить стековые переменные в регистрах, если это более оптимально. Это уменьшает количество обращений к памяти вдвое (остается только запись на glob). В случае std::vector компилятор не может выполнить такую оптимизацию, поскольку используется динамическая память. Попробуйте использовать значительно большие размеры для a1, a2, v1, v2.
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.
Хороший ответ! Clang сделал версию с массивом примерно на 67% быстрее, gcc — на 100%.
Clang с -stdlib=libc++ (вместо обычного libstdc++) может оптимизировать alloc/free для std::vector, если у вас установлен libc++ (libcxx.llvm.org). Я думаю, что это включает случаи, когда окончательный результат не используется, и цикл по массиву/вектору также можно оптимизировать.
Но в любом случае, asm, который вы здесь показываете, выглядит так, как будто версия vec не доказала, что glob и исходные массивы не перекрываются, поэтому на самом деле он перезагружает v1[0] и повторно выполняет добавление на случай, если хранилище на glob[i] изменило его.
И, как прокомментировал вопрос @geza, да, компилятор оптимизирует a1[] и a2[] и загружает суммы из .LC1[rip]. Это ключевой момент. Версия array не использует «более эффективные коды операций», они оба чисто скалярные. (movapd - это то, как вы копируете регистр xmm, независимо от того, интересуетесь ли вы всем этим или только скалярным двойным или плавающим внизу. movsd xmm,xmm выполняет слияние с зависимостью от выходного регистра, поэтому компиляторы никогда не использовали бы это, кроме как перетасовка)
@PeterCordes Это очень интересно! Я подтвердил то, что вы сказали, изменив функцию расчески на m + c*f, где c — переменная, которая изменяется для каждой итерации. Производительность обеих версий теперь равна.
Вы включили оптимизацию? Кроме того, 100 — это очень небольшое количество тестовых случаев. Обычно при бенчмаркинге требуется не менее десятков тысяч итераций. Вы можете использовать быстрая скамья для онлайн-бенчмаркера.