Оптимизирует ли Java деление на степени от двух до сдвига?

Оптимизирует ли Java-компилятор или JIT-компилятор деления или умножения с постоянной степенью двойки вплоть до сдвига битов?

Например, оптимизированы ли следующие два оператора, чтобы они были одинаковыми?

int median = start + (end - start) >>> 1;
int median = start + (end - start) / 2;

(в основном этот вопрос, но для Java)

Источник

3 ответа

Решение

Нет, компилятор Java не делает этого, потому что он не может быть уверен в том, что признак (end - start) будет. Почему это важно? Сдвиги битов на отрицательных целых числах дают результат, отличный от обычного деления. Здесь вы можете увидеть демо: этот простой тест:

System.out.println((-10) >> 1);  // prints -5
System.out.println((-11) >> 1);  // prints -6
System.out.println((-11) / 2);   // prints -5

Также обратите внимание, что я использовал >> вместо >>>, >>> это беззнаковое смещение, в то время как >> подписан

System.out.println((-10) >>> 1); // prints 2147483643

@Mystical: я написал тест, который показывает, что компилятор / JVM не выполняет эту оптимизацию: https://ideone.com/aKDShA

Источник

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

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

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

Если JVM не делает этого, вы можете легко сделать это самостоятельно.

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

Если вы можете выразить свой оригинальный код в этой форме:

int result = x / (1 << shift);

Вы можете заменить его следующим оптимизированным кодом:

int result = (x + (x >> 31 >>> (32 - shift))) >> shift;

Или, альтернативно:

int result = (x + ((x >> 31) & ((1 << shift) - 1))) >> shift;

Эти формулы компенсируют неправильное округление, добавляя небольшое число, вычисленное из знакового бита дивиденда. Это работает для любого x со всеми значениями сдвига от 1 до 30.

Если сдвиг равен 1 (т.е. вы делите на 2), то >> 31 можно удалить в первой формуле, чтобы получить этот очень аккуратный фрагмент:

int result = (x + (x >>> 31)) >> 1;

Я обнаружил, что эти методы быстрее, даже когда сдвиг не является постоянным, но, очевидно, они приносят наибольшую пользу, если сдвиг постоянен. Примечание: для longx вместо intизмените 31 и 32 соответственно на 63 и 64.

Изучение сгенерированного машинного кода показывает, что (что неудивительно) виртуальная машина HotSpot Server может выполнять эту оптимизацию автоматически, когда сдвиг постоянен, но (что неудивительно) виртуальная машина клиента HotSpot слишком глупа.

Источник
Другие вопросы по тегам