Войти
ПрограммированиеСтатьиОбщее

Будьте вежливы с кэшем (перевод вводной статьи)

Внимание! Этот документ ещё не опубликован.

Автор:

Будьте вежливы с КЭШем

(оригинал)
  25 апреля, 2010 г.

  Небольшой список советов и принципов, который каждый разработчик игр должен держать у себя в голове. Нет никаких аэрокосмических исследований и здравого смысла, но относительно редко всё ещё можно найти куски кода, относящиеся к ним. С сегодняшними компьютерами кэш (cache) может быть вашим и лучшим другом, и злейшим врагом, а процессоры докатились до того, что несколько дополнительных расчётов вредят гораздо меньше нежели один кэш-промах (cache miss). Я не собираюсь детально описывать архитектуру кэша как таковую, статья о другом. Если вам интересна эта тема, посмотрите статью(англ.) Густаво или этот документ(англ.) Ульриха Дреппера. В двух словах: кэш - это очень быстрая память, организованая в линии по 32-128 байт.  Когда запрашивается память, в первую очередь тестируется кэш: если данные в нём - доступ к ним очень быстрый, а если нет - линия загружается целиком. В последнем случае это означает кэш-промах и стОит сотен циклов. Заглядывая вперёд, просматриваю популярный документик Тони Альбрехта "Ловушки ООП"(англ.) - он ускорил расчёт описываюших сфер (bounding sphere) на 35% просто изменив расположение данных (не меняя код в целом).

  Вот 3 основных причины кэш-промахов:
- данные считываются в первый раз (и им не повезло оказаться в одной кэш-линии (cacheline) как предыдущим загруженным переменным).
- данные были выкинуты из кэша
- пробуксовка кэша (сейчас кэш асоциативный, поэтому, размещение памяти указывает на ограниченное число возможных линий кэша)

  Как же их избежать?
- не раздувайте ваши структуры. Думая о наполнении (Cruncher# в помощь!), используйте битовые поля вместо кучи BOOL'ов. Рекомендуется использовать более маленькие типы данных. Конечно, это никогда не должно делаться автоматически, думайте о каждом конкретном случае (см. ниже, например, не нарушайте модели доступа для минимизации наполнения). Как уже говорилось выше, оно должно стоить того, чтобы сбалансировать скорость процессора для доступа к памяти и для сжатия данных.
- подумайте о своей модели доступа. Размещайте члены, которые используются вместе, рядышком друг с другом. Мне очень часто попадается код, в котором первый доступный член находится по смещению в 2 байта, а затем необходимо делать переход на 130. Я видел фрагменты, которые были причиной трёх кэш-промахов при трёх обращениях к одному и тому же объекту! И я мог убрать сотни этих кэш-промахов за кадр всего-лишь переместив переменные.
- разделяйте "гарячие"/"холодные" данные. В сочетании с первым и вторым пунктами, это сделает ваши структуры меньше, а модель доступа более дружелюбной для кэша (cache-friendly).

  Давайте рассмотрим такой пример:

struct Lol
{
    int a, b;
    Cat cat; // 140 bytes
};
  И теперь представьте, что у нас есть цикл итераций, использующий Lol, и выполняющий расчёты над a и b. Каждый переход к следующему объекту гарантировано подарит нам промах! Теперь у нас есть другой цикл, работающий в основном с cat. Та же самая история. А теперь представьте, что у нас в Lol есть только указатель на объект класса Cat. Теперь наша структура составляет всего 12 байт, и первый рассмотренный нами цикл станет куда более дружелюбным для кэша. Cat'ы могут быть выделены из пула или храниться в другой линейной таблице.

  Другая типичная "анти"-модель, которая часто встречается:

for every object
{
    if (object->isActive)
        object->Update();
}
Теперь, если объект не активен, мы по-прежнему нагружаем целую кэш-линию, опрашивая только один байт! Это худшее, что можно сделать. Это как пригласить мистера Кэша к себе в гости, чтобы через секунду выпереть его обратно за порог. В соответствии с этим выступлением(англ.) от Microsoft обычный консольный заголовок характеризуется 30%-40% использованием кэша (мой опыт примерно такой же). Это означает, что он использует только один байт из трёх загруженных. Итак, более хорошее решение:
for every object
{
    if (isObjectActive[i])
        object->Update();
}
Вот это уже немного лучше. Если объект не активен, его даже не будут трогать. Массив флагов активности объектов - это прекрасный непрерывный блок памяти, и мы даже можем использовать биты, чтобы сжать его ещё больше. Это, конечно, не идеальный вариант, но одна из вещей, которую очень уважают процессор с кэшем, - это линейный доступ. В идеале, вы хотите загрузить данные, хранящиеся в линейных блоках, один за другим, та же ситуация и с кодом, мы не хотим прыгать вокруг, а используем тут две таблицы. Повторюсь, нету единого решения на все случаи, но, может быть, было бы лучше иметь список только активных объектов и пробежаться по нему:
for every active object
    object->Update();
Конечно, нам придётся заплатить определённую цену за формирование этого списка, всё зависит от того, насколько часто он меняется, но может быть стоит прислушаться и к этому варианту. Вопросы, над которы ми придётся задуматься: "Как часто эти флаги изменяются?" и "Каково соотношение обработанных и игнорируемых объектов?".

  Вот одна из наиболее патологических ситуаций, которую я видел:

while (itObject != 0)
{
    if (itObject->isDisposed())
        disposedObjects.push_back(itObject);
    itObject = itObject->next;
Вот это вызывалось каждый кадр. И в 99% случаев условие внутри цикла не выполнялось.Это же надо, перебрать сотни объектов (к слову, это был связанный список) лишь для того, чтобы убедиться, что там нечего делать. Моим первым же исправлением было представление флага, указывающего, нужно ли вообще что-то переставлять (работа на 3 минуты = в среднем на тысячу кэш-промахов в кадре меньше).

  Разделение "гарячих"/"холодных" данных окупается в основном в ситуациях, когда нам нужно часто перебирать объекты. Вот реальная ситуация: для каждого НПС у нас есть структура базы данных, содержащая информацию о других агентах. Она чатно необходима для запроса информации о тех или иных агентах, используя их ID. Сначала я использовал сортированый массив. Это хорошая cache-friendly структура, однако, информация об агенте достаточно большая, так что даже пропуск элементов при двоичном поиске приводил к кэш-промахам. Я изменил массив так, что он содержал только пары ID+указатель на данные, хранящиеся фактически в другом месте. И теперь при поиске мы затрагиваем только локальные данные, и когда верный ID найден, возвращается указатель, по которому уже мы получаем нужную информацию.

- Рассматривайте возможность использования компонентной модели. Она улучшает локализацию данных и делает объекты меньше. Мы сможем пакетно обработать компоненты и загрузить только те данные, которые сейчас нужны. При традиционном подходе структура базового объекта может вырасти очень сильно, и снова - мы загружаем 400 байт, чтобы использовать только один, потом 4 и потом может быть 64. При компонентном подходе все эти данные буду храниться рядом друг с другом без каких-либо других элементов поблизости.
  Мы можем пойти дальше и хранить однотипные компоненты в массивах один за другим. Таким образом, когда мы закончим работать с компонентой А1, уже на следующем байте (зависит от выравнивания) будет компонента А2 (одного и того же типа, но принадлежащий другому объекту). Такое размещение идеально подходит для пакетной обработки.

- Думайте о своих структурах данных. Повторюсь: кэш любит линейный доступ. Это означает: будьте осторожны с использованием "деревьев" и связанных списков. Они могут стать более дружелюбными при использовании аллокаторов пула, но, возможно, переход на другую структуру данных тоже стОит рассмотреть. Возможно, Вам придется забыть, чему Вас учили, и не слишком фокусироваться на вычислительной сложности алгоритмов. Если не так много элементов, обычный массив всё ещё может бороться со списками даже при вставке/удалении объектов. Сортированные массивы/хеш-таблицы хорошая альтернатива map/rb-tree.

- Не копируйте. Если вы взглянете на множество игровых "движков", то увидите, что многие из них тратят уйму времени на копирование/перемещение/трансформацию объектов между различными списками. Каждый раз, когда вы копируете данные, вы тратите время. Продолжайте себя спрашивать, действительно ли нужно это вам? Может быть будет достаточно хранить ссылку? Как отметил Брайан в комментариях "это может показаться слишком радикальным". Давайте перефразируем так: "Не копируйте, если некуда". Как и с другими советами, выбирайте меньшее из зол. В идеале у нас было бы всё совершенно, в cache-friendly формате. Но в реальности нам иногда потребуется изменить данные (как в примере с isActive). Для дополнительной информации смотрите комментарии Брайана.

- Профилируйте (profile). Даже если уверены, что полностью владеете ситуацией, - проверяйте себя. В первую очередь сфокусируйтесь на исправлении мест с плохим использованием байт/cacheline. А потом снова профилируйте и убедитесь, что ваши изменения действительно помогли.

- Делайте упреждение (prefetch). Оставьте это на конец, как самый радикальный, хотя, иногда не избежный, метод. Даже когда данные организованы по линейному закону, вы время от времени будете получать кэш-промахи (если новый объект не находится в кэше). Для того, чтобы избежать этого, вы можете попробовать подсказать процессору, что ему понадобится в скором времени. Упреждение, по сути, загружает данные в кэш в фоновом режиме. Вот такой вот трюк, хотя, он ещё нуждается в нескольких сотнях циклов для окончания. Так что не питайте больших иллюзий, если вы делаете так:

prefetch(0, tab[i]);
int a = tab[i].a;
Популярная модель является упреждающим выбором следующего элемента при обработке текущего. В зависимости от размеров объекта/времени обработки (время должно быть меньше затрачиваемого на упреждение) рассматривают предварительную загрузку 2/3/4 следующих элементов наперёд. Упреждение может быть очень полезным, но старайтесь сначала использовать другие методы и прибегать к упреждающему выбору лишь в конце, как к финальному штриху.

  Публикации, с которыми должен быть знаком каждый программист (кроме уже упомянутых):
- Christer Ericson – Memory Optimization (this article is a watered down version of Christer’s paper, basically)
- Bruce Dawson – Multi-Core Memory Coherence – The Hidden Perils of Sharing Data
- Igor Ostrovsky – Gallery of Processor Cache Effects

#cache, #cache miss, #CPU, #C++, #программирование, #кэш, #кэш-промах

11 ноября 2011 (Обновление: 3 дек. 2015)

Комментарии [25]