необъяснимый 10% + повышение производительности от простого добавления аргумента метода (более тонкий jit-код)
(обратите внимание: правильный ответ должен выходить за рамки воспроизведения).
После миллионов вызовов quicksort1 определенно быстрее, чем quicksort2, которые имеют идентичный код в стороне от этого 1 дополнительного аргумента.
Код находится в конце сообщения. Спойлер: Я также обнаружил, что jit-код более толстый на 224 байта, даже если он должен быть на самом деле проще (например, размер байтового кода говорит, см. Последнее последнее обновление ниже).
Даже после того, как вы пытаетесь отменить этот эффект с помощью какой-либо микрообъективной подвески (JMH), разница в производительности все еще существует.
Я спрашиваю: ПОЧЕМУ есть такая разница в генерации собственного кода и что он делает?
Добавляя аргумент к методу, он делает его быстрее...! Я знаю о эффектах gc/jit/warmup/etc. Вы можете запускать код как есть, или с большим или меньшим количеством итераций. На самом деле, вы должны даже прокомментировать один, а затем другой перфекционный тест, и запускать каждый в отдельном экземпляре jvm, чтобы доказать, что это не помеха между собой.
Байт-код не показывает большой разницы, кроме очевидного getstatic для sleft/sright, но и странного "iload 4" вместо "iload_3" (и istore 4/istore_3)
Что, черт возьми, происходит? Является ли iload_3/istore_3 действительно медленнее, чем iload 4/istore 4? И что гораздо медленнее, что даже добавленный getstatic-вызов все еще не замедляет работу? Я могу догадаться, что статические поля не используются, поэтому jit может просто пропустить его.
Во всяком случае, на моей стороне нет никакой двусмысленности, поскольку она всегда воспроизводима, и я ищу объяснение, почему javac/jit сделал то, что они сделали, и почему производительность сильно затронута. Это идентичный рекурсивный алгоритм с одинаковыми данными, сбой памяти и т.д.... Я не мог сделать более изолированное изменение, если бы захотел, чтобы показать значительную повторяющуюся разницу во времени выполнения.
Env:
java version "1.8.0_161"
Java(TM) SE Runtime Environment (build 1.8.0_161-b12)
Java HotSpot(TM) 64-Bit Server VM (build 25.161-b12, mixed mode)
(also tried and reproduced on java9)
on a 4 core i5 laptop 8GB ram.
windows 10 with the meltdown/specter patch.
С помощью -verbose: gc -XX: + PrintCompilation нет компиляции gc и jit, которая стабилизировалась в C2 (уровень 4).
При n = 20000:
main]: qs1: 1561.3336199999999 ms (res=null)
main]: qs2: 1749.748416 ms (res=null)
main]: qs1: 1422.0767509999998 ms (res=null)
main]: qs2: 1700.4858689999999 ms (res=null)
main]: qs1: 1519.5280269999998 ms (res=null)
main]: qs2: 1786.2206899999999 ms (res=null)
main]: qs1: 1450.0802979999999 ms (res=null)
main]: qs2: 1675.223256 ms (res=null)
main]: qs1: 1452.373318 ms (res=null)
main]: qs2: 1634.581156 ms (res=null)
Кстати, красивый java9, кажется, делает и быстрее, но все же на 10-15% друг от друга:
[0.039s][info][gc] Using G1
main]: qs1: 1287.062819 ms (res=null)
main]: qs2: 1451.041391 ms (res=null)
main]: qs1: 1240.800305 ms (res=null)
main]: qs2: 1391.2404299999998 ms (res=null)
main]: qs1: 1257.1707159999999 ms (res=null)
main]: qs2: 1433.84716 ms (res=null)
main]: qs1: 1233.7582109999998 ms (res=null)
main]: qs2: 1394.7195849999998 ms (res=null)
main]: qs1: 1250.885867 ms (res=null)
main]: qs2: 1413.88437 ms (res=null)
main]: qs1: 1261.5805739999998 ms (res=null)
main]: qs2: 1458.974334 ms (res=null)
main]: qs1: 1237.039902 ms (res=null)
main]: qs2: 1394.823751 ms (res=null)
main]: qs1: 1255.14672 ms (res=null)
main]: qs2: 1400.693295 ms (res=null)
main]: qs1: 1293.009808 ms (res=null)
main]: qs2: 1432.430952 ms (res=null)
main]: qs1: 1262.839628 ms (res=null)
main]: qs2: 1421.376644 ms (res=null)
КОД (ВКЛЮЧАЯ ИСПЫТАНИЯ):
(Пожалуйста, не обращайте внимание на то, насколько плох этот quicksort, это рядом с вопросом).
import java.util.Random;
import java.util.concurrent.Callable;
public class QuicksortTrimmed {
static void p(Object msg) {
System.out.println(Thread.currentThread().getName()+"]: "+msg);
}
static void perf(int N, String msg, Callable c) throws Exception {
Object res = null;
long t = System.nanoTime();
for(int i=0; i<N; i++) {
res = c.call();
}
Double d = 1e-6*(System.nanoTime() - t);
p(msg+": "+d+" ms (res="+res+")");
}
static String und = "__________";//10
static {
und += und;//20
und += und;//40
und += und;//80
und += und;//160
}
static String sleft = "//////////";//10
static {
sleft += sleft;//20
sleft += sleft;//40
sleft += sleft;//80
sleft += sleft;//160
}
static String sright= "\\\\\\\\\\\\\\\\\\\\";//10
static {
sright += sright;//20
sright += sright;//40
sright += sright;//80
sright += sright;//160
}
//============
public static void main(String[] args) throws Exception {
int N = 20000;
int n = 1000;
int bound = 10000;
Random r = new Random(1);
for(int i=0; i<5; i++) {
testperf(N, r, n, bound);
//System.gc();
}
}
static void testperf(int N, Random r, int n, int bound) throws Exception {
final int[] orig = r.ints(n, 0, bound).toArray();
final int[] a = orig.clone();
perf(N, "qs1", () -> {
System.arraycopy(orig, 0, a, 0, orig.length);
quicksort1(a, 0, a.length-1, und);
return null;
});
perf(N, "qs2", () -> {
System.arraycopy(orig, 0, a, 0, orig.length);
quicksort2(a, 0, a.length-1);
return null;
});
System.out.println();
}
private static void quicksort1(int[] a, final int _from, final int _to, String mode) {
int len = _to - _from + 1;
if(len==2) {
if(a[_from] > a[_to]) {
int tmp = a[_from];
a[_from] = a[_to];
a[_to] = tmp;
}
} else { //len>2
int mid = _from+len/2;
final int pivot = a[mid];
a[mid] = a[_to];
a[_to] = pivot; //the pivot value is the 1st high value
int i = _from;
int j = _to;
while(i < j) {
if(a[i] < pivot)
i++;
else if(i < --j) { //j is the index of the leftmost high value
int tmp = a[i];
a[i] = a[j]; //THIS IS HARMFUL: maybe a[j] was a high value too.
a[j] = tmp;
}
}
//swap pivot in _to with other high value in j
int tmp = a[j];
a[j] = a[_to];
a[_to] = tmp;
if(_from < j-1)
quicksort1(a, _from, j-1, sleft);
if(j+1 < _to)
quicksort1(a, j+1, _to, sright);
}
}
private static void quicksort2(int[] a, final int _from, final int _to) {
int len = _to - _from + 1;
if(len==2) {
if(a[_from] > a[_to]) {
int tmp = a[_from];
a[_from] = a[_to];
a[_to] = tmp;
}
} else { //len>2
int mid = _from+len/2;
final int pivot = a[mid];
a[mid] = a[_to];
a[_to] = pivot; //the pivot value is the 1st high value
int i = _from;
int j = _to;
while(i < j) {
if(a[i] < pivot)
i++;
else if(i < --j) { //j is the index of the leftmost high value
int tmp = a[i];
a[i] = a[j]; //THIS IS HARMFUL: maybe a[j] was a high value too.
a[j] = tmp;
}
}
//swap pivot in _to with other high value in j
int tmp = a[j];
a[j] = a[_to];
a[_to] = tmp;
if(_from < j-1)
quicksort2(a, _from, j-1);
if(j+1 < _to)
quicksort2(a, j+1, _to);
}
}
}
ОБНОВИТЬ:
Я сделал тест JMH, и он все еще доказывает, что quicksort1 быстрее, чем quicksort2.
# Run complete. Total time: 00:13:38
Benchmark Mode Cnt Score Error Units
MyBenchmark.testQuickSort1 thrpt 200 14861.437 ± 86.707 ops/s
MyBenchmark.testQuickSort2 thrpt 200 13097.209 ± 46.178 ops/s
Вот тест JMH:
package org.sample;
import java.util.Random;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.infra.Blackhole;
public class MyBenchmark {
static String und = "__________";//10
static {
und += und;//20
und += und;//40
und += und;//80
und += und;//160
}
static String sleft = "//////////";//10
static {
sleft += sleft;//20
sleft += sleft;//40
sleft += sleft;//80
sleft += sleft;//160
}
static String sright= "\\\\\\\\\\\\\\\\\\\\";//10
static {
sright += sright;//20
sright += sright;//40
sright += sright;//80
sright += sright;//160
}
static final int n = 1000;
static final int bound = 10000;
static Random r = new Random(1);
static final int[] orig = r.ints(n, 0, bound).toArray();
@State(Scope.Thread)
public static class ThrState {
int[] a;
@Setup(Level.Invocation)
public void setup() {
a = orig.clone();
}
}
//============
@Benchmark
public void testQuickSort1(Blackhole bh, ThrState state) {
int[] a = state.a;
quicksort1(a, 0, a.length-1, und);
bh.consume(a);
}
@Benchmark
public void testQuickSort2(Blackhole bh, ThrState state) {
int[] a = state.a;
quicksort2(a, 0, a.length-1);
bh.consume(a);
}
private static void quicksort1(int[] a, final int _from, final int _to, String mode) {
int len = _to - _from + 1;
if(len==2) {
if(a[_from] > a[_to]) {
int tmp = a[_from];
a[_from] = a[_to];
a[_to] = tmp;
}
} else { //len>2
int mid = _from+len/2;
final int pivot = a[mid];
a[mid] = a[_to];
a[_to] = pivot; //the pivot value is the 1st high value
int i = _from;
int j = _to;
while(i < j) {
if(a[i] < pivot)
i++;
else if(i < --j) { //j is the index of the leftmost high value
int tmp = a[i];
a[i] = a[j]; //THIS IS HARMFUL: maybe a[j] was a high value too.
a[j] = tmp;
}
}
//swap pivot in _to with other high value in j
int tmp = a[j];
a[j] = a[_to];
a[_to] = tmp;
if(_from < j-1)
quicksort1(a, _from, j-1, sleft);
if(j+1 < _to)
quicksort1(a, j+1, _to, sright);
}
}
private static void quicksort2(int[] a, final int _from, final int _to) {
int len = _to - _from + 1;
if(len==2) {
if(a[_from] > a[_to]) {
int tmp = a[_from];
a[_from] = a[_to];
a[_to] = tmp;
}
} else { //len>2
int mid = _from+len/2;
final int pivot = a[mid];
a[mid] = a[_to];
a[_to] = pivot; //the pivot value is the 1st high value
int i = _from;
int j = _to;
while(i < j) {
if(a[i] < pivot)
i++;
else if(i < --j) { //j is the index of the leftmost high value
int tmp = a[i];
a[i] = a[j]; //THIS IS HARMFUL: maybe a[j] was a high value too.
a[j] = tmp;
}
}
//swap pivot in _to with other high value in j
int tmp = a[j];
a[j] = a[_to];
a[_to] = tmp;
if(_from < j-1)
quicksort2(a, _from, j-1);
if(j+1 < _to)
quicksort2(a, j+1, _to);
}
}
}
ОБНОВИТЬ:
В этот момент я запустил и запустил jit-журнал для jitwatch (я использовал тег 1.3.0 и был создан с https://github.com/AdoptOpenJDK/jitwatch/tree/1.3.0)
-verbose:gc
-XX:+PrintGCDateStamps
-XX:+PrintGCDetails
-Xloggc:"./gc.log"
-XX:+UseGCLogFileRotation -XX:NumberOfGCLogFiles=10 -XX:GCLogFileSize=1M
-XX:+PrintGCApplicationStoppedTime
-XX:+PrintCompilation
-XX:+PrintSafepointStatistics
-XX:PrintSafepointStatisticsCount=1
-XX:+UnlockDiagnosticVMOptions -XX:+LogCompilation -XX:+PrintInlining
Нет никаких очевидных "предложений" от jitwatch, просто слишком большой, чтобы встроить или слишком глубоко, как для quicksort1, так и для quicksort2.
Одним из важных открытий является байт-код и коренная разница кода:
С дополнительным аргументом метода (quicksort1): байт код = 187 байт собственный код = 1872 байт
Без дополнительного аргумента метода (quicksort2): байтовый код = 178 байт (меньше на 9 байтов) собственный код = 2096 байт (больше на 224 байта !!!)
Это убедительное доказательство того, что jit-код более толстый и медленный в quicksort2.
Поэтому остается вопрос: что думал компилятор C2 jit? какое правило привело к созданию более быстрого собственного кода, когда я добавляю аргумент метода и 2 статические ссылки для загрузки и передачи?
Я наконец получил свою руку на ассемблерный код, но, как я и ожидал, почти невозможно разобраться и понять, что происходит. Я выполнил самую последнюю инструкцию, которую я смог найти на qaru.site/info/10944/.... У меня есть файл журнала размером 7 МБ xml (сжатый до 675 КБ), который вы можете получить его и посмотреть в течение 7 дней (истекает ~ может 4-го 2018 года) по адресу https://wetransfer.com/downloads/65fe0e94ab409d57cba1b95459064dd420180427150905/612dc9, если вы можете это понять ( в jitwatch, конечно!).
Добавленный параметр строки приводит к более компактному ассемблеру. Вопросы (все еще не отвеченные) почему? что в коде сборки отличается? каково правило или оптимизация, которая не используется в более медленном коде?
Ответы
Ответ 1
Я думаю, что я заметил что-то странное в коде сборки.
Во-первых, я добавил пустые строки, чтобы quicksort1 начинался со строки 100, а quicksort2 начинался с строки 200. Гораздо проще выстроить код сборки.
Я также изменил строку arg на int arg, просто чтобы проверить и доказать, что тип не является проблемой.
После утомительной задачи выстраивания кода asm в excel, вот файл xls: https://wetransfer.com/downloads/e56fd98fe248cef98f5a242b2db64f6920180430130753/7b8f2b (доступно в течение 7 дней). (Прошу прощения, если я не согласен в своей окраске, мне надоело...)
Образец, который я вижу, состоит в том, что для подготовки quicksort2 требуется больше mov ops. Если я правильно понимаю, встраивание собственного кода будет длиннее, и из-за рекурсии он выродится на несколько уровней, но достаточно, чтобы вызвать замедление. Я не очень хорошо разбираюсь в операциях, чтобы догадываться об этом.
Другими словами, когда последние быстрые стековые кадры из рекурсивного возврата указывают вверх, возможно, 3 или 5 уровней (трудно сказать) могут быть встроены, тогда он прибегает к прыжку. Однако эти байт-коды кадров quicksort2, используя более собственный код для неясных причин, составляют до сотни дополнительных операций.
На данный момент, я на 50% отвечу. C2 создает немного более толстый код, но его накачивают из-за наложения рекурсивных хвостовых фреймов.
Я думаю, что я собираюсь подать ошибку в oracle... Это была довольно сложная задача, но в конце концов, это очень разочаровывает, что неиспользуемый код Java приводит к худшей производительности!
Ответ 2
Воспроизведение и анализ
Я смог воспроизвести ваши результаты. Машинные данные:
Linux #143-Ubuntu x86_64 GNU/Linux
java version "1.8.0_171"
Java(TM) SE Runtime Environment (build 1.8.0_171-b11)
Java HotSpot(TM) 64-Bit Server VM (build 25.171-b11, mixed mode)
Я немного переписал ваш код, и я провел дополнительное тестирование. Ваше тестовое время включает System.arraycopy(). Я создал структуру массива 400 Мб и сохранил ее:
int[][][] data = new int[iterations][testCases][];
for (int iteration = 0; iteration < data.length; iteration++) {
for (int testcase = 0; testcase < data[iteration].length; testcase++) {
data[iteration][testcase] = random.ints(numberCount, 0, bound).toArray();
}
}
FileOutputStream fos = new FileOutputStream("test_array.dat");
ObjectOutputStream oos = new ObjectOutputStream(fos);
oos.writeObject(data);
После этого я пропустил эти тесты (разминка, разгон):
{
FileInputStream fis = new FileInputStream(fileName);
ObjectInputStream iis = new ObjectInputStream(fis);
int[][][] data = (int[][][]) iis.readObject();
perf("qs2", () -> {
for (int iteration = 0; iteration < data.length; iteration++) {
for (int testCase = 0; testCase < data[iteration].length; testCase++) {
quicksort2(data[iteration][testCase], 0, data[iteration][testCase].length - 1);
}
}
return null;
});
}
{
FileInputStream fis = new FileInputStream(fileName);
ObjectInputStream iis = new ObjectInputStream(fis);
int[][][] data = (int[][][]) iis.readObject();
perf("qs1", () -> {
for (int iteration = 0; iteration < data.length; iteration++) {
for (int testCase = 0; testCase < data[iteration].length; testCase++) {
quicksort1(data[iteration][testCase], 0, data[iteration][testCase].length - 1, und);
}
}
return null;
});
}
Если я запустил qs1 и qs2 вместе:
main]: qs1: 6646.219874 ms (res=null)
main]: qs2: 7418.376646 ms (res=null)
Результат не зависит от исполнения:
main]: qs2: 7526.215395 ms (res=null)
main]: qs1: 6624.261529 ms (res=null)
Я также запустил код в новых экземплярах JVM:
Экземпляр один:
main]: qs1: 6592.699738 ms (res=null)
Второй экземпляр:
main]: qs2: 7456.326028 ms (res=null)
Если вы попробуете его без JIT:
-Djava.compiler=NONE
Результаты выглядят как "ожидаемые" (более быстрый байт-код работает быстрее):
main]: qs1: 56547.589942 ms (res=null)
main]: qs2: 53585.909246 ms (res=null)
Для лучшего анализа я извлек коды в два разных класса.
Я использовал jclasslib для проверки байт-кода. Длина метода для меня:
Q1: 505
Q2: 480
Это имеет смысл для исполнения без JIT:
53585.909246×505÷480 = 56376.842019229
Что действительно близко к 56547.589942.
причина
Для меня в выводе компиляции (используя -XX:+PrintCompilation) У меня есть эти строки
1940 257 2 QS1::sort (185 bytes)
1953 258 % 4 QS1::sort @ 73 (185 bytes)
1980 259 4 QS1::sort (185 bytes)
1991 257 2 QS1::sort (185 bytes) made not entrant
9640 271 3 QS2::sort (178 bytes)
9641 272 4 QS2::sort (178 bytes)
9654 271 3 QS2::sort (178 bytes) made not entrant
Где % означает замену стека (где выполняется скомпилированный код). Согласно этому журналу, вызов с дополнительным параметром String оптимизируется, а второй - нет. Я думал о лучшем предсказании ветвей, но это не должно быть здесь (пыталось добавить произвольно сгенерированные строки в качестве параметров). Размеры выборки (400 МБ) в основном исключают кэширование. Я думал о оптимизации treshold, но когда я использую эти опции -Xcomp -XX:+PrintCompilation -Xbatch вывод следующий:
6408 3254 b 3 QS1::sort (185 bytes)
6409 3255 b 4 QS1::sort (185 bytes)
6413 3254 3 QS1::sort (185 bytes) made not entrant
14580 3269 b 3 QS2::sort (178 bytes)
14580 3270 b 4 QS2::sort (178 bytes)
14584 3269 3 QS2::sort (178 bytes) made not entrant
Это означает, что методам предусмотрена блокировка, скомпилированная перед вызовом, но время остается неизменным:
main]: qs1: 6982.721328 ms (res=null)
main]: qs2: 7606.077812 ms (res=null)
Ключом к этому я считаю String. В случае, если я изменил дополнительный (неиспользуемый) параметр на int он последовательно обрабатывается немного медленнее (работает с предыдущими параметрами оптимизации):
main]: qs1: 7925.472909 ms (res=null)
main]: qs2: 7727.628422 ms (res=null)
Я пришел к выводу, что на оптимизацию может влиять тип объекта дополнительных параметров. Вероятно, существует менее энергичная оптимизация в случае примитивов, которая имеет для меня смысл, но я не мог найти точного источника для этого утверждения.
Еще одно интересное.
