Перемещение битов влево и вправо, по-видимому, быстрее, чем операции умножения и деления на большинстве, возможно даже на всех, процессорах, если вы используете мощность 2. Однако это может уменьшить ясность кода для некоторых читателей и некоторые алгоритмы, Является ли бит-сдвиг действительно необходимым для производительности, или я могу ожидать, что компилятор или виртуальная машина заметят случай и оптимизируют его (в частности, когда сила-2 является литералом)? Меня в основном интересуют поведение Java и .NET, но также приветствуем понимание других реализаций языка.
Перемещает бит быстрее, чем умножение и деление на Java?.СЕТЬ?
Ответ 1
Большинство компиляторов сегодня будут делать больше, чем конвертировать умножить или разделить на две операции смены. При оптимизации многие компиляторы могут оптимизировать умножение или деление с постоянной времени компиляции, даже если это не сила 2. Часто умножение или деление можно разложить на ряд сдвигов и добавлений, и если эта серия операций будет быстрее чем умножить или разделить, компилятор будет использовать его.
Для деления на константу компилятор может часто преобразовывать операцию в умножение на "магическое число", за которым следует сдвиг. Это может быть основной заставкой с тактовым циклом, поскольку умножение часто происходит намного быстрее, чем операция деления.
Книга Генри Уоррена, Hacker Delight, содержит множество информации по этой теме, которая также хорошо освещена на веб-сайте компаньона:
См. также обсуждение (со ссылкой или двумя) в:
В любом случае, все это сводится к тому, чтобы компилятор мог заботиться о утомительных деталях микрооптимизации. Прошло много лет с тех пор, как ваши собственные смены перехитрили компилятор.
Ответ 2
Почти любая окружающая среда, достойная его соли, оптимизирует это для вас. И если это не так, у вас есть большая рыба, чтобы жарить. Серьезно, не тратьте больше внимания на это. Вы узнаете, когда у вас проблемы с производительностью. И после запуска профилировщика вы узнаете, что вызывает его, и должно быть достаточно ясно, как его исправить.
Вы никогда не услышите, как кто-либо скажет: "Моя заявка была слишком медленной, затем я начал случайным образом заменять x * 2 на x << 1, и все было исправлено!" Проблемы с производительностью, как правило, решаются путем поиска способа сделать работу на порядок меньше, а не найти способ сделать одну и ту же работу на 1% быстрее.
Ответ 3
В этих случаях люди ошибаются.
99%, когда они пытаются догадаться о современных (и всех будущих) компиляторах.
99,9%, когда они пытаются вторгаться в современные (и все будущие) JIT в одно и то же время.
99,999%, когда они пытаются второй угадать современные (и все будущие) оптимизации ЦП.
Программа таким образом, чтобы точно описать то, что вы хотите выполнить, а не как это сделать. Будущие версии JIT, VM, компилятора и процессора могут быть независимо улучшены и оптимизированы. Если вы укажете что-то настолько маленькое и конкретное, вы потеряете выгоду от всех будущих оптимизаций.
Ответ 4
Вы можете почти наверняка зависеть от оптимизации умножения буквальной мощности в два на операцию сдвига. Это одна из первых оптимизаций, которые будут изучать студенты компиляции.:)
Однако я не думаю, что для этого есть гарантия. Ваш исходный код должен отражать ваше намерение, а не пытаться сказать оптимизатору, что делать. Если вы делаете большее количество, используйте умножение. Если вы перемещаете небольшое поле из одного места в другое (подумайте о цветовой манипуляции RGB), используйте операцию переключения. В любом случае, ваш исходный код будет отражать то, что вы на самом деле делаете.
Ответ 5
Обратите внимание, что сдвиг вниз и деление (в Java, конечно) дают разные результаты для отрицательных, нечетных чисел.
int a = -7;
System.out.println("Shift: "+(a >> 1));
System.out.println("Div: "+(a / 2));
Печать
Shift: -4
Div: -3
Так как Java не имеет никаких неподписанных номеров, для компилятора Java это не реально оптимизировать.
Ответ 6
На компьютерах, которые я тестировал, целые деления от 4 до 10 раз медленнее, чем другие операции.
Когда компиляторы могут заменить деления на кратные 2 и заставить вас не видеть разницы, деления, не кратные 2, значительно медленнее.
Например, у меня есть (графическая) программа с множеством многих делений на 255. Фактически, мои вычисления:
r = (((top.R - bottom.R) * alpha + (bottom.R * 255)) * 0x8081) >> 23;
Я могу гарантировать, что это намного быстрее, чем предыдущие вычисления:
r = ((top.R - bottom.R) * alpha + (bottom.R * 255)) / 255;
так что нет, компиляторы не могут делать все трюки оптимизации.
Ответ 7
Я бы спросил: "Что ты делаешь, что это имеет значение?". Сначала создайте свой код для удобства чтения и обслуживания. Вероятность того, что стандартное умножение битов смещения стилей приведет к разнице в производительности, ЧРЕЗМЕРНО мало.
Ответ 8
Это зависит от оборудования. Если мы говорим о микроконтроллере или i386, смещение может быть быстрее, но, как утверждают несколько ответов, ваш компилятор обычно будет делать оптимизацию для вас.
На современном оборудовании (Pentium Pro и выше) конвейерная обработка делает это совершенно неуместным и отклоняется от проторенного пути, как правило, означает, что вы теряете гораздо больше оптимизаций, чем можете получить.
Микрооптимизация - это не только трата вашего времени, но и чрезвычайно трудно получить право.
Ответ 9
Если компилятор (константа времени компиляции) или JIT (константа времени выполнения) знает, что делитель или мультипликатор является степенью двух и целочисленной арифметики, он преобразует ее в сдвиг для вас.
Ответ 10
Я ошеломлен, так как я просто написал этот код и понял, что переход на один на самом деле медленнее, чем умножение на 2!
(EDIT: изменил код, чтобы перестать переполняться после предложения Майкла Майерса, но результаты одинаковы! Что здесь не так?)
import java.util.Date;
public class Test {
public static void main(String[] args) {
Date before = new Date();
for (int j = 1; j < 50000000; j++) {
int a = 1 ;
for (int i = 0; i< 10; i++){
a *=2;
}
}
Date after = new Date();
System.out.println("Multiplying " + (after.getTime()-before.getTime()) + " milliseconds");
before = new Date();
for (int j = 1; j < 50000000; j++) {
int a = 1 ;
for (int i = 0; i< 10; i++){
a = a << 1;
}
}
after = new Date();
System.out.println("Shifting " + (after.getTime()-before.getTime()) + " milliseconds");
}
}
Результаты:
Умножение 639 миллисекунд
Смена 718 миллисекунд
Ответ 11
По результатам этого микропредметника смещение в два раза быстрее, чем деление (Oracle Java 1.7.0_72).
Ответ 12
Большинство компиляторов в случае необходимости будут умножать и делить на сдвиги бит. Это одна из самых простых оптимизаций. Итак, вы должны сделать то, что более легко читаемо и подходит для данной задачи.
Ответ 13
Это анализ теста, сделанного Саввасом Далкицисом. Хотя этот тест проверяет скорость умножения по смещению битов, используемые значения не совпадают, проверьте код ниже на С#, который отображает значения)
for (int i = 0, j = 1, k = 1; i < 10; i++)
{
j = j * 2;
k <<= 2;
Console.WriteLine("{0} {1}", j, k);
}
Эквивалентный код примера Savvas Dalkitsis со значениями, отображаемыми на С#, будет
public static void Main(String[] args)
{
for (int i = 0, j = 1, k = 1; i < 10; i++)
{
j = j * 2; k <<= 2;
Console.WriteLine("{0} {1}", j, k);
}
Console.WriteLine("-----------------------------------------------");
DateTime before = DateTime.Now;
for (int j = 1; j < 500000000; j++)
{
int a = 1;
for (int i = 0; i < 10; i++) a *= 2;
}
DateTime after = DateTime.Now;
Console.WriteLine("Multiplying " + (after - before).ToString() + " milliseconds");
before = DateTime.Now;
for (int j = 1; j < 500000000; j++)
{
int a = 1;
for (int i = 0; i < 10; i++) a = a << 1;
}
after = DateTime.Now;
Console.WriteLine("Shifting " + (after - before).ToString() + " milliseconds");
Console.ReadKey();
}