358
Локальность данных (Data Locality) —
Паттерны программирования игр
реальными вычислениями для обновления активных
частиц. Если массив большой и содержит
много
неактив-
ных частиц, мы снова засорили кэш.
Помещение объектов в последовательный массив
не решает наших проблем, если сами помещаемые объ-
екты не являются последовательными. Если массив за-
полнен неактивными объектами, которые нам при-
ходится обходить, то все сводится к первоначальной
проблеме.
По названию данного раздела вы скорее всего дога-
даетесь, какое решение я предложу. Не проверять каж-
дый раз флаг активности, а рассортировать данные мас-
сива по значению. Мы поместим все активные частицы
в начало списка. И поскольку мы будем знать, что все
они активны, нам не придется выполнять проверку.
Также мы сможем легко отслеживать количество ак-
тивных частиц. Таким образом наш цикл обновления
превращается в нечто прекрасное:
for (int i = 0; i < numActive_; i++)
{
particles[i].update();
}
Теперь мы не пропускаем
никакие
данные. Каждый
фрагмент данных, попадающий в кэш, является частью
активной частицы, которую нам надо обработать.
Конечно, я не говорю, будто вам надо производить
быструю сортировку частиц каждый кадр. Это уничто-
жит выигранный нами прирост производительности.
Мы хотим просто хранить массив.
Предполагая, что массив уже сохранен — в его изна-
чальном виде, когда все частицы неактивны, — един-
ственный момент, когда он может стать
неотсорти-
рованным
, —
изменение статуса одной из частиц.
Обрабатывается ситуация довольно просто: когда ча-
стица активируется, мы помещаем ее в конец списка ак-
тивных частиц, просто меняя местами с первой
неак-
тивной
:
Грамотные программи-
сты, специализирую-
щиеся на низкоуровне-
вых языках, видят тут
еще одну проблему.
Проверка с помощью
if
для каждой из частиц
может привести к
оши-
бочному прогнозирова-
нию ветви (branch
misprediction)
и
потере
скорости конвейера
(pipeline stall)
. В совре-
менных процессорах
одна «инструкция» за-
нимает несколько так-
тов. Чтобы процессор
всегда был занят, ин-
струкции организуются
в
конвейер
, и следующая
инструкция начинает
выполняться до завер-
шения предыдущей.
Процессору прихо-
дится предполагать, ка-
кая же инструкция будет
следующей. В случае
последовательного кода
без ветвлений и циклов
сделать верное предпо-
ложение не составит
труда, но там, где реали-
зован контроль потоков,
уже сложнее. Пока вы-
полняется инструкция
if
, процессору надо
догадаться, будет ли
частица активна
и нужно ли для нее вы-
зывать метод
update()
.
Для ответа на постав-
ленный вопрос процес-
сор выполняет
прогно-
зирование ветви
— он
смотрит, какие ветви ис-
полнялись ранее, и при-
нимает решение выпол-
нить их же. Но если мы
постоянно скачем с ак-
тивных частиц на неак-
тивные и наоборот,
Do'stlaringiz bilan baham: |