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

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

Я новичок в Java, и вчера вечером запускал какой-то код, и это меня очень беспокоило. Я создавал простую программу для отображения всех выходов X в цикле for, и я заметил МАССОВОЕ снижение производительности, когда я использовал модуль как variable % variable против 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 (не довольно большое число) вдвое быстрее (медленнее), чем фиксированное значение. Где раньше это было тестирование примерно с той же скоростью.

4b9b3361

Ответ 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 1 результаты следующие:

для 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)
    }
}

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