Выбор ответа Senior Производительность и кеш обновлено
AoS и SoA
Вопрос
Есть std::vector<Particle> (позиция, скорость, цвет, имя), а горячий цикл обновляет только позиции. Какое изменение данных обычно ускорит цикл?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Разделить на отдельные массивы полей (structure of arrays). В массиве структур каждая кеш-линия наполовину занята ненужными полями, а SoA (vector<float x, y, z) кладёт нужные данные плотно, и цикл хорошо векторизуется.
Варианты ответа
- Разделить на отдельные массивы полей (structure of arrays)правильный ответ
- Сделать
Particleполиморфным классом с виртуальнымupdate() - Хранить частицы в
std::mapпо id, чтобы обходить их по порядку - Хранить
vector<unique_ptr<Particle>>, чтобы не копировать частицы
Разбор
В массиве структур каждая кеш-линия наполовину занята ненужными полями, а SoA (vector<float> x, y, z) кладёт нужные данные плотно, и цикл хорошо векторизуется. Это основа data-oriented design.
- Виртуальность добавит указатель на vtable и косвенные вызовы.
- map разбросает частицы по куче.
- Указатели на отдельные объекты добавят промах кеша на каждый элемент.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.