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

Я новичок в Java, и прошлой ночью выполнял какой-то код, и это действительно беспокоило меня. Я строил простую программу для отображения всех выходов X в цикле for, и я заметил МАССОВОЕ снижение производительности, когда я использовал модуль как variable % variablevs variable % 5000или еще много чего. Может кто-нибудь объяснить мне, почему это происходит и чем это вызвано? Так что я могу быть лучше ...

Вот «эффективный» код (извините, если я неправильно понял синтаксис, я сейчас не на компьютере с кодом)

long startNum = 0;
long stopNum = 1000000000L;

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

Вот "неэффективный код"

long startNum = 0;
long stopNum = 1000000000L;
long progressCheck = 50000;

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

Имейте в виду, у меня была переменная даты для измерения различий, и как только она стала достаточно длинной, первая заняла 50 мс, а другая - 12 секунд или что-то в этом роде. Возможно, вам придется увеличить stopNumили уменьшить, progressCheckесли ваш компьютер более эффективен, чем мой, или нет.

Я искал этот вопрос в Интернете, но не могу найти ответ, может быть, я просто не правильно его спрашиваю.

РЕДАКТИРОВАТЬ: Я не ожидал, что мой вопрос будет настолько популярным, я ценю все ответы. Я выполнил эталонный тест по каждой полученной половине времени, и неэффективный код занял значительно больше времени, 1/4 секунды по сравнению с 10 секундами отдача или взятие. Конечно, они используют println, но они оба делают одинаковое количество, так что я бы не подумал, что это сильно исказит его, особенно если расхождение повторяется. Что касается ответов, так как я новичок в Java, я позволю голосам решить, какой ответ лучше. Я постараюсь выбрать один к среде.

РЕДАКТИРОВАТЬ 2: Я собираюсь сделать еще один тест сегодня вечером, где вместо модуля, он просто увеличивает переменную, а когда он достигает progressCheck, он выполнит ее, а затем сбросит эту переменную на 0. для третьего варианта.

EDIT3.5:

Я использовал этот код, и ниже я покажу свои результаты. Спасибо ВСЕМ за прекрасную помощь! Я также попытался сравнить короткое значение long с 0, поэтому все мои новые проверки выполняются когда-либо «65536» раз, делая его равным в повторениях.

public class Main {


    public static void main(String[] args) {

        long startNum = 0;
        long stopNum = 1000000000L;
        long progressCheck = 65536;
        final long finalProgressCheck = 50000;
        long date;

        // using a fixed value
        date = System.currentTimeMillis();
        for (long i = startNum; i <= stopNum; i++) {
            if (i % 65536 == 0) {
                System.out.println(i);
            }
        }
        long final1 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();
        //using a variable
        for (long i = startNum; i <= stopNum; i++) {
            if (i % progressCheck == 0) {
                System.out.println(i);
            }
        }
        long final2 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();

        // using a final declared variable
        for (long i = startNum; i <= stopNum; i++) {
            if (i % finalProgressCheck == 0) {
                System.out.println(i);
            }
        }
        long final3 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();
        // using increments to determine progressCheck
        int increment = 0;
        for (long i = startNum; i <= stopNum; i++) {
            if (increment == 65536) {
                System.out.println(i);
                increment = 0;
            }
            increment++;

        }

        //using a short conversion
        long final4 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();
        for (long i = startNum; i <= stopNum; i++) {
            if ((short)i == 0) {
                System.out.println(i);
            }
        }
        long final5 = System.currentTimeMillis() - date;

                System.out.println(
                "\nfixed = " + final1 + " ms " + "\nvariable = " + final2 + " ms " + "\nfinal variable = " + final3 + " ms " + "\nincrement = " + final4 + " ms" + "\nShort Conversion = " + final5 + " ms");
    }
}

Полученные результаты:

• исправлено = 874 мс (обычно около 1000 мс, но быстрее из-за мощности 2)
• переменная = 8590 мс
• конечная переменная = 1944 мс (было ~ 1000 мс при использовании 50000)
• приращение = 1904 мс
• Короткое преобразование = 679 мс

Неудивительно, что из-за недостатка деления «Короткая конверсия» была на 23% быстрее, чем «быстрый» путь. Это интересно отметить. Если вам нужно что-то показывать или сравнивать каждые 256 раз (или примерно там), вы можете сделать это и использовать

if ((byte)integer == 0) {'Perform progress check code here'}

ОДНО ЗАКЛЮЧИТЕЛЬНОЕ ЗАИНТЕРЕСОВАННОЕ ПРИМЕЧАНИЕ: использование модуля в «Окончательной объявленной переменной» с 65536 (не довольно большое число) было вдвое быстрее (медленнее), чем фиксированное значение. Где раньше это было тестирование примерно с той же скоростью.

Вы измеряете заглушку 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. Но как только метод перезапускается с самого начала, запускается новая неограниченная версия, которая использует все доступные оптимизации компилятора.

В продолжение комментария @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}

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

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выше.

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

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)
    }
}

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