Методы хранения данных в кеше, локальность?

Question

Для сверхбыстрого кода важно, чтобы мы сохраняли локальность ссылок - сохраняйте столько данных, которые тесно используются вместе, в кэше ЦП:

http://en.wikipedia.org/wiki/Locality_of_reference

Какие методы для этого? Могут ли люди привести примеры?

Мне интересны примеры на Java и C / C ++. Интересно узнать, как люди используют много мест для кеширования.

Привет

Answer 1

Это, вероятно, слишком общий характер, чтобы иметь четкий ответ. Подходы в C или C ++ по сравнению с Java будут сильно отличаться (способ, которым язык определяет объекты).

Основным было бы сохранение данных, к которым будет осуществляться доступ, в тесных циклах. Если ваш цикл работает с типом T и имеет члены m1 ... mN, но в критическом пути используются только m1 ... m4, рассмотрите разбиение T на T1, содержащее m1 ... m4, и T2, содержащее m4. ..mN. Возможно, вы захотите добавить к T1 указатель, который ссылается на T2. Старайтесь избегать объектов, которые не выровнены относительно границ кэша (очень зависит от платформы).

Используйте смежные контейнеры (обычный старый массив в C, vector в C ++) и пытайтесь управлять итерациями, чтобы идти вверх или вниз, но не случайным образом перепрыгивая через контейнер. Связанные списки являются убийцами локальности, два последовательных узла в списке могут находиться в совершенно разных случайных местах.

Контейнеры объектов (и обобщения) в Java также являются убийцами, в то время как в векторе ссылки являются смежными, а реальные объекты - нет (существует дополнительный уровень косвенности). В Java есть много дополнительных переменных (если вы new два объекта один за другим, объекты, вероятно, окажутся в почти смежных областях памяти, даже если будет некоторая дополнительная информация (обычно два или три указателя) ) данных управления объектами между ними. GC будет перемещать объекты, но, надеюсь, не станет намного хуже, чем до запуска.

Если вы фокусируетесь на Java, создайте компактные структуры данных, если у вас есть объект, который имеет позицию и к которому нужно обращаться в узком цикле, рассмотрите возможность хранения примитивных типов x и y внутри вашего объект вместо создания Point и удержания ссылки на него. Ссылочные типы должны быть обновлены, а это означает другое распределение, дополнительную косвенность и меньшую локальность.

Answer 2

Два общих метода включают в себя:

• Минимализм (размера данных и / или размера кода / путей)
• Использование методов кеширования

Пример минимализма: В трассировке лучей (парадигма рендеринга трехмерной графики) общепринятым является использование 8-байтовых Kd-деревьев для хранения статических данных сцены.Алгоритм обхода занимает всего несколько строк кода.Затем Kd-дерево часто компилируется таким образом, чтобы минимизировать количество шагов обхода, имея большие пустые узлы в верхней части дерева («Эвристика поверхности» по Хаврану).

Как правило, неправильные прогнозы имеютвероятность 50%, но это незначительные затраты, потому что в строке кэша помещается очень много узлов (учтите, что вы получаете 128 узлов на КиБ!), а один из двух дочерних узлов всегда является прямым соседом в памяти.

Пример для методов кеширования: Индексация массива Мортона , также известная как индексация Z-порядка-кривой.Этот вид индексации может быть предпочтительным, если вы обычно получаете доступ к соседним элементам массива в непредсказуемом направлении.Это может быть полезно для больших изображений или данных вокселей, где у вас может быть 32 или даже 64 байта больших пикселей, а затем миллионы из них (типичная мера для компактной камеры - мегапиксели, верно?) Или даже тысячи миллиардов для научных симуляций.

Тем не менее, оба метода имеют одну общую черту: держите наиболее часто используемые объекты рядом, реже они могут быть дальше, охватывая весь диапазон кэша L1 от основной памяти до жесткого диска, а затем другиекомпьютеры в той же комнате, в соседней комнате, в той же стране, во всем мире, на других планетах.

Answer 3

Некоторые случайные уловки, которые приходят мне в голову, и какие из них я недавно использовал:

Переосмыслите ваш алгоритм.Например, у вас есть изображение с формой и алгоритм обработки, который ищет углы формы.Вместо того, чтобы работать непосредственно с данными изображения, вы можете предварительно обработать его, сохранить все пиксельные координаты фигуры в списке и затем работать со списком.Вы избегаете случайных прыжков вокруг изображения

Сокращенные типы данных.Обычный int будет занимать 4 байта, и если вам удастся использовать, например, uint16_t, вы будете кэшировать в 2 раза больше материала

Иногда вы можете использовать растровые изображения, я использовал их для обработки двоичного изображения.Я хранил пиксели на бит, поэтому я мог уместить 8 * 32 пикселя в одну строку кэша.Это действительно повысило производительность

Форма Java, вы можете использовать JNI (это не сложно) и реализовать свой критический код в C для управления памятью

Answer 4

В мире Java JIT будет усердно работать, чтобы достичь этого, и попытаться догадаться, что это может привести к обратным результатам. Этот вопрос SO более полно решает проблемы, связанные с Java.