Производительность вызова метода Java

У меня есть этот кусок кода, делающий Range Minimum Query. Когда t = 100000, я и j всегда изменяются в каждой строке ввода, время его выполнения в Java 8u60 составляет около 12 секунд.

Когда я извлекаю новый метод для поиска минимального значения, время выполнения в 4 раза быстрее (около 2,5 секунд).

Я всегда думал, что вызовы методов медленны. Но этот пример показывает обратное. Java 6 также демонстрирует это, но время выполнения намного медленнее в обоих случаях (17 секунд и 10 секунд). Может кто-то дать некоторое представление об этом?

Ответы

Ответ 1

TL; DR JIT-компилятор имеет больше возможностей для оптимизации внутреннего цикла во втором случае, поскольку замена на стеке происходит в другой точке.

Мне удалось воспроизвести проблему с уменьшенным тестовым случаем.
Нет операций ввода-вывода или строковых операций, всего два вложенных цикла с доступом к массиву.

public class NestedLoop {
    private static final int ARRAY_SIZE = 5000;
    private static final int ITERATIONS = 1000000;

    private int[] width = new java.util.Random(0).ints(ARRAY_SIZE).toArray();

    public long inline() {
        long sum = 0;

        for (int i = 0; i < ITERATIONS; i++) {
            int min = width[0];
            for (int k = 1; k < ARRAY_SIZE; k++) {
                if (min > width[k]) {
                    min = width[k];
                }
            }
            sum += min;
        }

        return sum;
    }

    public long methodCall() {
        long sum = 0;

        for (int i = 0; i < ITERATIONS; i++) {
            int min = getMin();
            sum += min;
        }

        return sum;
    }

    private int getMin() {
        int min = width[0];
        for (int k = 1; k < ARRAY_SIZE; k++) {
            if (min > width[k]) {
                min = width[k];
            }
        }
        return min;
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        long sum = new NestedLoop().inline();  // or .methodCall();
        long endTime = System.nanoTime();

        long ms = (endTime - startTime) / 1000000;
        System.out.println("sum = " + sum + ", time = " + ms + " ms");
    }
}

inline вариант действительно работает в 3-4 раза медленнее, чем methodCall.

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

-XX:-TieredCompilation
-XX:CompileOnly=NestedLoop
-XX:+UnlockDiagnosticVMOptions
-XX:+PrintCompilation
-XX:+TraceNMethodInstalls

'inline' журнал компиляции:

    251   46 %           NestedLoop::inline @ 21 (70 bytes)
Installing osr method (4) NestedLoop.inline()J @ 21

Журнал компиляции methodCall:

    271   46             NestedLoop::getMin (41 bytes)
Installing method (4) NestedLoop.getMin()I 
    274   47 %           NestedLoop::getMin @ 9 (41 bytes)
Installing osr method (4) NestedLoop.getMin()I @ 9
    314   48 %           NestedLoop::methodCall @ 4 (30 bytes)
Installing osr method (4) NestedLoop.methodCall()J @ 4

Это означает, что JIT выполняет свою работу, но сгенерированный код должен быть другим.
Пусть проанализируйте его с помощью -XX:+PrintAssembly.

'inline' разборка (самый горячий фрагмент)

0x0000000002df4dd0: inc    %ebp               ; OopMap{r11=Derived_oop_rbx rbx=Oop off=114}
                                              ;*goto
                                              ; - NestedLoop::[email protected] (line 12)

0x0000000002df4dd2: test   %eax,-0x1d64dd8(%rip)        # 0x0000000001090000
                                              ;*iload
                                              ; - NestedLoop::[email protected] (line 12)
                                              ;   {poll}
0x0000000002df4dd8: cmp    $0x1388,%ebp
0x0000000002df4dde: jge    0x0000000002df4dfd  ;*if_icmpge
                                              ; - NestedLoop::[email protected] (line 12)

0x0000000002df4de0: test   %rbx,%rbx
0x0000000002df4de3: je     0x0000000002df4e4c
0x0000000002df4de5: mov    (%r11),%r10d       ;*getfield width
                                              ; - NestedLoop::[email protected] (line 13)

0x0000000002df4de8: mov    0xc(%r10),%r9d     ; implicit exception
0x0000000002df4dec: cmp    %r9d,%ebp
0x0000000002df4def: jae    0x0000000002df4e59
0x0000000002df4df1: mov    0x10(%r10,%rbp,4),%r8d  ;*iaload
                                              ; - NestedLoop::[email protected] (line 13)

0x0000000002df4df6: cmp    %r8d,%r13d
0x0000000002df4df9: jg     0x0000000002df4dc6  ;*if_icmple
                                              ; - NestedLoop::[email protected] (line 13)

0x0000000002df4dfb: jmp    0x0000000002df4dd0

"методCall" разборки (также самая горячая часть)

0x0000000002da2af0: add    $0x8,%edx          ;*iinc
                                              ; - NestedLoop::[email protected] (line 36)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2af3: cmp    $0x1381,%edx
0x0000000002da2af9: jge    0x0000000002da2b70  ;*iload_1
                                              ; - NestedLoop::[email protected] (line 37)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2afb: mov    0x10(%r9,%rdx,4),%r11d  ;*iaload
                                              ; - NestedLoop::[email protected] (line 37)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b00: cmp    %r11d,%ecx
0x0000000002da2b03: jg     0x0000000002da2b6b  ;*iinc
                                              ; - NestedLoop::[email protected] (line 36)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b05: mov    0x14(%r9,%rdx,4),%r11d  ;*iaload
                                              ; - NestedLoop::[email protected] (line 37)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b0a: cmp    %r11d,%ecx
0x0000000002da2b0d: jg     0x0000000002da2b5c  ;*iinc
                                              ; - NestedLoop::[email protected] (line 36)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b0f: mov    0x18(%r9,%rdx,4),%r11d  ;*iaload
                                              ; - NestedLoop::[email protected] (line 37)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b14: cmp    %r11d,%ecx
0x0000000002da2b17: jg     0x0000000002da2b4d  ;*iinc
                                              ; - NestedLoop::[email protected] (line 36)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b19: mov    0x1c(%r9,%rdx,4),%r11d  ;*iaload
                                              ; - NestedLoop::[email protected] (line 37)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b1e: cmp    %r11d,%ecx
0x0000000002da2b21: jg     0x0000000002da2b66  ;*iinc
                                              ; - NestedLoop::[email protected] (line 36)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b23: mov    0x20(%r9,%rdx,4),%r11d  ;*iaload
                                              ; - NestedLoop::[email protected] (line 37)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b28: cmp    %r11d,%ecx
0x0000000002da2b2b: jg     0x0000000002da2b61  ;*iinc
                                              ; - NestedLoop::[email protected] (line 36)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b2d: mov    0x24(%r9,%rdx,4),%r11d  ;*iaload
                                              ; - NestedLoop::[email protected] (line 37)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b32: cmp    %r11d,%ecx
0x0000000002da2b35: jg     0x0000000002da2b52  ;*iinc
                                              ; - NestedLoop::[email protected] (line 36)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b37: mov    0x28(%r9,%rdx,4),%r11d  ;*iaload
                                              ; - NestedLoop::[email protected] (line 37)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b3c: cmp    %r11d,%ecx
0x0000000002da2b3f: jg     0x0000000002da2b57  ;*iinc
                                              ; - NestedLoop::[email protected] (line 36)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b41: mov    0x2c(%r9,%rdx,4),%r11d  ;*iaload
                                              ; - NestedLoop::[email protected] (line 37)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b46: cmp    %r11d,%ecx
0x0000000002da2b49: jg     0x0000000002da2ae6  ;*if_icmple
                                              ; - NestedLoop::[email protected] (line 37)
                                              ; - NestedLoop::[email protected] (line 27)

0x0000000002da2b4b: jmp    0x0000000002da2af0

Скомпилированный код полностью отличается; methodCall оптимизирован намного лучше.

цикл имеет 8 итераций, развернутых;
проверка границ массива отсутствует; Поле
width кэшируется в регистре.

Напротив, inline вариант

не выполняет разворот цикла;
загружает массив width из памяти каждый раз;
выполняет проверку границ массива на каждой итерации.

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

Замена на стоп обычно происходит на обратных ветвях (т.е. в нижней части цикла). inline метод имеет два вложенных цикла, а OSR происходит внутри внутреннего цикла, а methodCall имеет только один внешний цикл. Переход OSR во внешнем цикле более благоприятный, поскольку JIT-компилятор имеет больше свободы для оптимизации внутреннего цикла. И это именно то, что происходит в вашем случае.

Ответ 2

Без фактического анализа getMin, скорее всего, будет скомпилирован JIT, когда вы извлекли его в метод, который вызывался много раз. Если вы используете JSM HotSpot, это происходит по умолчанию после 10 000 попыток метода.

Вы всегда можете проверить окончательный код, используемый вашим приложением, используя правильные флаги и сборки JVM. Посмотрите вопрос/ответ Как увидеть JIT-скомпилированный код в JVM для примера.

Ответ 3

Одним из преимуществ Java над языками, скомпилированными как С++, является то, что JIT (Just in time compiler) может делать оптимизации из байт-кода во время выполнения кода. Кроме того, сам компилятор Java готов сделать несколько оптимизаций уже на этапах сборки. Эти методы позволяют, например, превращать вызов метода во встроенный код внутри цикла, что позволяет избежать накладных расходов на поиск повторяющихся методов при полиморфных вызовах. Выполнение вызова метода run inline означает, что код метода работает так, как если бы он был написан непосредственно в том месте, где вызывается метод. Таким образом, нет накладных расходов на поиск метода, который нужно выполнить, выделения памяти, новых переменных контекста. В основном в вашей петле, потеря обработки происходит, когда вы выделяете новые переменные в памяти (например, int k), когда вы передаете это для метода, вы в конечном итоге уменьшаете накладные расходы, поскольку переменные уже будут выделены для этого выполнения

Ответ 4

Вопрос не дает воспроизводимого тестового примера. Итак Я создал один, который фокусируется исключительно на вычислении минимальных значений:

git clone [email protected]:lemire/microbenchmarks.git
cd microbenchmarks
mvn clean install
java -cp target/microbenchmarks-0.0.1-jar-with-dependencies.jar me.lemire.microbenchmarks.rangequery.RangeMinimum

Мои результаты (на сервере, настроенном для тестирования, Java 8):

m.l.m.r.RangeMinimum.embeddedmin    avgt        5  0.053 ± 0.009  ms/op
m.l.m.r.RangeMinimum.fncmin         avgt        5  0.052 ± 0.003  ms/op

Таким образом, в моем тестовом случае нет существенной разницы в производительности между одним большим циклом с подслоем или одним циклом, содержащим вызов функции. Обратите внимание, что эталонный вызов вызывает функции несколько раз, чтобы компилятор JIT мог выполнять свою работу.

Ответ 5

Я считаю, что java делает некоторую оптимизацию /memoization. Он может кэшировать результаты функций, если функции/методы чисты. Я считаю, что ваше время уменьшилось, но ваше пространство/память увеличится (из-за воспоминаний) и наоборот.