Добавить против мул (IA32-Assembly)
Я знаю, что добавить быстрее по сравнению с многофункциональным.
Я хочу знать, как использовать add вместо mul в следующем коде, чтобы сделать его более эффективным.
Образец кода:
mov eax, [ebp + 8] #eax = x1
mov ecx, [ebp + 12] #ecx = x2
mov edx, [ebp + 16] #edx = y1
mov ebx, [ebp + 20] #ebx = y2
sub eax,ecx #eax = x1-x2
sub edx,ebx #edx = y1-y2
mul edx #eax = (x1-x2)*(y1-y2)
5 ответов
add быстрее, чем mul, но если вы хотите умножить два общих значения, mul гораздо быстрее, чем любой цикл, выполняющий операции add.
Вы не можете серьезно использовать add, чтобы заставить этот код работать быстрее, чем с mul. Если вам нужно умножить на некоторое небольшое постоянное значение (например, 2), то, возможно, вы могли бы использовать add, чтобы ускорить процесс. Но для общего случая - нет.
Если вы умножаете два значения, которые вы не знаете заранее, фактически невозможно превзойти инструкцию умножения в ассемблере x86.
Если вы заранее знаете значение одного из операндов, вы можете превзойти инструкцию умножения, используя небольшое количество добавлений. Это особенно хорошо работает, когда известный операнд мал и имеет только несколько битов в двоичном представлении. Чтобы умножить неизвестное значение x на известное значение, состоящее из 2^p+2^q+...2^r, вы просто добавляете x*2^p+x*2^q+..x*2*r, если биты p,q, ... и r установлены. Это легко достигается в ассемблере путем сдвига влево и добавления:
; x in EDX
; product to EAX
xor eax,eax
shl edx,r ; x*2^r
add eax,edx
shl edx,q-r ; x*2^q
add eax,edx
shl edx,p-q ; x*2^p
add eax,edx
Основная проблема заключается в том, что для этого требуется не менее 4 часов, при условии, что суперскалярный процессор ограничен зависимостями регистров. Умножение обычно занимает 10 или меньше тактов на современных процессорах, и если эта последовательность становится длиннее, чем во времени, вы могли бы также сделать умножение.
Умножить на 9:
mov eax,edx ; same effect as xor eax,eax/shl edx 1/add eax,edx
shl edx,3 ; x*2^3
add eax,edx
Это бьет умножение; должно занять всего 2 часа.
Что менее известно, так это использование инструкции LEA (эффективный адрес загрузки) для быстрого умножения на маленькую константу. LEA, который занимает только один такт в худшем случае, его время выполнения часто может перекрываться с другими инструкциями суперскалярных процессоров.
LEA, по сути, "добавляет два значения с небольшими постоянными множителями". Он вычисляет t=2^k*x+y для k=1,2,3 (см. Справочное руководство Intel) для t, x и y - любой регистр. Если x==y, вы можете получить 1,2,3,4,5,8,9 раз x, но использование x и y в качестве отдельных регистров позволяет комбинировать промежуточные результатыи перемещать их в другие регистры (например, в t), и это оказывается удивительно удобным. Используя его, вы можете выполнить умножение на 9, используя одну инструкцию:
lea eax,[edx*8+edx] ; takes 1 clock
Тщательно используя LEA, вы можете умножить на множество своеобразных констант за небольшое количество циклов:
lea eax,[edx*4+edx] ; 5 * edx
lea eax,[eax*2+edx] ; 11 * edx
lea eax,[eax*4] ; 44 * edx
Чтобы сделать это, вы должны разложить ваш постоянный множитель на различные факторы / суммы, включающие 1,2,3,4,5,8 и 9. Примечательно, сколько маленьких констант вы можете сделать это, и все еще использовать только 3-4 инструкции.
Если вы разрешаете использовать другие обычно одночасовые инструкции (например, SHL/SUB/NEG/MOV), вы можете умножить на некоторые постоянные значения, которые чистый LEA не может сделать так же эффективно сам по себе. Умножить на 31:
lea eax,[4*edx]
lea eax,[8*eax] ; 32*edx
sub eax,edx; 31*edx ; 3 clocks
Соответствующая последовательность LEA длиннее:
lea eax,[edx*4+edx]
lea eax,[edx*2+eax] ; eax*7
lea eax,[eax*2+edx] ; eax*15
lea eax,[eax*2+edx] ; eax*31 ; 4 clocks
Выяснить эти последовательности немного сложно, но вы можете организовать организованную атаку.
Поскольку LEA, SHL, SUB, NEG, MOV - это наихудший случай однократных команд и нулевые часы, если они не зависят от других команд, вы можете рассчитать стоимость выполнения любой такой последовательности. Это означает, что вы можете реализовать алгоритм динамического программирования для генерации наилучшей возможной последовательности таких инструкций. Это полезно только в том случае, если счетчик тактов меньше целочисленного умножения для вашего конкретного процессора (я использую 5 часов в качестве практического правила), и он не использует все регистры или, по крайней мере, не использует регистры которые уже заняты (избегая любых разливов).
Я фактически встроил это в наш компилятор PARLANSE, и он очень эффективен для вычисления смещений в массивах структур A[i], где размер элемента структуры в A является известной константой. Умный человек, возможно, кеширует ответ, поэтому его не нужно пересчитывать каждый раз, когда происходит умножение одной и той же константы; На самом деле я этого не делал, потому что время генерации таких последовательностей меньше, чем вы ожидаете.
Мягко интересно напечатать последовательности команд, необходимые для умножения на все константы от 1 до 10000. Большинство из них можно выполнить в 5-6 инструкциях в худшем случае. Как следствие, компилятор PARLANSE вряд ли когда-либо использует фактическое умножение при индексации даже самых неприятных массивов вложенных структур.
Если ваши умножения не являются достаточно упрощенными, add скорее всего, не выиграют mul, Сказав это, вы можете использовать add делать умножения:
Multiply by 2:
add eax,eax ; x2
Multiply by 4:
add eax,eax ; x2
add eax,eax ; x4
Multiply by 8:
add eax,eax ; x2
add eax,eax ; x4
add eax,eax ; x8
Они хорошо работают на двоих. Я не говорю, что они быстрее. Они, безусловно, были необходимы в дни, предшествовавшие сложным инструкциям умножения. Это от кого-то, чья душа была выкована в адских пожарах, таких как Mostek 6502, Zilog z80 и RCA1802:-)
Вы можете даже умножить на не-полномочия, просто сохранив промежуточные результаты:
Multiply by 9:
push ebx ; preserve
push eax ; save for later
add eax,eax ; x2
add eax,eax ; x4
add eax,eax ; x8
pop ebx ; get original eax into ebx
add eax,ebx ; x9
pop ebx ; recover original ebx
Я обычно советую писать код в первую очередь для удобства чтения и беспокоиться о производительности только тогда, когда вам это нужно. Однако, если вы работаете в ассемблере, вы, возможно, уже в этот момент. Но я не уверен, что мое "решение" действительно применимо к вашей ситуации, поскольку у вас есть произвольный множитель.
Однако вы всегда должны профилировать свой код в целевой среде, чтобы гарантировать, что то, что вы делаете , действительно быстрее. Ассемблер не меняет этот аспект оптимизации вообще.
Если вы действительно хотите увидеть более универсальный ассемблер для использования add чтобы сделать умножение, вот процедура, которая примет два значения без знака в ax а также bx и вернуть товар в ax, Он не справится с переполнением элегантно.
START: MOV AX, 0007 ; Load up registers
MOV BX, 0005
CALL MULT ; Call multiply function.
HLT ; Stop.
MULT: PUSH BX ; Preserve BX, CX, DX.
PUSH CX
PUSH DX
XOR CX,CX ; CX is the accumulator.
CMP BX, 0 ; If multiplying by zero, just stop.
JZ FIN
MORE: PUSH BX ; Xfer BX to DX for bit check.
POP DX
AND DX, 0001 ; Is lowest bit 1?
JZ NOADD ; No, do not add.
ADD CX,AX
NOADD: SHL AX,1 ; Shift AX left (double).
SHR BX,1 ; Shift BX right (integer halve, next bit).
JNZ MORE ; Keep going until no more bits in BX.
FIN: PUSH CX ; Xfer product from CX to AX.
POP AX
POP DX ; Restore registers and return.
POP CX
POP BX
RET
Это опирается на тот факт, что 123 умножается на 456 идентичен:
123 x 6
+ 1230 x 5
+ 12300 x 4
это так же, как вас учили умножению еще в классе / начальной школе. Это проще с двоичным, так как вы умножаете только на ноль или единицу (другими словами, добавление или не добавление).
Это довольно старая школа x86 (8086, из сессии DEBUG - я не могу поверить, что они все еще включают эту штуку в XP), так как это было в последний раз, когда я программировал непосредственно на ассемблере. Есть что-то, что можно сказать о языках высокого уровня:-)
Когда дело доходит до инструкции по сборке, скорость выполнения любой инструкции измеряется с использованием тактового цикла. Инструкция Mul всегда занимает больше тактов, чем операция добавления, но если вы выполняете ту же самую инструкцию добавления в цикле, то общий тактовый цикл для умножения с использованием инструкции добавления будет намного больше, чем одиночной инструкции mul. Вы можете взглянуть на следующий URL, который говорит о тактовом цикле одиночной инструкции add / mul. Таким образом, вы можете выполнять математику, которая будет быстрее.
http://home.comcast.net/~fbui/intel_a.html
http://home.comcast.net/~fbui/intel_m.html
Я рекомендую использовать инструкцию mul вместо того, чтобы помещать add в цикл, позднее это очень неэффективное решение.
Я должен повторить ответы, которые у вас уже есть - для общего умножения вам лучше всего использовать MUL - в конце концов, это то, что он там!
В некоторых конкретных случаях, когда вы знаете, что вам захочется умножаться на определенное фиксированное значение каждый раз (например, при разработке индекса пикселя в растровом изображении), вы можете рассмотреть возможность разбить умножение на (маленькую) горстку SHL и ADDs - например:
Дисплей 1280 x 1024 - каждая строка на дисплее имеет 1280 пикселей.
1280 = 1024 + 256 = 2 ^ 10 + 2 ^ 8
y * 1280 = y * (2 ^ 10) + y * (2 ^ 8) = ДОБАВИТЬ (SHL y, 10), (SHL y, 8)
... учитывая, что графическая обработка, вероятно, должна быть быстрой, такой подход может сэкономить вам драгоценные такты.