GDC2015: Destiny's multithreaded rendering architecture
Почти все про организацию системы тасков в движке под загрузку, подготовку, проверку видимости и рендеринг.
Слайды 60-66 - предлагают использовать системы:

object system

,

rendering

,

visibility

.
Компонент

visibility

отвечает за тест видимости и вычисление детализации, таким образом для rendering компонента будут подгружаться только необходимые данные.
#cpu_opt #ecs #threading

Handles are the better pointers
Большая статья, где приводится альтернатива shared_ptr и weak_ptr.
В 2018 я также перешел на подобную модель.
Вместо указателя используется ID { uint index; uint generation; } индекс указывает на память, а поколение используется для проверки валидности этого ID.
Если добавить счетчик ссылок в данные объекта по индексу, то как раз получится замена shader_ptr:

Object
{
  uint  generation;
  uint  refCounter;
  Data  data;  // все что угодно
}
array<Object, 1024> pool;

if ( id.index < pool.size() )
  if ( pool[id.index].generation == id.generation )
    pool[id.index].data ... // id валиден, можно использовать

Когда refCounter == 0 объект удаляется и увеличивается счетчик поколений:

pool[id.index].data.~Data();
pool[id.index].generation++;

Таким образом все копии ID становятся невалидными.
#cpp #cpu_opt

(video) CppCon 2014: Mike Acton "Data-Oriented Design and C++"
Старая презентация, но все еще актуальная.
Автор периодически стебется над Ogre.
#cpp #cpu_opt #dod

(video) CppCon 2018: Stoyan Nikolov “OOP Is Dead, Long Live Data-oriented Design”
Еще презентация по DOD.
На этот раз критика Chromium.
#cpp #cpu_opt #dod

Запись в блоге про Job System 2.0: -1-, -2-, -3-, -4-, -5-
Используется классический алгоритм work stealing, но написано интересно.
#cpu_opt #threading

(video) Tune CPU job scheduling for Apple silicon games
Рассказывают как устроен мобильный ЦП, как ОС распределяет работу по потокам.
В начале полезно для новичнов и чтобы освежить знания.
21:48 - рассказывают как организовать менеджер тасков с учетом E и P ядер и типа задач.
#cpu_opt #apple_cpu #threading

(video) CPU design effects - Jakub Beránek
Детально рассказывается про предсказание ветвлений, из интересного - в GCC подсказка __builtin_expect игнорируется ЦП.
41.53 - пример, где denorm float работает в 2 раза медленее.
51:56 - false sharing, как происходит синхронизация кэшей
#cpp #cpu_opt #intel_cpu

GDC2022 AMD Ryzen Processor Software Optimization, (video)
19 - некоторые ядра ЦП могут работать быстрее других. Получается у ОС есть больше информации о ЦП, чем доступно из API.
35..41 - Весьма странный тест на производительность, из интересного разве что использование _mm_pause() при зацикливании на спинлоке.
44..46 - Наглядно показаны кэш промахи при чтении полей структуры, классический array of structure vs structure of arrays.
47..48 - Пример использования _mm_prefetch().
49 - Оптимизация memcpy за счет выравнивания памяти, 64 байт - хорошо, 4Кб - еще лучше.
#cpu_opt #amd_cpu

(video) Tune CPU job scheduling for Apple silicon games
Рекомендации, как делать многопоточку на ЦП от Apple.
6:00 - оверхэд от запуска тасков на разных ядрах.
16:20 - как получить количество P и E ядер ЦП.
19:30 - LibDispatch для тех, кто не пишет свою систему тасков.
21:58 - выбор приоритетов для потоков.
#cpu_opt #threading #apple_cpu

(video) CppCon 2016: Timur Doumler “Want fast C++? Know your hardware!"
Рекомендации по оптимизации, ничего нового, но презентация хорошая.
21:52 - немного про префетчер.
23:00 - ассоциативность кэша, объясняет почему происходит резкое падение производительности при чтении с определенным шагом (256, 512 байт). Ссылается на статью Gallery of Processor Cache Effects.
28:18 - выравнивание данных.
34:20 - предсказание ветвлений.
44:10 - 'false sharing', частые синхронизации кэшей между ядрами ЦП.
48:10 - зависимость между данными в цикле.
#cpu_opt

(video) Optimizing Binary Search - Sergey Slotin - CppCon 2022

3:50 - вариант с ветвлением, как в stl. Так было сделано для совместимости со всеми итераторами.
8:30 - детально разбирается почему ветвления это плохо.
12:29 - вариант без ветвлений, работает в 2 раза быстрее на небольших массивах.

Для большинства этого должно хватить, а дальше начинается магия оптимизаций.
#cpp #cpu_opt

C++20’s likely Attribute - Optimizations, Pessimizations, and unlikely Consequences (video)
Нюансы использования аттрибутов likely, unlikely.
Если кратко - все сильно зависит от кода и версии компилятора.
36:04 - likely оказался на 10% быстрее unlikely.
#cpp #cpu_opt

Что следует помнить C++ разработчику об архитектуре процессора
Часто в таких докладах повторяются одни и те же рекомендации, тут также, но кое-что разобрано более детально, это интересно послушать:
14:37 - про конвеер ЦП.
19:46 - параллельное выполнение инструкций, разбор разных архитектур ЦП.
22:48 - про кэш. Десктопные ЦП делают префетч и для доступа по шаблону (фиксированное смещение), мобильные ЦП делают префетч только для линейных даннных.
40:05 - эмулятор ЦП, применяется для микрооптимизаций.
#cpu_opt #rus

std::find() and memchr() Optimizations

Разбирается как оптимизировать memchr с помощью SIMD, но в статье SIMD не дает значительного ускорения.

По моим тестам стандартная реализация find() и memchr по производительности аналогична версии с uint64_t, а более новые ЦП в 4 раза быстрее выполняют AVX2 версию.

Для большей оптимизации можно добавить принудительный инлайнинг, а также аттрибуты likely/unlikely.
for_likely (; i < e; i += 32)
{
__m256i x = _mm256_lddqu_si256(
reinterpret_cast<const __m256i *>( i ));
__m256i r = _mm256_cmpeq_epi8( x, q );
int z = _mm256_movemask_epi8( r );

if_unlikely( z ) {
auto* r2 = i + BitScanForward( z );
return Min( r2, e );
}
}
#cpp #cpu_opt

Instruction-level parallelism (ILP) - параллелизм на уровне команд.

Одна инструкция выполняется за несколько этапов, процессор может параллельно выполнять разные этапы для нескольких инструкций. Но если следующая инструкция зависит от результата предыдущей, то параллельное выполнение невозможно. Иногда компилятор и процессор переставляют инструкции для лучшего распараллеливания, но часто вручную получается добиться лучших результатов.

Вместо последовательного выполнения операций над одной переменной оптимальнее выполнять одну инструкцию для 4х переменных, тогда не будет зависимостей по памяти и выполнится максимально быстро.
ILP актуально для SSE/AVX/NEON, а также на ГП начиная с AMD RDNA архитектуры, на NV появилось раньше.

Подробнее на algorithmica, RDNA Architecture, Better Performance at Lower Occupancy.
#gpu_opt #cpu_opt

Возможно ли ускорить memcpy?

Внутри memcpy проверяется выравнивание памяти, поддержка AVX/SSE и в зависимости от этого выбирается наилучший вариант копирования. Но есть нюанс.

В SSE/AVX есть два варианта копирования: store и stream. Store записывает значение в кэш, а stream - нет, результат сразу пишется в RAM и скорость ограничена пропускной способностью памяти. В memcpy используют оба варианта, но для разных случаев, так store используется для диапазона 512B - 2MB, после 2MB идет stream, а до 512B - не SIMD версия. 2MB выбрано как примерный размер L3 кэша, но реальный размер L3 сильно зависит от модели ЦП.
Получается на диапазоне от 2MB до 8MB (на Ryzen 3900X) можно обогнать memcpy используя _mm256_storeu_si256.

Многопоточный тест.
На 4х потоках store после 2MB сильно замедляется, а memcpy показывает максимальную производительность. Похоже все ЦП на x64 имеют кэш, настоенный под лимит в 2MB. Но нашелся старый AMD Phenom II на котором memcpy после 2MB выдает 4ГБ/с, а _mm_stream_si128 - 6ГБ/с, по какой-то причине в SSE версии memcpy используется только _mm_storeu_si128 и здесь можно ускорить.
#cpp #cpu_opt

Vertical SIMD

Для float3 вектора достаточно функционала SSE (128бит), но давно появился AVX (256бит) с 2х производительностью, а за ним и AVX512 и SVE на ARM. В большинстве открытых движков AVX почти не используются, только в сторонних либах для физики и хэшей. В UE5 AVX используется для транспонирования матриц и для double4 вектора. В O3DE AVX используется только в masked occlusion culling от Intel.

К тому же писать код на SSE/AVX сложно, часто требуется применять shuffle инструкцию, чтобы переставить компоненты для нужного порядка сложения, как это сделано для реализации dot, cross. А последовательное преобразование снижает ILP, задержка инструкций для SSE/AVX составляет 4 цикла для новых ЦП и 5 для более старых.

Намного проще становится при переворачивании SIMD операций, так для AVX получается аналог варпа на 8 потоков, которые одновременно выполняют одну операцию со скаляром. То же самое сделали ГП при переходе на скалярную архитектуру (SIMT).

Было:
A{x,y,z,w} + B{x,y,z,w}
стало:
X{A,..} Y{A,..}
+X{B,..} +Y{B,..}

Плюсы такого подхода: легче переносить скалярные операции на вектора, лучше ILP, экономится 25% памяти для float3 типов, легко переключаться на разную длину вектора и тип команд SSE/NEON.
Недостатки тоже есть: ограничение в 16 регистров, потребуется переход на структуру с массивами (SoA) вместо массива структур (AoS), сложно перемещать отдельные элементы.

В тестах получается ускорение в 3 раза для Dot и в 1.7 раза для Cross.
Похожий способ используется в JoltPhysics: RayAABox4, RayTriangle4.
#cpu_opt

GDC2015: SIMD at Insomniac Games
pdf, video

15. Авто-векторизация и когда она не работает.
25. ISPC - компилятор от Intel для C-подобного языка, сделан специально для автовекторизации.
38. Vec4 тип на SSE это не лучшее решение.
47. Переходим на структуру из массивов (SoA).
60. Иногда AoS лучше. При поиске одного элемента получаем один кэш промах, вместо промахов на каждый массив.
63. Реальный пример. Замена ООП на SoA + SIMD.
104. Как выбрать определенные элементы из вектора. Проблемы с перемещением элементов в лево.
187. Branchless вместо ветвления.
#cpu_opt

Unlocking Modern CPU Power - Next-Gen C++ Optimization Techniques

17:00 - про кэш и префетч, цена случайного доступа к памяти.
24:42 - операции могут выполняться параллельно на уровне инструкций, но все портит ветвление.
32:19 - branchless, когда выполняются обе ветви.
45:45 - дальше про оптимизации на NUMA (много ЦП с локальной и общей памятью).
#cpp #cpu_opt

В видео Unlocking Modern CPU Power (30:19) есть код:
x += condition ? a[i] : b[i];

Как ЦП его выполнит?
Задолго до реального выполнения происходит спекулятивное выполнение - ЦП смотри вперед, если значение condition уже содержится в L1, то выполнение идет дальше и загружает данные в кэш.

Если значение неизвестно, то спекулятивное выполнение не останавливается и включается предсказатель ветвлений, который направлет выполнение по одному из путей.
Если предсказатель ошибся, то спекулятивное выполнение откатывается назад, но запрошенные данные остаются в кэше.

Глубина выполнения зависит от размера reorder buffer, например 192 микроопераций на Haswell архитектуре, а задержка на чтение из L3 около 36 циклов, из ОЗУ - более 200 циклов. Это позволяет почти скрыть потери на все кэш-промахи.

Какая память загружается в кэш?
Оказалось, что пытается загрузить любой адрес, работает аналогично _mm_prefetch. Если виртуальный адрес не существует, то выполнение может пойти по другому пути, предполагая, что несуществующий адрес не будет использован.

Особенности спекулятивного выполнения хорошо разобрали в статьях по Spectre. Так исследования безопасности ЦП дают интересные подробности работы различных систем, тогда как в рекомендациях по оптимизации это не так наглядно.
#cpu_opt