Оптимизируют ли современные компиляторы операцию x * 2 до x << 1?

Question

Оптимизирует ли компилятор C ++ умножение на две операции x*2 до операции битового сдвига x<<1?

Я бы хотел верить, что да.

Answer 1

На самом деле VS2008 оптимизирует это до х + х:

01391000  push        ecx  
    int x = 0;

    scanf("%d", &x);
01391001  lea         eax,[esp] 
01391004  push        eax  
01391005  push        offset string "%d" (13920F4h) 
0139100A  mov         dword ptr [esp+8],0 
01391012  call        dword ptr [__imp__scanf (13920A4h)] 

    int y = x * 2;
01391018  mov         ecx,dword ptr [esp+8] 
0139101C  lea         edx,[ecx+ecx] 

В сборке x64 он еще более явный и использует:

    int y = x * 2;
000000013FB9101E  mov         edx,dword ptr [x] 

    printf("%d", y);
000000013FB91022  lea         rcx,[string "%d" (13FB921B0h)] 
000000013FB91029  add         edx,edx 

Это будут настройки оптимизации на «Максимизировать скорость» (/ O2)

Answer 2

Эта статья от Рэймонда Чена может быть интересной:

Когда x / 2 отличается от x >> 1? : http://blogs.msdn.com/oldnewthing/archive/2005/05/27/422551.aspx

Цитата Рэймонда:

Конечно, компилятор может распознать это и переписать вашу операцию умножения или сдвига. На самом деле, это очень вероятно, потому что x + x более легко выплачиваем, чем умножение или сдвиг. Ваш сдвиг или умножение на два, вероятно, будет переписано как нечто более близкое к инструкции add eax, eax.

[...]

Даже если вы предполагаете, что сдвиг заполняется знаковым битом, результат сдвига и деления будут разными, если x отрицателен.

(- 1) / 2 ≡ 0
(-1) >> 1 ≡ -1

[...]

Мораль этой истории - написать, что вы имеете в виду. Если вы хотите разделить на два, напишите «/ 2», а не «>> 1».

Мы можем только предполагать, что разумно указывать компилятору, что вы хотите, а не то, что вы хотите, чтобы он делал: Компилятор лучше, чем человек, оптимизирует мелкомасштабный код (спасибо за то, что Дэмин укажите этот тонкий момент): если вы действительно хотите оптимизировать, используйте профилировщик и изучите эффективность ваших алгоритмов.

Answer 3

VS 2008 оптимизированная шахта до х << 1. </p>

    x = x * 2;
004013E7  mov         eax,dword ptr [x] 
004013EA  shl         eax,1 
004013EC  mov         dword ptr [x],eax 

EDIT: при этом использовалась конфигурация "Debug" VS по умолчанию с отключенной оптимизацией (/ Od). Использование любого из переключателей оптимизации (/ O1, / O2 (VS "Retail") или / Ox) приводит к добавлению Роба добавленного кода собственной личности. Кроме того, просто для примера, я убедился, что x = x << 1 действительно обрабатывается так же, как и x = x * 2 компилятором cl в / Od и / Ox. Итак, в итоге, cl.exe версии 15.00.30729.01 для x86 одинаково обрабатывает * 2 и << 1, и я ожидаю, что почти все другие последние компиляторы делают то же самое.

Answer 4

Нет, если x это число с плавающей точкой, оно не будет.

Answer 5

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

Answer 6

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

Answer 7

Это только начало того, что могут сделать оптимизаторы. Чтобы увидеть, что делает ваш компилятор, найдите ключ, который заставляет его испускать ассемблерный источник. Для компиляторов Digital Mars выходной ассемблер можно проверить с помощью инструмента OBJ2ASM. Если вы хотите узнать, как работает ваш компилятор, просмотр вывода ассемблера может быть очень полезным.

Answer 8

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

Answer 9

Почему вы думаете, что это оптимизация?

Почему бы не 2*x → x+x? Или, может быть, операция умножения выполняется так же быстро, как и операция левого сдвига (может быть, только если в множителе установлен только один бит)? Если вы никогда не используете результат, почему бы не исключить его из скомпилированного вывода? Если компилятор уже загрузил 2 в некоторый регистр, возможно, инструкция умножения будет быстрее, например если бы нам сначала нужно было загрузить счетчик смен. Может быть, операция сдвига больше, и ваш внутренний цикл больше не помещается в буфер предварительной выборки ЦП, что снижает производительность? Может быть, компилятор может доказать, что единственный раз, когда вы вызываете вашу функцию x, будет иметь значение 37 и x*2 может быть заменено на 74? Может быть, вы делаете 2*x, где x - это число циклов (очень распространенное, хотя и неявное при циклическом выполнении двухбайтовых объектов)? Тогда компилятор может изменить цикл с

    for(int x = 0; x < count; ++x) ...2*x...

к эквиваленту (без учета патологий)

    int count2 = count * 2
    for(int x = 0; x < count2; x += 2) ...x...

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

Моя точка зрения : миллионы факторов решают, даст ли замена x*2 на x<<1 более быстрый двоичный файл. Оптимизирующий компилятор попытается сгенерировать самый быстрый код для данной программы, а не для изолированной операции. Поэтому результаты оптимизации для одного и того же кода могут в значительной степени различаться в зависимости от окружающего кода, и они могут быть совсем не тривиальными.

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

Answer 10

@ Ферруччо Барлетта

Это хороший вопрос. Я пошел поискать в Google, чтобы попытаться найти ответ.

Я не смог найти ответы для процессоров Intel напрямую, но на этой странице есть кто-то, кто пытался рассчитать время. Показывает, что сдвиги будут более чем в два раза быстрее, чем реклама и умножается. Сдвиги битов настолько просты (где умножение может быть сдвигом и сложением), что это имеет смысл.

Итак, я прогуглил AMD и нашел старое руководство по оптимизации для Athlon 2002 года, в котором перечислены самые быстрые способы умножения чисел на константы между 2 и 32. Интересно, что это зависит от числа. Некоторые из них являются рекламой, некоторые смены. Это на странице 122 .

Руководство для Athlon 64 показывает то же самое (стр. 164 или около того). В нем говорится, что умножение - это 3 (в 32-разрядном) или 4 (в 64-разрядном) циклические операции, где сдвиги равны 1, а сложения - 2.

Кажется, это все еще полезно в качестве оптимизации.

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

Но это предположение.