Сдвиг бита на X быстрее, чем сдвиг бита в один X раз?

Вопрос 1

В Java смещение в несколько раз дороже, чем использование одного оператора для сдвига на одно и то же число?

Например, это

int x = 5;
x = x << 16;

Быстрее, чем

int x = 5;
for (int i=0; i<16; ++i) {
    x = x << 1;
}

Далее, что насчет

int x = 5;
for (int i=0; i<16; ++i) {
    x = x*2;
}

Изменить: какова точная производительность «x ‹‹ 16»? Это та же скорость, что и "x ‹‹ 1"?

Вопрос №2

Есть ли онлайн-ресурс, который я могу использовать для определения производительности различных побитовых операций в Java, чтобы мне не приходилось тратить время пользователей StackOverflow? :-)


person Kirby    schedule 25.04.2012    source источник
comment
Выполнение многобитового сдвига почти всегда будет на порядок быстрее, чем использование однобитового цикла.   -  person Hot Licks    schedule 25.04.2012
comment
Кроме того, на несколько порядков быстрее, чем повторение цикла в Java...   -  person Damon    schedule 25.04.2012
comment
(И в 99,9% случаев не стоит даже беспокоиться о таких вещах. Создайте одну строку, и вы проделаете в 1000 раз больше работы.)   -  person Hot Licks    schedule 25.04.2012
comment
Спасибо Hot Licks и Деймону. Можете ли вы уточнить, что именно происходит с многобитным сдвигом? В частности, эквивалентно ли это одному утверждению? Например, x ‹‹ 1 по производительности такой же, как x ‹‹ 16?   -  person Kirby    schedule 25.04.2012
comment
Правильный ответ: совершенно очевидно, что использование одной смены дает вам непревзойденную производительность. Он преобразуется непосредственно в одну машинную инструкцию. Что касается других идиом, вам все еще может повезти, и JIT-компилятор сам поймет, что summa summarum вашего цикла - это всего лишь один сдвиг. Но зачем это делать.   -  person Marko Topolnik    schedule 25.04.2012
comment
Умножение может быть худшим из всех, в зависимости от деталей реализации. Или так же плохо, как в одну смену.   -  person Hot Licks    schedule 25.04.2012
comment
Спасибо, Марко. Теперь, с одной сменой, эквивалентна ли производительность x ‹‹ 1 производительности x ‹‹ 16?   -  person Kirby    schedule 25.04.2012
comment
Теперь я вспомнил, что даже на аппаратном уровне процессора есть специальная схема, так называемая barrel-shifter, которая заставляет операцию сдвига выполняться за один такт. Представлен на Intel 80386 в 1987 году. Если вам нужен еще более прямой ответ — да, x << 1 точно такой же, как x << anything else.   -  person Marko Topolnik    schedule 25.04.2012
comment
Все обычные компьютеры имеют операцию многобитового сдвига, которая выполняет сдвиг N битов за одну команду. (На некоторых грубых RISC-процессорах это может занять 2-3 инструкции, но на них требуется 2-3 инструкции.) Длинные смены могут занимать на несколько больше внутренних циклов, чем более короткие смены, но разница вряд ли будет измерима.   -  person Hot Licks    schedule 25.04.2012
comment
@Kirby javap -c YourClass может помочь в следующий раз, когда у вас возникнут сомнения.   -  person soulcheck    schedule 25.04.2012
comment
Спасибо, Марко и Hot Licks. Это именно то, что я хотел знать.   -  person Kirby    schedule 25.04.2012
comment
Отлично, душевно! Я никогда не слышал об этом раньше.   -  person Kirby    schedule 25.04.2012
comment
@soulcheck - javap просто показывает байт-коды, что даже близко не раскрывает фактическую стоимость операции. Некоторые байт-коды преобразуются менее чем в одну машинную инструкцию, другие — в тысячи.   -  person Hot Licks    schedule 25.04.2012
comment
@HotLicks это было предложение к вопросу перед редактированием (почти уверен, что цикл, содержащий что-то + ishl, будет переведен как минимум на то же количество инструкций, что и одиночный ishl)   -  person soulcheck    schedule 25.04.2012
comment
В области оптимизации хорошо знать имя Agner Fog: agner.org/optimize.   -  person DarenW    schedule 21.08.2012


Ответы (4)


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

При использовании версии for loop для каждой итерации цикла проверяется условие завершения цикла, увеличивается i, выполняется побитовая операция и выполняется присвоение x.

При использовании одинарного сдвига выполняется одна побитовая операция и выполняется присвоение x.

И, как уже говорили другие, это действительно похоже на преждевременную оптимизацию.

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

Тем не менее, в зависимости от языка и компилятора, возможно, что компилятор увидит, что ваш for loop всегда выполняется 16 раз, а затем приступит к оптимизации вашего кода, изменив его на x << 16. Если это так, вы не увидите никакой разницы между каждым приведенным вами примером кода.

person Liam George Betsworth    schedule 25.04.2012
comment
Очевидно, это зависит от того, насколько хорошо оптимизирован код. Я вполне мог себе представить, что JIT развернет такой цикл в прямую последовательность смен, которые затем сворачиваются в одну. Дело в том, что вы не можете сказать, сколько времени потребуется для выполнения, глядя на синтаксис на уровне Java. - person aioobe; 25.04.2012
comment
Конечно. Однако с точки зрения базовой логики, без какой-либо оптимизации компилятора или языка, я описал поток инструкций. - person Liam George Betsworth; 25.04.2012
comment
Не то чтобы я не согласен с вашим конечным ответом, но ваша логика не верна, поскольку сдвиг более чем на 1 может логически (но не разумно) быть реализован внутри как цикл одиночных сдвигов. Чтобы привести более очевидный пример, Collection.addAll обычно имеет ту же производительность, что и цикл Collection.add, поскольку сам addAll просто реализует этот цикл. С вашей логикой одна операция логически должна быть быстрее, чем цикл. - person yshavit; 25.04.2012
comment
Я понимаю, откуда вы, но было бы гораздо менее эффективно зацикливать отдельные смены. Я очень сомневаюсь, что в java реализовано смещение битов таким образом. - person Liam George Betsworth; 28.04.2012

...чтобы мне не пришлось тратить время пользователей StackOverflow?

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

Это давно пахнет преждевременной оптимизацией.

Какова точная производительность «x ‹‹ 16»? Это та же скорость, что и "x ‹‹ 1"?

Да, это то же самое. Но с технической точки зрения это на самом деле зависит от компилятора, реализации JVM, JIT, архитектуры ЦП и т. д. Спецификация Java не накладывает никаких ограничений на время выполнения в таких случаях.

person aioobe    schedule 25.04.2012
comment
Если у меня есть возможность сделать что-то быстрее, чем сделать что-то медленнее, почему бы не знать, как сделать это быстрее? - person Kirby; 25.04.2012
comment
@Kirby - есть определенная правильность в изучении некоторых из этих приемов, но в целом, чем короче и прямолинейнее последовательность кода, тем она эффективнее. Ясность и эффективность обычно идут рука об руку (по крайней мере, пока вы не начнете зацикливаться). - person Hot Licks; 25.04.2012
comment
@aioobe, удобочитаемость, безусловно, важна, но для меня важно знать, что на самом деле происходит в приложении. - person Kirby; 25.04.2012
comment
@Hot Licks: Хороший вопрос. Я предполагал, что это так, но я благодарен за объяснения, которые были даны. - person Kirby; 25.04.2012

почему бы не написать простой бенчмарк и не убедиться в этом самостоятельно?

    long start1 = System.nanoTime();
    for (int k = 0; k < 100000000; k++) {
        int x = 5;
        x = x << 16;
    }
    long stop1 = System.nanoTime();

    long start2 = System.nanoTime();
    for (int k = 0; k < 100000000; k++) {
        int x = 5;
        for (int i = 0; i < 16; ++i) {
            x = x << 1;
        }
    }
    long stop2 = System.nanoTime();

    long start3 = System.nanoTime();
    for (int k = 0; k < 100000000; k++) {
        int x = 5;
        for (int i = 0; i < 16; ++i) {
            x = x * 2;
        }
    }
    long stop3 = System.nanoTime();

    System.out.println(stop1 - start1);
    System.out.println(stop2 - start2);
    System.out.println(stop3 - start3);
person meliniak    schedule 25.04.2012
comment
Веская причина не писать простой бенчмарк и не проверять его самостоятельно, заключается в том, что он очень, очень легко получить неправильный микробенчмарк. - person Joachim Sauer; 25.04.2012

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

Вы не должны много думать об этих незначительных вещах «улучшения скорости». Скорость этих небольших арифметических/логических операций огромна, и это не сильно повлияет на производительность программы.

person SmRndGuy    schedule 25.04.2012