Почему если (variable1% variable2 == 0) неэффективно?

Ответ 1

Вы измеряете заглушку OSR (замена в стеке).

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

Заглушки OSR не так оптимизированы, как обычные методы, потому что им требуется структура кадра, совместимая с интерпретируемым кадром. Я показал это уже в следующих ответах: 1, 2, 3.

Подобное происходит и здесь. Пока "неэффективный код" выполняет длинный цикл, метод компилируется специально для замены в стеке прямо внутри цикла. Состояние передается из интерпретируемого фрейма в метод, скомпилированный OSR, и это состояние включает локальную переменную progressCheck. В этот момент JIT не может заменить переменную константой и, следовательно, не может применить определенные оптимизации, такие как снижение прочности.

В частности, это означает, что JIT не заменяет целочисленное деление на умножение. (См. Почему GCC использует умножение на странное число при реализации целочисленного деления? Для трюка asm от опережающего компилятора, когда значение является константой времени компиляции после встраивания/распространения констант, если эти оптимизации включены Целочисленное литеральное право в выражении % также оптимизируется с помощью gcc -O0, аналогично тому, где оно оптимизируется с помощью JITer даже в заглушке OSR.)

Однако, если вы запустите один и тот же метод несколько раз, при втором и последующих запусках будет выполнен обычный (не OSR) код, который полностью оптимизирован. Вот эталонный тест для доказательства теории (с использованием JMH):

@State(Scope.Benchmark)
public class Div {

    @Benchmark
    public void divConst(Blackhole blackhole) {
        long startNum = 0;
        long stopNum = 100000000L;

        for (long i = startNum; i <= stopNum; i++) {
            if (i % 50000 == 0) {
                blackhole.consume(i);
            }
        }
    }

    @Benchmark
    public void divVar(Blackhole blackhole) {
        long startNum = 0;
        long stopNum = 100000000L;
        long progressCheck = 50000;

        for (long i = startNum; i <= stopNum; i++) {
            if (i % progressCheck == 0) {
                blackhole.consume(i);
            }
        }
    }
}

И результаты:

# Benchmark: bench.Div.divConst

# Run progress: 0,00% complete, ETA 00:00:16
# Fork: 1 of 1
# Warmup Iteration   1: 126,967 ms/op
# Warmup Iteration   2: 105,660 ms/op
# Warmup Iteration   3: 106,205 ms/op
Iteration   1: 105,620 ms/op
Iteration   2: 105,789 ms/op
Iteration   3: 105,915 ms/op
Iteration   4: 105,629 ms/op
Iteration   5: 105,632 ms/op


# Benchmark: bench.Div.divVar

# Run progress: 50,00% complete, ETA 00:00:09
# Fork: 1 of 1
# Warmup Iteration   1: 844,708 ms/op          <-- much slower!
# Warmup Iteration   2: 105,893 ms/op          <-- as fast as divConst
# Warmup Iteration   3: 105,601 ms/op
Iteration   1: 105,570 ms/op
Iteration   2: 105,475 ms/op
Iteration   3: 105,702 ms/op
Iteration   4: 105,535 ms/op
Iteration   5: 105,766 ms/op

Самая первая итерация divVar действительно намного медленнее из-за неэффективно скомпилированной заглушки OSR. Но как только метод перезапускается с самого начала, запускается новая неограниченная версия, которая использует все доступные оптимизации компилятора.

Ответ 2

В продолжение комментария @phuclv я проверил код, сгенерированный JIT ¹ результаты следующие:

для variable % 5000 (деление на константу):

mov     rax,29f16b11c6d1e109h
imul    rbx
mov     r10,rbx
sar     r10,3fh
sar     rdx,0dh
sub     rdx,r10
imul    r10,rdx,0c350h    ; <-- imul
mov     r11,rbx
sub     r11,r10
test    r11,r11
jne     1d707ad14a0h

для variable % variable:

mov     rax,r14
mov     rdx,8000000000000000h
cmp     rax,rdx
jne     22ccce218edh
xor     edx,edx
cmp     rbx,0ffffffffffffffffh
je      22ccce218f2h
cqo
idiv    rax,rbx           ; <-- idiv
test    rdx,rdx
jne     22ccce218c0h

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

Версия Java:

java version "11" 2018-09-25
Java(TM) SE Runtime Environment 18.9 (build 11+28)
Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11+28, mixed mode)

^{1 - используемые параметры виртуальной машины: -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,src/java/Main.main}

Ответ 3

Как уже отмечали другие, операция общего модуля требует деления. В некоторых случаях деление может быть заменено (компилятором) умножением. Но оба могут быть медленными по сравнению с сложением/вычитанием. Следовательно, лучшая производительность может ожидаться чем-то вроде этого:

long progressCheck = 50000;

long counter = progressCheck;

for (long i = startNum; i <= stopNum; i++){
    if (--counter == 0) {
        System.out.println(i);
        counter = progressCheck;
    }
}

(В качестве незначительной попытки оптимизации мы используем здесь предварительный декремент обратного отсчета, потому что на многих архитектурах сравнение с 0 сразу после арифметической операции стоит ровно 0 инструкций/циклов ЦП, поскольку флаги ALU уже установлены соответствующим образом предыдущей операцией. Достойный оптимизирующий компилятор, однако, выполнит эту оптимизацию автоматически, даже если вы напишите if (counter++ == 50000) {... counter = 0; }.)

Заметьте, что часто вам не нужен/не нужен модуль, потому что вы знаете, что ваш счетчик цикла (i) или что-то еще увеличивается только на 1, и вы действительно не заботитесь о фактическом остатке, который даст вам модуль, просто Посмотрим, достигнет ли счетчик увеличения на единицу какого-либо значения.

Другой "трюк" заключается в использовании значений/пределов степени двух, например progressCheck = 1024; , Modulus степень двойки может быть быстро вычислены с помощью побитового and, т.е. if ( (i & (1024-1)) == 0 ) {...}. Это тоже должно быть довольно быстро, и на некоторых архитектурах может превзойти явный counter выше.

Ответ 4

Я также удивлен, увидев производительность вышеуказанных кодов. Это все о времени, затраченном компилятором на выполнение программы согласно объявленной переменной. Во втором (неэффективном) примере:

for (long i = startNum; i <= stopNum; i++) {
    if (i % progressCheck == 0) {
        System.out.println(i)
    }
}

Вы выполняете операцию модуля между двумя переменными. Здесь компилятор должен проверять значения stopNum и progressCheck чтобы переходить к конкретному блоку памяти, расположенному для этих переменных, каждый раз после каждой итерации, потому что это переменная, и ее значение может быть изменено.

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

В первом примере кода вы выполняете оператор модуля между переменной и постоянным числовым значением, которое не будет изменяться в процессе выполнения, и компилятору не нужно проверять значение этого числового значения из области памяти. Вот почему компилятор смог создать эффективный байт-код. Если вы объявите progressCheck как final или как final static переменную, то во время компиляции во время выполнения/времени компиляции будет известно, что это конечная переменная, и ее значение не будет изменяться, тогда компилятор заменит в коде progressCheck 50000:

for (long i = startNum; i <= stopNum; i++) {
    if (i % 50000== 0) {
        System.out.println(i)
    }
}

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