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

Я новичок в 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. для 3-го варианта.

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

ONE FINAL ИНТЕРЕСНОЕ ЗАМЕЧАНИЕ, используя модуль для «Окончательной объявленной переменной» с 65536 (несимпатичное число) было вдвое меньше (медленнее), чем фиксированное значение.Там, где раньше было тестирование примерно с той же скоростью.

Ответы [ 4 ]

0 голосов
/ 29 января 2019

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

long progressCheck = 50000;

long counter = progressCheck;

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

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

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

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

0 голосов
/ 29 января 2019

В последующих действиях до @ 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

0 голосов
/ 29 января 2019

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

0 голосов
/ 28 января 2019

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

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...