A-tit indd

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

---