Следующая Java-программа выполняется в среднем от 0,50 до 0,55 с:
public static void main(String[] args) {
long startTime = System.nanoTime();
int n = 0;
for (int i = 0; i < 1000000000; i++) {
n += 2 * (i * i);
}
System.out.println((double) (System.nanoTime() - startTime) / 1000000000 + " s");
System.out.println("n = " + n);
}
Если я заменяю 2 * (i * i)
на 2 * i * i
, это занимает от 0,60 до 0,65 секунды для запуска. Как так?
Я запускал каждую версию программы 15 раз, чередуя их. Вот результаты:
2*(i*i) | 2*i*i
----------+----------
0.5183738 | 0.6246434
0.5298337 | 0.6049722
0.5308647 | 0.6603363
0.5133458 | 0.6243328
0.5003011 | 0.6541802
0.5366181 | 0.6312638
0.515149 | 0.6241105
0.5237389 | 0.627815
0.5249942 | 0.6114252
0.5641624 | 0.6781033
0.538412 | 0.6393969
0.5466744 | 0.6608845
0.531159 | 0.6201077
0.5048032 | 0.6511559
0.5232789 | 0.6544526
Самый быстрый пробег 2 * i * i
занял больше времени, чем самый медленный 2 * (i * i)
. Если бы они имели одинаковую эффективность, вероятность этого бы была меньше 1/2^15 * 100% = 0.00305%
.
java
performance
benchmarking
bytecode
jit
Стефан
источник
источник
2 * i * i
медленнее. Я тоже попробую бегать с Граалем.i * i * 2
быстрее, чем2 * i * i
? », Чтобы лучше понять, что проблема в порядке операций.Ответы:
Существует небольшая разница в порядке следования байт-кода.
2 * (i * i)
:против
2 * i * i
:На первый взгляд это не должно иметь значения; во всяком случае, вторая версия является более оптимальной, поскольку она использует на один слот меньше.
Поэтому нам нужно копать глубже в нижний уровень (JIT) 1 .
Помните, что JIT очень агрессивно разворачивает маленькие петли. Действительно, мы наблюдаем 16-кратное развертывание для
2 * (i * i)
случая:Мы видим, что есть 1 регистр, который «проливается» на стек.
И для
2 * i * i
версии:Здесь мы наблюдаем гораздо больше «разливов» и больше обращений к стеку
[RSP + ...]
из-за более промежуточных результатов, которые необходимо сохранить.Таким образом, ответ на вопрос прост:
2 * (i * i)
быстрее, чем2 * i * i
потому, что JIT генерирует более оптимальный код сборки для первого случая.Но, конечно, очевидно, что ни первая, ни вторая версии не годятся; цикл может действительно выиграть от векторизации, поскольку любой процессор x86-64 имеет по крайней мере поддержку SSE2.
Так что это проблема оптимизатора; как это часто бывает, он слишком агрессивно разворачивается и стреляет себе в ногу, при этом упуская различные другие возможности.
Фактически, современные процессоры x86-64 разбивают инструкции дальше на микрооперации (µop) и с такими функциями, как переименование регистров, µop кеши и буферы циклов, оптимизация цикла требует гораздо больше изящества, чем простое развертывание для оптимальной производительности. Согласно руководству по оптимизации Agner Fog :
Что касается времени загрузки - даже самое быстрое попадание L1D стоит 4 цикла , дополнительный регистр и µop, так что да, даже несколько обращений к памяти повредят производительность в тесных циклах.
Но вернемся к возможности векторизации - чтобы увидеть, насколько быстро это может быть, мы можем скомпилировать аналогичное приложение C с GCC , которое прямо его векторизует (показан AVX2, SSE2 похож) 2 :
Время выполнения:
1 Чтобы получить сгенерированный JIT вывод сборки, получите отладочную JVM и запустите
-XX:+PrintOptoAssembly
2 Версия C компилируется с
-fwrapv
флагом, который позволяет GCC обрабатывать целочисленное переполнение со знаком как обертку из двух дополнений.источник
ret
инструкцию, или выдает метку, а не команду ret, поэтому выполнение просто проваливается. На самом деле GCC ведет себя так, как иногда, когда он сталкивается с UB. Например: почему рет исчезают с оптимизацией? , Вы определенно хотите скомпилировать правильно сформированный код, чтобы убедиться, что ассм является нормальным.mov
/add-immediate
. например,movl RBX, R9
/addl RBX, #8
должно бытьleal ebx, [r9 + 8]
, 1 моп для копирования и добавления. Илиleal ebx, [r9 + r9 + 16]
делатьebx = 2*(r9+8)
. Так что да, разворачиваться до такой степени глупо, как и наивный мозговой кодеин, который не использует в своих интересах целочисленные тождества и ассоциативную целочисленную математику.Когда это умножение
2 * (i * i)
, JVM может вычленить умножение2
из цикла, что приводит к следующему эквивалентному, но более эффективному коду:но когда умножение есть
(2 * i) * i
, JVM не оптимизирует его, так как умножение на константу больше не прямо перед сложением.Вот несколько причин, почему я думаю, что это так:
if (n == 0) n = 1
оператора в начале цикла приводит к тому, что обе версии оказываются настолько эффективными, поскольку разложение умножения больше не гарантирует, что результат будет одинаковым2 * (i * i)
версияВот тестовый код, который я использовал, чтобы сделать эти выводы:
И вот результаты:
источник
n *= 2000000000;
2*1*1 + 2*2*2 + 2*3*3
. Очевидно, что вычисление1*1 + 2*2 + 3*3
и умножение на 2 является правильным, тогда как умножение на 8 не будет.2(1²) + 2(2²) + 2(3²) = 2(1² + 2² + 3²)
. Это было очень просто, и я просто забыл это, потому что цикл увеличивается.2 * (i * i)
но не от(2 * i) * i
? Я думаю, что они эквивалентны (это может быть моим плохим предположением). Если это так, разве JVM не сможет канонизировать выражение перед оптимизацией?Байт-коды: https://cs.nyu.edu/courses/fall00/V22.0201-001/jvm2.html Байт-коды Просмотрщик: https://github.com/Konloch/bytecode-viewer
На моем JDK (Windows 10 64 бит, 1.8.0_65-b17) я могу воспроизвести и объяснить:
Вывод:
Так почему же? Байт-код таков:
Разница в следующем: с скобками (
2 * (i * i)
):Без скобок (
2 * i * i
):Загрузка всего в стек и последующая работа обратно быстрее, чем переключение между помещением в стек и работой с ним.
источник
Касперд спросил в комментарии принятого ответа:
У меня недостаточно репутации, чтобы ответить на это в комментариях, но это тот же ISA. Стоит отметить, что в версии GCC используется 32-разрядная целочисленная логика, а в скомпилированной версии JVM внутренне используется 64-разрядная целочисленная логика.
R8-R15 являются только новыми x86_64 регистров . EAX-EDX - это нижние части регистров общего назначения RAX-RDX. Важной частью в ответе является то, что версия GCC не развернута. Он просто выполняет один цикл цикла для каждого фактического цикла машинного кода. Хотя версия JVM имеет 16 циклов цикла в одном физическом цикле (основываясь на ответе rustyx, я не интерпретировал сборку). Это одна из причин, почему используется больше регистров, поскольку тело цикла на самом деле в 16 раз длиннее.
источник
*2
из цикла. Хотя в этом случае это даже не победа, потому что это делается бесплатно с LEA. На процессорах Intellea eax, [rax+rcx*2]
имеет такую же задержку 1с, как иadd eax,ecx
. Однако на процессорах AMD любой масштабированный индекс увеличивает задержку LEA до 2 циклов. Таким образом, цепочка зависимостей, переносимая циклами, удлиняется до 2 циклов, становясь узким местом для Райзена. (imul ecx,edx
пропускная способность равна 1 за такт на Ryzen и на Intel).Хотя это не было напрямую связано со средой вопроса, просто для любопытства, я провел тот же тест на .NET Core 2.1, x64, режим релиза.
Вот интересный результат, подтверждающий подобные фономены (наоборот), происходящие над темной стороной силы. Код:
Результат:
2 * (я * я)
2 * я * я
источник
Я получил похожие результаты:
Я получил те же результаты, если оба цикла были в одной и той же программе или каждый был в отдельном файле .java / .class, выполняемом по отдельности.
Наконец, вот
javap -c -v <.java>
декомпиляция каждого:против
К вашему сведению -
источник
-XX:+PrintOptoAssembly
. Или просто используйте vtune или подобное.Интересное наблюдение с использованием Java 11 и выключение циклического развертывания со следующей опцией VM:
Цикл с
2 * (i * i)
выражением приводит к более компактному нативному коду 1 :по сравнению с
2 * i * i
версией:Версия Java:
Результаты тестов:
Исходный код теста:
1 - используемые параметры виртуальной машины:
-XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0
источник
i
перед копированием для вычисления2*i
, он делает это после, поэтому ему нужна дополнительнаяadd r11d,2
инструкция. (Кроме того, он пропускаетadd same,same
глазок вместоshl
1 (добавление работает на большем количестве портов). Он также пропускает глазок LEA дляx*2 + 2
(lea r11d, [r8*2 + 2]
), если он действительно хочет делать вещи в таком порядке по какой-то сумасшедшей причине планирования инструкций. Мы уже могли видеть из развернутая версия, которая упускала LEA, стоила ему много мопов, так же, как обе петли здесьlea eax, [rax + r11 * 2]
заменил бы 2 инструкции (в обоих циклах), если бы JIT-компилятор успел найти эту оптимизацию в длительных циклах. Любой приличный опережающий компилятор найдет его. (Если, возможно, настройка не только для AMD, где масштабированный индекс LEA имеет задержку в 2 цикла, так что, может быть, и не стоит.)Я попробовал JMH, используя архетип по умолчанию: я также добавил оптимизированную версию на основе объяснения Рунеморо .
Результат здесь:
На моем ПК ( Core i7 860 - он ничего не делает, кроме чтения на моем смартфоне):
n += i*i
тогдаn*2
первый2 * (i * i)
второйJVM явно не оптимизирует так же, как человек (основываясь на ответе Рунеморо).
Теперь, читая байт-код:
javap -c -v ./target/classes/org/sample/MyBenchmark.class
Я не эксперт по байт-коду, но мы
iload_2
раньше, чем мыimul
: вероятно, в этом и заключается разница: могу предположить, что JVM оптимизирует чтениеi
дважды (i
уже здесь, и нет необходимости загружать его снова), пока2*i*i
оно может ' т.источник
Больше из дополнения. Я повторил эксперимент, используя последнюю версию Java 8 JVM от IBM:
И это показывает очень похожие результаты:
(второй результат с использованием 2 * i * i).
Интересно, что при работе на той же машине, но с использованием Oracle Java:
результаты в среднем немного медленнее:
Короче говоря, здесь важен даже младший номер версии HotSpot, поскольку незначительные различия в реализации JIT могут иметь заметные последствия.
источник
Два метода добавления генерируют немного другой байт-код:
Для
2 * (i * i)
:Для
2 * i * i
.И при использовании теста JMH, как это:
Разница очевидна:
То, что вы наблюдаете, является правильным, а не просто аномалией вашего стиля бенчмаркинга (т.е. без разминки, см. Как написать правильный микро-бенчмарк в Java? )
Бегом снова с Граалем:
Вы видите, что результаты намного ближе, что имеет смысл, поскольку Graal - это более производительный, более современный, более современный компилятор.
Так что на самом деле это зависит только от того, насколько хорошо JIT-компилятор способен оптимизировать определенный фрагмент кода, и не обязательно имеет логическую причину для этого.
источник