x86_64: IMUL быстрее, чем 2x SHL + 2x ADD?

Question

При взгляде на сборку, произведенную Visual Studio (2015U2) в /O2 (выпуск) режима Я видел, что этот "оптимизированный вручную" фрагмент кода C переводится обратно в умножение:

int64_t calc(int64_t a) {
  return (a << 6) + (a << 16) - a;
}

Монтаж:

  imul        rdx,qword ptr [a],1003Fh  

Поэтому мне было интересно, если это действительно быстрее, чем делать так, как написано, что-то вроде:

  mov         rbx,qword ptr [a]  
  mov         rax,rbx  
  shl         rax,6  
  mov         rcx,rbx  
  shl         rcx,10h  
  add         rax,rcx  
  sub         rax,rbx  

У меня всегда было впечатление, что умножение всегда медленнее, чем несколько смен / добавок? Разве это больше не относится к современным процессорам Intel x86_64?

Answer 1

Это верно, современные процессоры x86 (особенно Intel) имеют очень высокие множители производительности.
imul r, r/m а также imul r, r/m, imm оба имеют задержку 3 цикла, по одному на пропускную способность 1c в семействе Intel SnB и AMD Ryzen, даже для размера 64-битных операндов.

В семействе AMD Bulldozer это задержка 4c или 6c и одна на 2c или одна на 4c пропускную способность. (Более медленное время для размера 64-битных операндов).

Данные из таблиц инструкций Агнера Фога. Смотрите также другие вещи в теге x86 вики.

---

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

Ограничение бюджета мощности, а не бюджета транзистора означает, что использование выделенного оборудования для множества различных функций возможно, если они не могут переключаться одновременно ( https://en.wikipedia.org/wiki/Dark_silicon). например, вы не можете насытить pext/pdep единица измерения, целочисленный множитель и векторные модули FMA одновременно на процессоре Intel, поскольку многие из них находятся на одних и тех же портах исполнения.

Интересный факт: imul r64 также 3c, так что вы можете получить полный результат умножения 64*64 => 128b за 3 цикла. imul r32 задержка 4с и дополнительный моп, хотя. Я предполагаю, что дополнительный цикл uop / цикл разбивает 64-битный результат из обычного 64-битного умножителя на две 32-битные половины.

---

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

gcc и clang3.8 и позже используют до двух LEA инструкции вместо imul r, r/m, imm, Я думаю, что GCC будет использовать imul если альтернатива 3 или более инструкции (не включая mov), хоть.

Это разумный вариант настройки, так как цепочка депиляции из 3 команд будет такой же длины, что и imul на интеле. Использование двух инструкций по 1 циклу тратит дополнительный моп, чтобы сократить задержку на 1 цикл.

clang3.7 и ранее имеет тенденцию в пользу imul за исключением множителей, которые требуют только одного LEA или смены. Таким образом, clang совсем недавно переключился на оптимизацию для задержки вместо пропускной способности для умножения на маленькие константы. (Или может быть по другим причинам, например, не конкурировать с другими вещами, которые находятся только на том же порту, что и множитель.)

например, этот код в проводнике компилятора Godbolt:

int foo (int a) { return a * 63; }
    # gcc 6.1 -O3 -march=haswell (and clang actually does the same here)
    mov     eax, edi  # tmp91, a
    sal     eax, 6    # tmp91,
    sub     eax, edi  # tmp92, a
    ret

clang3.8 и позже делает тот же код.