- PVSM.RU - https://www.pvsm.ru -
В каком случае инкремент элементов вектора std::vector будет быстрее – если они имеют тип uint8_t или uint32_t?
Чтобы не рассуждать отвлечённо, рассмотрим две конкретные реализации:
void vector8_inc(std::vector<uint8_t>& v)
{
for (size_t i = 0; i < v.size(); i++)
{
v[i]++;
}
}
void vector32_inc(std::vector<uint32_t>& v)
{
for (size_t i = 0; i < v.size(); i++)
{
v[i]++;
}
}
На этот вопрос легко ответить, используя бенчмарк, и чуть позже мы так и сделаем, но для начала попробуем угадать (это называется «рассуждением на основе базовых принципов» – так звучит более наукообразно).
Во-первых, стоит задать вопрос: Каков размер этих векторов?
Что ж, давайте выберем какое-нибудь число. Пусть будет 20 000 элементов в каждом.
Далее, известно, что тестировать мы будем на процессоре Intel Skylake, – посмотрим характеристики команд сложения для 8-битных [1] и 32-битных [2] операндов при непосредственной адресации. Оказывается, основные показатели у них одинаковые: 1 операция на такт и задержка 4 такта на обращение к памяти (1). В данном случае задержка не имеет значения, поскольку каждая операция сложения выполняется независимо, так что расчётная скорость – 1 элемент на такт при условии, что вся остальная работа по выполнению цикла будет проходить в параллельном режиме.
Можно также заметить, что 20 000 элементов соответствуют набору данных размером 20 Кбайт для версии с uint8_t и целых 80 Кбайт для версии с uint32_t. В первом случае они идеально умещаются в кэш уровня L1 современных компьютеров с архитектурой x86, а во втором – нет. Получается, 8-битная версия получит фору благодаря эффективному кэшированию?
Наконец, отметим, что наша задача очень напоминает классический случай автоматической векторизаци [3]и: в цикле с известным числом итераций выполняется арифметическая операция над элементами, последовательно расположенными в памяти. В таком случае 8-битная версия должна иметь колоссальное преимущество по сравнению с 32-битной версией, так как одна векторная операция будет обрабатывать вчетверо больше элементов и в целом процессоры Intel выполняют векторные операции над однобайтовыми элементами с той же скоростью, что и над 32-битными элементами.
Ладно, хватит разглагольствовать. Пора обратиться к тесту.
Я получил следующие тайминги для векторов из 20 000 элементов на компиляторах gcc 8 и clang 8 с разными уровнями оптимизации:
Получается, что, за исключением уровня -O1, вариант с uint32_t быстрее варианта с uint8_t, причём в некоторых случаях значительно: в 5,4 раза на gcc на уровне -O3 и ровно в 8 раз на clang на обоих уровнях, -O2 и -O3. Да-да, инкремент 32-битных целых чисел в std::vector выполняется до восьми раз быстрее, чем инкремент 8-битных целых чисел на популярном компиляторе при стандартных настройках оптимизации.
Как обычно, обратимся к листингу ассемблера в надежде, что он прольёт свет на происходящее.
Вот листинг для gcc 8 на уровне -O2, где 8-битная версия «всего лишь» в 1,5 раза медленнее 32-битной версии (2):
8-bit:
.L3:
inc BYTE PTR [rdx+rax]
mov rdx, QWORD PTR [rdi]
inc rax
mov rcx, QWORD PTR [rdi+8]
sub rcx, rdx
cmp rax, rcx
jb .L3
32-bit:
.L9:
inc DWORD PTR [rax]
add rax, 4
cmp rax, rdx
jne .L9
32-битная версия выглядит именно так, как мы и ожидали от неразвёрнутого (3) цикла: инкремент (4) с указанием адреса, затем три команды управления циклом: add rax, 4 – инкремент индуктивной переменной (5) и пара команд cmp и jne для проверки условия выхода из цикла и условного перехода по нему. Выглядит всё здорово – разворачивание компенсировало бы затраты на инкремент счётчика и проверку условия, и наш код почти достиг бы максимально возможной скорости 1 элемент на такт (6), но для приложения с открытым кодом и так сойдёт. А что же в 8-битной версии? Помимо команды inc с указанием адреса выполняются две дополнительные команды чтения из памяти, а также команда sub, взявшаяся непонятно откуда.
Вот листинг с комментариями:
8-bit:
.L3:
inc BYTE PTR [rdx+rax] ; инкремент по адресу v[i]
mov rdx, QWORD PTR [rdi] ; загрузка v.begin
inc rax ; i++
mov rcx, QWORD PTR [rdi+8] ; загрузка v.end
sub rcx, rdx ; end - start (т.е. vector.size())
cmp rax, rcx ; i < size()
jb .L3 ; след. итерация если i < size()
Здесь vector::begin и vector::end – это внутренние указатели std::vector, которые он использует для указания на начало и конец последовательности элементов, содержащихся внутри выделенной для него области (7), – это, по сути, те же значения, которые используются для реализации vector::begin() и vector::end() (хотя они и имеют другой тип). Выходит, все дополнительные команды – лишь следствие вычисления vector.size(). Вроде ничего необычного? Но ведь в 32-битной версии, разумеется, тоже вычисляется size(), однако в том листинге этих команд не было. Вычисление size() произошло только один раз – за пределами цикла.
Так в чём же дело? Краткий ответ – алиасинг указателей [4]. Развёрнутый ответ я дам ниже.
Вектор v передаётся функции по ссылке, которая, по сути, есть замаскированный указатель. Компилятор должен обратиться к членам v::begin и v::end вектора, чтобы вычислить его размер size(), а в нашем примере size() вычисляется на каждой итерации. Но компилятор не обязан слепо подчиняться исходному коду: он вполне может вынести результат вызова функции size() за пределы цикла, но только если точно знает, что семантика программы от этого не изменится [5]. С этой точки зрения единственным проблемным местом цикла является инкремент v[i]++. Запись происходит по неизвестному адресу. Может ли такая операция изменить значение size()?
Если запись происходит в std::vector<uint32_t> (т.е. по указателю uint32_t *), то нет, она не может изменить значение size(). Запись в объекты типа uint32_t может модифицировать только объекты типа uint32_t, а указатели, задействованные при вычислении size(), имеют другой тип (8).
Однако в случае с uint8_t, по крайней мере на распространённых компиляторах (9), ответ будет таким: да, теоретически значение size() может измениться, так как uint8_t – это псевдоним для unsigned char, а массивы типа unsigned char (и char) могут алиаситься с любым другим типом. Это значит, что, по мнению компилятора, запись по указателям на uint8_t способна модифицировать содержимое памяти неизвестного происхождения по любому адресу (10). Поэтому он предполагает, что каждая операция инкремента v[i]++ может изменить значение size(), и потому вынужден вычислять его заново на каждой итерации цикла.
Мы-то с вами знаем, что запись в память, на которую указывает std::vector, никогда не изменит его собственный size(), ведь это означало бы, что вектор сам каким-то образом был выделен внутри собственной кучи, а это практически невозможно и сродни проблеме курицы и яйца (11). Но компилятору это, к сожалению, неведомо!
Хорошо, мы выяснили, почему версия с uint8_ немного медленнее версии uint32_t на gcc на уровне -O2. Но чем объяснить громадную разницу – до 8 раз – на clang или том же gcc на -O3?
Тут всё просто: в случае с uint32_t clang может выполнить автовекторизацию цикла:
.LBB1_6: ; =>This Inner Loop Header: Depth=1
vmovdqu ymm1, ymmword ptr [rax + 4*rdi]
vmovdqu ymm2, ymmword ptr [rax + 4*rdi + 32]
vmovdqu ymm3, ymmword ptr [rax + 4*rdi + 64]
vmovdqu ymm4, ymmword ptr [rax + 4*rdi + 96]
vpsubd ymm1, ymm1, ymm0
vpsubd ymm2, ymm2, ymm0
vpsubd ymm3, ymm3, ymm0
vpsubd ymm4, ymm4, ymm0
vmovdqu ymmword ptr [rax + 4*rdi], ymm1
vmovdqu ymmword ptr [rax + 4*rdi + 32], ymm2
vmovdqu ymmword ptr [rax + 4*rdi + 64], ymm3
vmovdqu ymmword ptr [rax + 4*rdi + 96], ymm4
vmovdqu ymm1, ymmword ptr [rax + 4*rdi + 128]
vmovdqu ymm2, ymmword ptr [rax + 4*rdi + 160]
vmovdqu ymm3, ymmword ptr [rax + 4*rdi + 192]
vmovdqu ymm4, ymmword ptr [rax + 4*rdi + 224]
vpsubd ymm1, ymm1, ymm0
vpsubd ymm2, ymm2, ymm0
vpsubd ymm3, ymm3, ymm0
vpsubd ymm4, ymm4, ymm0
vmovdqu ymmword ptr [rax + 4*rdi + 128], ymm1
vmovdqu ymmword ptr [rax + 4*rdi + 160], ymm2
vmovdqu ymmword ptr [rax + 4*rdi + 192], ymm3
vmovdqu ymmword ptr [rax + 4*rdi + 224], ymm4
add rdi, 64
add rsi, 2
jne .LBB1_6
Цикл был развёрнут 8 раз, и это в общем-то максимальная производительность, какую только можно получить: один вектор (8 элементов) на такт для кэша L1 (больше не получится из-за ограничения в одну операцию записи на такт (12)).
Для uint8_t векторизация не производится, потому что ей препятствует необходимость вычислять size() для проверки условия цикла на каждой итерации. Причина отставания всё та же, а само отставание гораздо больше.
Самые низкие тайминги объясняются автовекторизацией: gcc применяет её только на уровне -O3, а clang – и на уровне -O2, и на уровне -O3 по умолчанию. Компилятор gcc на уровне -O3 генерирует несколько более медленный код, чем clang, потому что он не разворачивает автовекторизованный цикл.
Мы выяснили, в чём проблема – как же её исправить?
Для начала попробуем один способ, который, правда, не будет работать, – а именно, напишем более идиоматический цикл, основанный на итераторе:
for (auto i = v.begin(); i != v.end(); ++i)
{
(*i)++;
}
Код, который сгенерирует gcc на уровне -O2, будет несколько лучше варианта с size():
.L17:
add BYTE PTR [rax], 1
add rax, 1
cmp QWORD PTR [rdi+8], rax
jne .L17
Две лишние операции чтения превратились в одну, так как i мы теперь сравниваем с указателем end вектора, а не вычисляем заново size(), вычитая из указателя конца указатель начала вектора. По количеству команд этот код догнал код с uint32_t, поскольку дополнительная операция чтения слилась с операцией сравнения. Однако проблема никуда не делась и автовекторизация по-прежнему недоступна, так что uint8_t всё ещё значительно отстаёт от uint32_t – более чем в 5 раз как на gcc, так и на clang на тех уровнях, где предусмотрена автовекторизация.
Попробуем что-нибудь другое. У нас снова ничего не получится, а точнее, мы найдём ещё один неработающий способ.
В этом варианте мы вычисляем size() только один раз до цикла и помещаем результат в локальную переменную:
for (size_t i = 0, s = v.size(); i < s; i++)
{
v[i]++;
}
Вроде бы должно сработать? Проблема была в size(), а теперь мы велели компилятору зафиксировать результат size() в локальной переменной s в начале цикла, а локальные переменные, как известно, не пересекаются с другими данными. Мы фактически сделали то, чего не мог сделать компилятор. И код, который он сгенерирует, действительно будет лучше (по сравнению с первоначальным):
.L9:
mov rdx, QWORD PTR [rdi]
add BYTE PTR [rdx+rax], 1
add rax, 1
cmp rax, rcx
jne .L9
Здесь только одна лишняя операция чтения и нет команды sub. Но что делает эта лишняя команда (rdx, QWORD PTR [rdi]), если она не участвует в вычислении размера? Она считывает указатель data() из v!
Выражение v[i] реализуется как *(v.data() + i), а член, возвращаемый data() (и являющийся, по сути, обычным указателем begin), порождает ту же проблему, что и size(). Правда, я эту операцию не заметил в исходном варианте, потому что там она была «бесплатной», ведь её все равно нужно было выполнить, чтобы вычислить размер.
Потерпите ещё чуть-чуть, мы почти нашли решение. Нужно просто убрать из нашего цикла все зависимости от содержимого std::vector. Проще всего это сделать, если немного модифицировать нашу идиому с итератором:
for (auto i = v.begin(), e = v.end(); i != e; ++i)
{
(*i)++;
}
Теперь всё круто изменилось (здесь мы сравниваем только версии с uint8_t – в одной мы сохраняем итератор end в локальной переменнойперед циклом, в другой – нет):
Это небольшое изменение дало нам 20-кратный прирост скорости на уровнях с автовекторизацией. Причём код с uint8_t не просто догнал код с uint32_t – он обогнал его почти ровно в 4 раза на gcc -O3 и clang -O2 и -O3, как мы и ожидали в самом начале, полагаясь на векторизацию: в конце концов, именно вчетверо больше элементов может быть обработано векторной операцией и вчетверо меньшая пропускная способность нам требуется – независимо от уровня кэша (13).
Если вы дочитали до этого места, то, должно быть, всё это время восклицали про себя:
А как же for-цикл с обходом диапазона [6], появившийся в C++11?
Спешу вас обрадовать: он работает! Это, по сути, синтаксический сахар, за которым скрывается почти в том же виде наша версия с итератором, где мы фиксировали указатель end в локальной переменной до начала цикла. Так что быстродействие у него то же.
Если бы нам вдруг вздумалось вернуться в древние, пещерные времена и написать C-подобную функцию, то такой код тоже замечательно сработал бы:
void array_inc(uint8_t* a, size_t size)
{
for (size_t i = 0; i < size; i++)
{
a[i]++;
}
}
Здесь указатель на массив a и переменная size передаются в функцию по значению, поэтому они не могут быть изменены в результате записи по указателю a (14) – совсем как локальные переменные. Производительность у этого кода такая же, как у предыдущих вариантов.
Наконец, на тех компиляторах, где эта опция доступна, вы можете объявить вектор с __restrict (15):
void vector8_inc_restrict(std::vector<uint8_t>& __restrict v)
{
for (size_t i = 0; i < v.size(); i++)
{
v[i]++;
}
}
Ключевое слово __restrict не входит в стандарт C++, но входит в стандарт C начиная с C99 [7] (как restrict). Если в компиляторе оно реализовано как расширение C++, то, скорее всего, оно будет подчиняться семантике C. Разумеется, в C нет ссылок, поэтому можете мысленно заменить ссылку на вектор указателем на вектор.
Обратите внимание, что restrict не обладает транзитивным свойством: действие спецификатора __restrict, с которым объявлена ссылка на std::vector, распространяется только на члены самого вектора, но не на область кучи, на которую ссылается v.data(). В нашем случае большего не требуется, потому что (как в случае с локальными переменными) достаточно лишь убедить компилятор, что сами по себе члены, указывающие на начало и конец вектора, ни с чем не пересекаются. Оговорка по поводу restrict, однако, всё равно актуальна, так как запись через v.data() может по-прежнему привести к изменению других объектов в вашей функции из-за алиасинга.
Тут мы приходим к последнему – и весьма неутешительному – выводу. Дело в том, что все показанные выше решения применимы только к этому конкретному случаю, когда вектор теоретически может помешать сам себе. Решение заключалось в том, чтобы вынести за пределы цикла или изолировать результат вызова size() или end() вектора, а не в том, чтобы втолковать компилятору, что запись в данные вектора не затрагивает другие данные. Такой код будет сложно масштабировать по мере роста функции.
Проблема алиасинга никуда не делась, и команды записи по-прежнему могут попасть «куда угодно» – просто в этой функции нет других данных, которые могут быть затронуты… пока. Как только в ней появится новый код, всё повторится. Вот пример навскидку [8]. Если в малых циклах у вас происходит запись в массивы из элементов типа uint8_t, придётся воевать с компилятором до конца (16).
Буду рад любым отзывам. У меня пока ещё нет системы комментирования (17), поэтому, как обычно, обсуждение будем вести в этом треде на HackerNews [9].
Перевод статьи публикуется с разрешения автора. Оригинальная публикация: Travis Downs. Incrementing vectors [12].
Автор: Andrey Karpov
Источник [13]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/c-3/336459
Ссылки в тексте:
[1] 8-битных: https://uops.info/html-instr/ADD_M8_I8.html
[2] 32-битных: https://uops.info/html-instr/ADD_M32_I32.html
[3] автоматической векторизаци: https://en.wikipedia.org/wiki/Automatic_vectorization
[4] алиасинг указателей: https://en.wikipedia.org/wiki/Pointer_aliasing
[5] не изменится: https://en.wikipedia.org/wiki/As-if_rule
[6] for-цикл с обходом диапазона: https://en.cppreference.com/w/cpp/language/range-for
[7] C начиная с C99: https://en.cppreference.com/w/c/language/restrict
[8] пример навскидку: https://godbolt.org/z/iQHDY5
[9] этом треде на HackerNews: https://news.ycombinator.com/item?id=20800076
[10] загрузите код в godbolt: https://godbolt.org/z/pZ5FKz
[11] прекрасно работает в clang, но совсем не работает в gcc: https://godbolt.org/z/IhyTTM
[12] Incrementing vectors: https://travisdowns.github.io/blog/2019/08/26/vector-inc.html
[13] Источник: https://habr.com/ru/post/475636/?utm_source=habrahabr&utm_medium=rss&utm_campaign=475636
Нажмите здесь для печати.