Почему (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:

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

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

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

Обновить

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

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

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

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

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

Процессор: Intel Core i7-3610QM @ 2,3 ГГц

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

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

Это компилятор или аппаратный уровень?

Это последнее, я думаю:

  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.

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

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

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

• Точно так (a*b)!=0же поступит неправильно для значений, которые переполняются. (Случайный пример: 196608 * 327680 равен 0, потому что истинный результат делится на 2 ³² , поэтому его младшие 32 бита равны 0, и эти биты - все, что вы получите, если это intоперация.)

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

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

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

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

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

Существует много неопределенностей, и всегда трудно сказать что-то определенное с такого рода микрооптимизациями, потому что трюк, который быстрее на одной ВМ или ЦП, может быть медленнее на другой. Если вы используете 32-разрядную версию HotSpot JVM, а не 64-разрядную версию, имейте в виду, что она поставляется в двух вариантах: виртуальная машина «Клиент» имеет другие (более слабые) оптимизации по сравнению с виртуальной машиной «Сервер».

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

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

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

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]оценивается, но компилятор не может быть уверен, что он не будет выбрасывать из диапазона или нулевой реф, когда вы это сделаете. Сокращая блок if до простых bools, компилятор может быть достаточно умен, чтобы понять, что оценка второго логического значения без необходимости не будет иметь отрицательных побочных эффектов.

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

    (a*b != 0)

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

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

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

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

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