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

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

1 голос
/ 11 февраля 2012

Классическая операция Multiply-Accumulate - 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)?

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

Ответы [ 2 ]

7 голосов
/ 11 февраля 2012

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

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

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

1 голос
/ 05 апреля 2019

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

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

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

Демонстрацию можно увидеть на Compiler Explorer

Однако, если вы спросите об этом только потому, чтоВы выполняете эту операцию миллиарды раз , тогда это, по сути, проблема 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 Explorer

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

...