Оптимизирует ли компилятор a c/ C++ константное деление по степени двойки на сдвиги?

Question

Вопрос говорит сам за себя. Кто-нибудь знает, если следующее...

size_t div(size_t value) {
    const size_t x = 64;
    return value / x;
}

... оптимизирован в?

size_t div(size_t value) {
    return value >> 6;
}

Компиляторы делают это? (Мой интерес к GCC). Существуют ли ситуации, когда это происходит, а другие - нет?

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

Answer 1

Даже с 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.

Answer 2

Большинство компиляторов пойдут даже дальше, чем уменьшение деления на степени 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 с умножением, парой смен и парой прибавлений.

Для получения более подробной информации о том, что происходит, обратитесь к книге Генри Уоррена "Восторг Хакера" или к веб-странице компаньона:

• http://www.hackersdelight.org/

Есть онлайн добавленная глава, которая предоставляет дополнительную информацию о делении на константы, используя умножение / сдвиг / сложение с магическими числами, и страницу с небольшой программой JavaScript, которая вычислит нужные вам магические числа.

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

Другая статья, которую я обнаружил только что, которая обсуждает эту оптимизацию: http://blogs.msdn.com/devdev/archive/2005/12/12/502980.aspx

Answer 3

Только тогда, когда он может определить, что аргумент является положительным. Это относится к вашему примеру, но с тех пор, как в C99 была задана семантика округления до нуля для целочисленного деления, стало сложнее оптимизировать деление на степени двойки на сдвиги, поскольку они дают разные результаты для отрицательных аргументов.

В ответ на комментарий Майкла ниже, это один из способов разделения r=x/p;из x известной силой двух p действительно может быть переведен компилятором:

if (x<0)
  x += p-1;
r = x >> (log2 p);

Поскольку ОП спрашивал, должен ли он думать об этих вещах, одним из возможных ответов будет "только если вы знаете знак дивиденда лучше, чем компилятор, или знаете, что не имеет значения, округляется ли результат до 0 или -∞".

Answer 4

Да, компиляторы генерируют наиболее оптимальный код для таких упрощенных вычислений. Однако, почему вы настаиваете именно на "сменах", мне не ясно. Оптимальный код для данной платформы может легко оказаться чем-то отличным от "сдвига".

В общем случае старая и забитая до смерти идея о том, что "сдвиг" является каким-то самым оптимальным способом реализации умножения и деления по степеням двух, имеет очень мало практического значения для современных платформ. Это хороший способ проиллюстрировать новичкам концепцию "оптимизации", но не более того.

Ваш исходный пример не является действительно репрезентативным, поскольку он использует тип без знака, что значительно упрощает реализацию операции деления. Требование "округлить до нуля" языков C и C++ делает невозможным деление простым сдвигом, если операнд подписан.