Замена деления умножением на Ассемблере

При написании на Ассемблере алгоритмов, использующих деление на константу, операции деления можно заменять на операции умножения. Зачем это надо? Дело в том, что процессор выполняет операцию умножения в несколько раз быстрее, чем операцию деления. К примеру, на умножение тратится 5-9 тактов процессора (знаковое умножение) или 4-8 (беззнаковое умножение), тогда как для деления необходимо 22-47 тактов (знаковое деление) или 17-41 тактов (беззнаковое деление). В высокооптимизированных алгоритмах, таких как шифрование, математические расчеты, архивация больших объемов данных, подсчет контрольных сумм и других подобных задачах, экономия каждого такта процессора может дать значительный прирост общей скорости работы программы.

В руководстве по оптимизации "AMD Athlon Processor x86 Code Optimization Guide" вопрос замены деления умножением расписан очень подробно. Рассмотрены частные случаи деления, такие как деление на степень двойки, описан выбор алгоритма для знакового и беззнакового деления и приведен код для вычисления вспомогательных корректирующих значений. Кроме этого, в руководстве описаны методы оптимизации и других математических операций. Даже если вы никогда не будете использовать на практике замену деления умножением, почитать о других способах оптимизации будет очень полезно.

Сперва рассмотрим оптимизацию беззнакового целочисленного деления. Здесь есть несколько вариантов в зависимости от значений делителя. Первый вариант - если делитель находится в диапазоне от 1 до (231 - 1):

; В описании используются следующие вспомогательные значения:
; m = множитель (multiplier)
; s = коэффициент смещения (shift factor)
 
;-----------------------------------------------------
; Алгоритм №0
;-----------------------------------------------------
        mov     eax, m
        mul     делитель
        shr     edx, s
        ; EDX = частное
 
;-----------------------------------------------------
; Алгоритм №1
;-----------------------------------------------------
        mov     eax, m
        mul     делитель
        add     eax, m
        adc     edx, 0
        shr     edx, s
        ; EDX = частное

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

Второй вариант беззнакового деления - когда делитель находится в интервале от 231 до (232 - 1). В этом случае частное может принимать только два значения - 0 или 1. Соответственно, оптимизированный алгоритм будет иметь следующий вид:

        ; EAX = делимое
        xor     edx, edx
        cmp     eax, делитель ; CF = (делимое < делитель) ? 1 : 0
        sbb     edx, -1 ; частное = 0+1-CF = (делимое < делитель) ? 0 : 1
        ; EDX = частное

В случае, если значение делимого неважно для дальнейших расчетов, этот вариант можно еще немного оптимизировать, отказавшись от использования дополнительного регистра:

        ; EAX = делимое
        cmp     eax, делитель ; CF = (делимое < делитель) ? 1 : 0
        mov     eax, 0
        sbb     eax, -1 ; частное = 0+1-CF = (делимое < делитель) ? 0 : 1
        ; EAX = частное

В мануале, кстати, в этом месте допущена опечатка. В тексте рассказывается об избавлении от второго регистра, и тут же приводится неработающий код с этим же регистром (страница 117, если интересно). Копипаст не всегда бывает полезным. Там же в мануале рекомендуется использовать вариант с дополнительным регистром, хотя лично я какой-то принципиальной разницы в этом не вижу. Те же яйца, только сбоку.

На всякий случай напомню частные случаи беззнакового целочисленного деления. На ноль натуральные числа делить нельзя, это без вариантов, так что и про оптимизацию тут речи быть не может. При делении на единицу частное всегда равно делимому, это вы тоже должны помнить еще со школьной скамьи. Деление на степень двойки в Ассемблере оптимизируется с использованием команды битового сдвига вправо SHR reg, степень_двойки:

        ; EAX = делимое
        shr     eax,1    ; EAX / 2
        shr     eax,2    ; EAX / 4
        shr     eax,3    ; EAX / 8
        shr     eax,4    ; EAX / 16
        ; и так далее

Под это же правило, в принципе, можно притянуть и деление на единицу, так как 20 = 1.

        ; EAX = делимое
        shr     eax,0    ; EAX / 1
        ; EAX остался неизменным

Целочисленное знаковое деление немного сложнее, так как при получении результата приходится учитывать знак делимого и делителя. Приведенные ниже алгоритмы работают только с положительными значениями делителя. Если делитель отрицательный, то сперва вычисляется его модуль, который и используется в дальнейших расчетах, а к полученному результату деления применяется ассемблерная команда NEG. Это следует из математической аксиомы n/-d = -(n/d). Целочисленный делитель должен находиться в диапазоне от 2 до (231 - 1).

; В описании используются следующие вспомогательные значения:
; m = множитель (multiplier)
; s = коэффициент смещения (shift factor)
 
;-----------------------------------------------------
; Алгоритм №0
;-----------------------------------------------------
        mov     eax, m
        imul    делитель
        mov     eax, делитель
        shr     eax, 31
        sar     edx, s
        add     edx, eax
        ; EDX = частное
 
;-----------------------------------------------------
; Алгоритм №1
;-----------------------------------------------------
        mov     eax, m
        imul    делитель
        mov     eax, делитель
        add     edx, eax
        shr     eax, 31
        shr     eax, s
        add     edx, eax
        ; EDX = частное

Как и в беззнаковом делении, тип алгоритма, множитель и коэффициент смещения вычисляются на основании значения делителя, а точнее его модуля. Исходник на C есть в мануале.

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

;-----------------------------------------------------
; Знаковое деление на 2
;-----------------------------------------------------
        ; EAX = делимое
        cmp     eax, 800000000h
        sbb     eax, –1
        sar     eax, 1
        ; EAX = частное
 
;-----------------------------------------------------
; Знаковое деление на 2^n
;-----------------------------------------------------
        ; EAX = делимое
        cdq
        and     edx, (2^n–1)
        add     eax, edx
        sar     eax, n
        ; EAX = частное
 
;-----------------------------------------------------
; Знаковое деление на -2
;-----------------------------------------------------
        ; EAX = делимое
        cmp     eax, 800000000h
        sbb     eax, –1
        sar     eax, 1
        neg     eax
        ; EAX = частное
 
;-----------------------------------------------------
; Знаковое деление на -(2^n)
;-----------------------------------------------------
        ; EAX = делимое
        cdq
        and     edx, (2^n–1)
        add     eax, edx
        sar     eax, n
        neg     eax
        ; EAX = частное

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

Добавлено: 12 Сентября 2013 11:29:22 Добавил: Андрей Ковальчук Нравится 0

Добавить