C/c ++ компилятор оптимизируют постоянные подразделения значением power-two в сдвиги?
Вопрос говорит все это. Делает любой знает если следующее...
size_t div(size_t value) {
const size_t x = 64;
return value / x;
}
... оптимизирован в?
size_t div(size_t value) {
return value >> 6;
}
Компиляторы делают это? (Мой интерес заключается в GCC). Есть ли ситуации, где это делает и другие, где это не делает?
Я действительно хотел бы знать, потому что каждый раз я пишу подразделение, которое могло быть оптимизировано как это, я трачу некоторую умственную энергию, задающуюся вопросом о том, потрачены ли драгоценные мелочи секунды впустую, делая подразделение, где сдвиг был бы достаточен.
4 ответа
Даже с g++ -O0 (да, -O0!), это происходит. Ваша функция компилируется так:
_Z3divm:
.LFB952:
pushq %rbp
.LCFI0:
movq %rsp, %rbp
.LCFI1:
movq %rdi, -24(%rbp)
movq $64, -8(%rbp)
movq -24(%rbp), %rax
shrq $6, %rax
leave
ret
Обратите внимание на shrq $6, что является сдвигом вправо на 6 мест.
С помощью -O1 ненужный мусор удаляется:
_Z3divm:
.LFB1023:
movq %rdi, %rax
shrq $6, %rax
ret
Результаты на g++ 4.3.3, x64.
Только когда он может определить, что аргумент положительный. Это случай вашего примера, но с тех пор, как C99 определил семантику округления к нулю для целочисленного деления, стало сложнее оптимизировать деление по степеням двойки на сдвиги, потому что они дают разные результаты для отрицательных аргументов.
В ответ на комментарий Майкла ниже, вот один из способов деления r = x / p; x известной степенью двойки p может действительно может быть переведен компилятором:
if (x<0)
x += p-1;
r = x >> (log2 p);
Поскольку ОП спрашивал, следует ли ему думать об этих вещах, одним из возможных ответов было бы «только если вы знаете знак делимого лучше, чем компилятор, или знаете, что не имеет значения, если результат округляется в сторону 0 или -∞ ».
Большинство компиляторов пойдут даже дальше, чем сокращение деления на степени 2 на сдвиги - они часто преобразуют целочисленное деление на константу в серию инструкций умножения, сдвига и сложения для получения результата вместо использования встроенных в ЦП -в инструкции деления (если она вообще есть).
Например, MSVC преобразует деление на 71 в следующее:
// volatile int y = x / 71;
8b 0c 24 mov ecx, DWORD PTR _x$[esp+8] ; load x into ecx
b8 49 b4 c2 e6 mov eax, -423447479 ; magic happens starting here...
f7 e9 imul ecx ; edx:eax = x * 0xe6c2b449
03 d1 add edx, ecx ; edx = x + edx
c1 fa 06 sar edx, 6 ; edx >>= 6 (with sign fill)
8b c2 mov eax, edx ; eax = edx
c1 e8 1f shr eax, 31 ; eax >>= 31 (no sign fill)
03 c2 add eax, edx ; eax += edx
89 04 24 mov DWORD PTR _y$[esp+8], eax
Итак, вы получаете деление на 71 с умножением, сдвигом на пару и сложением пары.
Для получения более подробной информации о том, что происходит, обратитесь к книге Генри Уоррена "Hacker's Delight" или на сопутствующей веб-странице:
Там есть онлайн-добавленная глава ], которая предоставляет некоторую дополнительную информацию о делении на константы с использованием умножения / сдвига / сложения с магическими числами, и страницу с небольшой программой JavaScript , которая вычислит нужные вам магические числа.
Стоит прочитать сопутствующий сайт книги (как и саму книгу), особенно если вас интересуют микрооптимизации на битовом уровне.
Другая статья, которую я только что обнаружил, обсуждает эту оптимизацию: http://blogs.msdn.com/dev/archive/2005/12/12/502980.aspx
Да, компиляторы генерируют наиболее оптимальный код для таких упрощенных вычислений. Однако мне непонятно, почему вы настаиваете именно на «сменах». Оптимальный код для данной платформы легко может оказаться чем-то отличным от «сдвига».
В общем случае старая и забитая до смерти идея о том, что «сдвиг» является каким-то образом наиболее оптимальным способом реализации умножения и деления по степени двойки, имеет очень мало практического значения на современных платформах. Это хороший способ проиллюстрировать концепцию «оптимизации» новичкам, но не более того.
Ваш исходный пример не совсем репрезентативен, потому что он использует беззнаковый тип, что значительно упрощает реализацию операции деления.Требование «округления к нулю» языков C и C ++ делает невозможным деление простым сдвигом, если операнд подписан.