Оптимизирует ли компилятор 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 ++ делает невозможным деление простым сдвигом, если операнд подписан.