example - paint java swing




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

Я пишу некоторый код на 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 != 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, смешанный режим)


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

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


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

    (a*b != 0)

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

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

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


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

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

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

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

  • ВМ оптимизирует выражение во время первых нескольких запусков внешнего цикла ( 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-разрядную версию, имейте в виду, что она поставляется в двух вариантах: виртуальная машина «Клиент» имеет другие (более слабые) оптимизации по сравнению с виртуальной машиной «Сервер».

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


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

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

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

  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 != 0 случаев. В логике предсказателей веток может быть что-то умное. Или это может указывать на что-то еще.

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

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







branch-prediction