Умножить-добавить инструкцию `a = a * 2 + b` на CPU?

Классическая операция умножения-накопления - a = a + b*c. Но в настоящее время мне интересно, существует ли инструкция, которая позволяет выполнять следующие операции с целыми числами за 1 такт: (a и b - 64-битные целые числа без знака: unsigned long long int)

a = a*2-1
a = a*2+b

В настоящее время я использую:

a *= 2
--a

для первого и

a *= 2
a += b

для второго. И я думаю, что каждая из них переведена на 2 инструкции в ASM. Но есть ли способ вместо этого использовать 1 инструкцию ASM (и с каким расширением набора инструкций на процессоре Intel)?

(Я ищу это, потому что проделываю эту операцию миллиарды раз)


c x86 multiplication assembly fma
person Vincent    schedule 11.02.2012    source источник
comment
Почему имеет значение, сколько инструкций генерирует компилятор? Это будет только слабо связано с количеством тактовых циклов, которые требуется для вычисления?   -  person CB Bailey    schedule 11.02.2012
comment
@KerrekSB, Вы правы - lea может делать a*2+b, если b между 0 и 4096, или он у вас в реестре.   -  person ugoren    schedule 11.02.2012
comment
@Vincent - Текущие процессоры могут выполнять несколько простых инструкций за каждый такт. Удаление одного не гарантирует, что следующая инструкция восполнит пробел. Вам действительно нужен компилятор, чтобы вести бухгалтерию!   -  person Bo Persson    schedule 11.02.2012

Ответы (2)


arrow_upward
7
arrow_downward

  1. Для ЦП Intel см. LEA инструкцию. Он может выполнять обе ваши задачи в одной инструкции (хотя и не уверен в циклах) каждая. (например, LEA EAX, [EAX*2+EBX]). Обратите внимание, что на самом деле это не означало, что это умножение-сложение, отсюда и его забавное название (эффективный адрес загрузки).

  2. В C и C ++ вам не о чем беспокоиться. Компилятор будет делать то, что считает лучшим, и вы, вероятно, можете просто помешать его усилиям. Я бы остался со старым добрым a = a*2-1.

PS: Если вы думаете, что что-то переведено как две инструкции, нет ничего проще, чем посмотреть в сборке. Тогда вы бы знали.

person jpalecek    schedule 11.02.2012
comment
Соглашаться. Когда-то давно LEA был свободен, потому что у ЦП были выделенные блоки вычисления адресов, которые бездействовали, когда не использовались. Не верно для нынешних поколений, где он, вероятно, будет генерировать те же микрооперации, что и отдельные смены и добавления. - person Bo Persson; 11.02.2012
comment
lea eax, [eax*2 + ebx] - задержка в 1 цикл на процессорах Intel (масштабируемый индекс не делает его сложным LEA). Но на процессорах AMD масштабированный индекс делает его сложным LEA, поэтому он имеет задержку в 2 цикла. Тем не менее, все еще только 1 муп. agner.org/optimize. @BoPersson: LEA очень распространен, и его стоит использовать, потому что он не микрокодирован. Это одинарный сдвиг и добавление. Но да, он работает на исполнительных модулях ALU, а не на AGU. Простые LEA имеют 2 пропускной способности на такт в семействе Intel SnB по сравнению с 1 на такт для сложных LEA. Intel следующего поколения будет иметь блоки LEA на всех 4 портах ALU. - person Peter Cordes; 06.04.2019

arrow_upward
1
arrow_downward

Существует множество архитектур, которые могут выполнять такие операции в одной инструкции. Например, a*2 + b компилируется в

  • lea eax, [rsi+rdi*2] on x86-64
  • add r0, r1, r0, lsl #1 на ARM
  • add w0, w1, w0, lsl 1 на ARM64
  • lda16 r0, r1[r0] на xcore

Компилятор соответствующим образом оптимизирует выражение. Нет причин делать такие вещи, как a *= 2; a += b, что во многих случаях снижает удобочитаемость.

Вы можете увидеть демо на Компилятор Проводник

Однако если вы спросите об этом только потому, что выполняете эту операцию миллиарды раз, то это, по сути, проблема XY, потому что изменение версии C - неправильный способ, а сокращение количества инструкций - это не то, как вы сокращаете время выполнения. Вы не измеряете производительность по количеству инструкций

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

Например, Clang выдает следующие инструкции в основном цикле для AVX-512

vpaddd  zmm0, zmm0, zmm0                            ; a *= 2
vpaddd  zmm1, zmm1, zmm1
vpaddd  zmm2, zmm2, zmm2
vpaddd  zmm3, zmm3, zmm3
vpaddd  zmm0, zmm0, zmmword ptr [rsi + 4*rdx]       ; a += b
vpaddd  zmm1, zmm1, zmmword ptr [rsi + 4*rdx + 64]
vpaddd  zmm2, zmm2, zmmword ptr [rsi + 4*rdx + 128]
vpaddd  zmm3, zmm3, zmmword ptr [rsi + 4*rdx + 192]

который включает как разворачивание цикла, так и автоматическая векторизация. Каждая инструкция может работать одновременно с шестнадцатью 32-битными целыми числами. Конечно, если вы используете 64-битную int, тогда она может работать "только" с 8 за раз. Кроме того, каждая из тех же инструкций может выполняться независимо от других, поэтому, если у ЦП достаточно портов выполнения, он может добавить 64 int параллельно. Вот что мы называем "быстрым"

GCC часто менее агрессивен при развертывании цикла и использует vpslld, за которым следует vpaddd. Но это все равно быстрее, чем скалярная версия. На ARM с неоном видно, что используется shl v0.4s, v0.4s, 1; add v0.4s, v0.4s, v1.4s. Вот Compiler Проводник демо ссылка

В сочетании с многопоточностью это намного быстрее, чем ваша "оптимизация"

person phuclv    schedule 05.04.2019