Почему (a*b!= 0) быстрее, чем (a!= 0 & & b!= 0) в Java?

Я пишу некоторый код на Java, где в какой-то момент поток программы определяется тем, являются ли две переменные int, "a" и "b", ненулевыми (Примечание: a и b никогда не отрицательны и никогда не находятся в диапазоне переполнения целых чисел).

Я могу оценить его с

if (a != 0 && b != 0) { /* Some code */ }

или

if (a*b != 0) { /* Some code */ }

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

long time;
final int len = 50000000;
int arbitrary = 0;
int[][] nums = new int[2][len];

for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) {
    for(int i = 0 ; i < 2 ; i++) {
        for(int j = 0 ; j < len ; j++) {
            double random = Math.random();

            if(random < fraction) nums[i][j] = 0;
            else nums[i][j] = (int) (random*15 + 1);
        }
    }

    time = System.currentTimeMillis();

    for(int i = 0 ; i < len ; i++) {
        if( /*insert nums[0][i]*nums[1][i]!=0 or nums[0][i]!=0 && nums[1][i]!=0*/ ) arbitrary++;
    }
    System.out.println(System.currentTimeMillis() - time);
}

и результаты показывают, что если вы ожидаете, что "a" или "b" будут равны 0 более чем ~3% времени,a*b != 0 быстрее a!=0 && b!=0:

мне любопытно знать, почему. Может ли кто-нибудь пролить свет? Это компилятор или это на аппаратном уровень?

Edit:из любопытства... теперь, когда я узнал о предсказании ветвей, мне было интересно, что аналоговое сравнение покажет для или b не равно нулю:

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

обновление

1 - я добавил !(a==0 || b==0) к анализу, чтобы увидеть Что происходит.

2 - я a != 0 || b != 0,(a+b) != 0 и (a|b) != 0 из любопытства, узнав о предсказании ветвей. Но они логически не эквивалентны другим выражениям, потому что только a или b должен быть ненулевым, чтобы вернуть true, поэтому они не предназначены для сравнения эффективности обработки.

3-я также добавил фактический тест, который я использовал для анализа, который просто повторяет произвольную переменную int.

4 - Некоторые люди предлагали включить a != 0 & b != 0 в противоположность a != 0 && b != 0, с предсказанием, что он будет вести себя более внимательно к a*b != 0 потому что мы удалили бы эффект предсказания ветвей. Я этого не знал & может использоваться с булевыми переменными, я думал, что он используется только для двоичных операций с целыми числами.

Примечание: в контексте того, что я рассматривал все это, переполнение int не является проблемой, но это определенно важное соображение в общем контексте.

процессор: Intel Core i7-3610QM @ 2.3 GHz

версия Java: 1.8.0_45
Java (TM) SE Runtime Environment (build 1.8.0_45-b14)
Java HotSpot (TM) 64-разрядная серверная виртуальная машина (сборка 25.45-b02, смешанный режим)

5 355
javascript performance microbenchmark branch-prediction processing-efficiency

5 ответов:

я игнорирую вопрос, что ваш бенчмаркинг может быть ущербным, и принимая результат за чистую монету.

это компилятор или это на аппаратном уровне?

этот последний, я думаю:

  if (a != 0 && b != 0)

будет компилироваться до 2 нагрузок памяти и двух условных ветвей

  if (a * b != 0)

будет компилироваться до 2 нагрузок памяти, умножения и одной условной ветви.

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

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

(Примечание: приведенное выше объяснение упрощенно. Для более точного объяснения вам нужно посмотреть литературу, предоставленную производителем ЦП для кодеров языка ассемблера и составителей компиляторов. Страница Википедии на Филиала Предикторы - это хороший фон.)

однако, есть одна вещь, которую вы должны быть осторожны с этой оптимизацией. Есть ли какие-то ценности где a * b != 0 даст неправильный ответ? Рассмотрим случаи, когда вычисление продукта приводит к переполнению целого числа.

обновление

ваши графики, как правило, подтверждают то, что я сказал.

  • существует также эффект "предсказания ветвей" в условной ветви a * b != 0 случае, и это выходит на графиках.

  • если вы проецируете кривые за 0.9 на ось X, похоже, что 1) они будут встреча примерно в 1.0 и 2) точка встречи будет примерно на том же значении Y, что и для X = 0.0.

обновление 2

Я не понимаю, почему кривые различны для a + b != 0 и a | b != 0 случаях. Там может быть что-то умное в логике предсказателей ветвей. Или это может означать что-то другое.

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

однако, они оба имеют преимущество работы для всех неотрицательных значений a и b.

216

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

  • (a*b)!=0 будет делать неправильные вещи для значений, которые переполняются, и (a+b)!=0 дополнительно будет делать неправильные вещи для положительных и отрицательных значений, которые суммируются до нуля, поэтому вы не можете использовать ни одно из этих выражений в общем случае, даже если они работают здесь.

  • (a|b)!=0 и (a+b)!=0 тестировании, если или значение не равно нулю, в то время как (a*b)!=0 и a != 0 && b != 0 тестируют, если и не равны нулю. Эти два типа условий не будут выполняться для одного и того же процента данных.

  • виртуальная машина оптимизирует выражение во время первых нескольких запусков внешнего (fraction) петли, когда fraction равно 0, когда ветви почти никогда не берут. Оптимизатор может делать разные вещи, если вы начинаете fraction at 0,5.

  • если виртуальная машина не может устранить некоторые проверки границ массива здесь, в выражении есть четыре других ветви только из-за проверок границ, и это усложняет фактор при попытке выяснить, что происходит на низком уровне. Вы можете получить разные результаты, если вы разделите двумерный массив на два плоских массива, изменяя nums[0][i] и nums[1][i] до nums0[i] и nums1[i].

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

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

  • System.currentTimeMillis() на большинстве систем, не более точны, чем +/- 10 мс. System.nanoTime() обычно более точным.

как вы можете видеть есть много неопределенность, и всегда трудно сказать что-то определенное с такими микро-оптимизациями, потому что трюк, который быстрее на одной виртуальной машине или процессоре, может быть медленнее на другом. Если ваша виртуальная машина является HotSpot, имейте в виду, что есть еще две разновидности, с "клиентской" виртуальной машиной, имеющей разные (более слабые) оптимизации по сравнению с "серверной" виртуальной машиной.

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

63

ответы здесь хороши, хотя у меня была идея, которая могла бы улучшить ситуацию.

bool aNotZero = (nums[0][i] != 0);
bool bNotZero = (nums[1][i] != 0);
if (aNotZero && bNotZero) { /* Some code */ }

Он также может работать

int a = nums[0][i];
int b = nums[1][i];
if (a != 0 && b != 0) { /* Some code */ }

причина в том, что по правилам короткого замыкания, если первое логическое значение ложно, второе не должно оцениваться. Он должен выполнить дополнительный филиал, чтобы избежать оценки nums[1][i] Если nums[0][i] была ложной. Теперь вам может быть все равно, что nums[1][i] получает оценку, но компилятор не может быть уверен, что он не будет выбрасывать вне диапазона или нулевой ref, когда вы это делаете. Сократив блок if до простых bools, компилятор может быть достаточно умен, чтобы понять, что оценка второго логического значения без необходимости не будет иметь негативных побочных эффектов.

21

когда мы берем умножения, даже если одно число равно 0, то произведение равно 0. Во время написания 

    (a*b != 0)

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

   (a != 0 && b != 0)

, где каждый элемент сравнивается с 0 и оценивали. Следовательно, требуется меньше времени. Но я считаю, что второе условие может дать вам больше точное решение.

10

вы используете рандомизированные входные данные, что делает ветви непредсказуемыми. На практике ветви часто (~90%) предсказуемы, поэтому в реальном коде ветвящийся код, вероятно, будет быстрее.

что сказал. Я не вижу, как a*b != 0 может быть быстрее, чем (a|b) != 0. Как правило, целочисленное умножение стоит дороже, чем побитовое или. Но такие вещи иногда становятся странными. См., например, пример "Пример 7: аппаратные сложности" из Галерея кэша процессора Эффекты.

6