Что я могу сделать в Java-коде для оптимизации кэширования процессора?

При написании Java-программы я могу повлиять на то, как процессор будет использовать свой кеш для хранения моих данных? Например, если у меня есть массив, к которому обращается много, помогает ли он, если он достаточно мал, чтобы вписаться в одну строку кэша (обычно 128 байт на 64-битной машине)? Что делать, если я сохраняю много используемого объекта в пределах этого предела, могу ли я ожидать, что память, используемая им, будет близка и останется в кеше?

Фон: я создаю сжатое цифровое дерево, которое сильно вдохновлено массивы Judy, которые находятся на C. В то время как в основном я использую методы сжатия node, у Джуди есть оптимизация кэша ЦП в качестве центральной цели дизайна и типов node, а также эвристика для переключение между ними в значительной степени зависит от этого. Мне было интересно, есть ли у меня шанс получить эти преимущества?

Изменить. Общий совет ответов до сих пор заключается в том, чтобы не пытаться микрооптимизировать детали машинного уровня, когда вы так далеко от машины, как на Java. Я полностью согласен, поэтому я чувствовал, что должен добавить некоторые (надеюсь) разъясняющие комментарии, чтобы лучше объяснить, почему я думаю, что этот вопрос по-прежнему имеет смысл. Они приведены ниже:

Есть несколько вещей, которые обычно проще обрабатывать компьютеры из-за того, как они создаются. Я видел, что Java-код работает значительно быстрее при сжатии данных (из памяти), хотя декомпрессии пришлось использовать дополнительные циклы ЦП. Если данные были сохранены на диске, очевидно, почему это так, но, конечно, в ОЗУ этот же принцип.

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

В Java я не могу (и не хочу) много знать о том, как память будет управляться определенной средой выполнения. Поэтому я должен принимать оптимизацию и на более высокий уровень абстракции. Мой вопрос в основном, как мне это сделать? Что касается локальности ссылки, то что означает "близко друг к другу" на уровне абстракции, над которой я работаю на Java? Тот же объект? Тот же тип? Тот же массив?

В общем, я не думаю, что слои абстракции меняют "законы физики", метафорически. Удвоение вашего массива в размере каждый раз, когда вы заканчиваете пространство, является хорошей стратегией на Java, даже если вы больше не называете malloc().

Ответ 1

Ключом к хорошей производительности с Java является запись идиоматического кода, а не попытка перехитрить JIT-компилятор. Если вы напишете свой код, чтобы попытаться повлиять на него, чтобы сделать что-то определенным образом на уровне собственной инструкции, вы с большей вероятностью будете стрелять в ногу.

Это не означает, что общие принципы, такие как местность ссылок, не имеют значения. Они это делают, но я бы рассматривал использование массивов и т.д., Чтобы быть уверенным в производительности, идиоматическим кодом, но не "сложным".

HotSpot и другие оптимизирующие время работы чрезвычайно умны в том, как они оптимизируют код для конкретных процессоров. (Например, проверить это обсуждение.) Если бы я был экспертом по программированию на машинах, я бы написал машинный язык, а не Java. И если это не так, было бы неразумно думать, что я мог бы лучше оптимизировать свой код, чем эксперты.

Кроме того, даже если вы знаете, как лучше реализовать что-то для конкретного процессора, красота Java - это однократная запись. Умные трюки для "оптимизации" Java-кода, как правило, делают возможности оптимизации для JIT более жесткими. Прямой код, который придерживается общих идиом, легче распознать оптимизатор. Таким образом, даже если вы получите лучший Java-код для вашего тестового стенда, этот код может сильно пострадать от другой архитектуры или, в лучшем случае, не воспользоваться преимуществами улучшений в будущих JIT.

Если вам нужна хорошая производительность, сохраните ее просто. Команды действительно умных людей работают, чтобы сделать это быстро.

Ответ 2

Если данные, которые вы хрустите, в основном или полностью состоят из примитивов (например, в числовых проблемах), я бы посоветовал следующее.

Выделите плоскую структуру массивов-примитивов фиксированного размера во время инициализации и убедитесь, что данные в нем периодически уплотняются/дефрагментируются (0- > n, где n - наименьший максимальный индекс, если вы можете подсчитать количество элементов) для повторного использования с использованием цикла for. Это единственный способ гарантировать непрерывное выделение в Java, а уплотнение дополнительно улучшает локальность ссылок. Уплотнение выгодно, так как это уменьшает необходимость итерации по неиспользуемым элементам, уменьшая количество условных чисел: по мере того как цикл for итерации заканчивается, завершение происходит раньше, и меньше итерации = меньше движения через кучу = меньше шансов на прохождение кеша. В то время как уплотнение создает собственные накладные расходы само по себе, это может быть сделано только периодически (по отношению к вашим основным областям обработки), если вы этого захотите.

Еще лучше, вы можете чередовать значения в этих заранее выделенных массивах. Например, если вы представляете пространственные преобразования для многих тысяч объектов в 2D-пространстве и обрабатываете уравнения движения для каждого из них, у вас может быть узкая петля вроде

int axIdx, ayIdx, vxIdx, vyIdx, xIdx, yIdx;

//Acceleration, velocity, and displacement for each
//of x and y totals 6 elements per entity.
for (axIdx = 0; axIdx < array.length; axIdx += 6) 
{
    ayIdx = axIdx+1;
    vxIdx = axIdx+2;
    vyIdx = axIdx+3;
    xIdx = axIdx+4;
    yIdx = axIdx+5;

    //velocity1 = velocity0 + acceleration 
    array[vxIdx] += array[axIdx];
    array[vyIdx] += array[ayIdx];

    //displacement1 = displacement0 + velocity
    array[xIdx] += array[vxIdx];
    array[yIdx] += array[vxIdx];
}

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

Ответ 3

Если вы не понимаете, какое улучшение имеет несколько процентов, используйте C, где вы получите улучшение на 50-100%!

Если вы считаете, что простота использования Java делает его лучшим языком для использования, то не сомневайтесь в сомнительной оптимизации.

Хорошей новостью является то, что Java будет делать много вещей под обложками, чтобы улучшить ваш код во время выполнения, но почти наверняка не будет делать тех оптимизаций, о которых вы говорите.

Если вы решите пойти с Java, просто напишите свой код так четко, как можете, не учитывайте незначительные оптимизации. (Основные из них, например, использование правильных коллекций для правильного задания, а не выделение/освобождение объектов внутри цикла и т.д., Все равно стоит)

Ответ 4

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

Я не знаю каких-либо конструкций на Java, которые позволяют вам контролировать вещи на этом уровне детализации. Теоретически вы можете косвенно влиять на него тем, как вы организуете свою программу и данные, но вы так далеко, что я не вижу, как вы могли бы сделать это надежно или даже знать, происходит ли это или нет.

Ответ 5

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

Что касается макета памяти для объектов, Sun Jvm (теперь Oracle) кладет объекты в память по типу (т.е. сначала удваивает и долго, затем ints и плавает, затем шорты и символы после этих байтов и boolean и, наконец, ссылки на объекты). Вы можете получить подробнее здесь.

Локальные переменные обычно хранятся в стеке (это ссылки и примитивные типы).

Как упоминает Ник, лучший способ обеспечить макет памяти в Java - это использовать примитивные массивы. Таким образом, вы можете следить за тем, чтобы данные были непрерывными в памяти. Будьте осторожны с размерами массивов, хотя у GC есть проблемы с большими массивами. Это также имеет недостаток, что вы должны сами управлять памятью.

В верхней части вы можете использовать шаблон Flyweight, чтобы получить объектно-ориентированную юзабилити, сохраняя при этом высокую производительность.

Если вам нужна дополнительная производительность в производительности, генерация собственного байт-кода "на лету" помогает с некоторыми проблемами, если сгенерированный код выполняется достаточно раз, а ваш собственный кеш-код встроенного кода не заполняется (что отключает JIT для всех практических целей).