Форум программистов, компьютерный форум, киберфорум
Наши страницы

Оптимизация кода: обходимся без ветвлений

Войти
Регистрация
Восстановить пароль
Оценить эту запись

Оптимизация кода: обходимся без ветвлений

Запись от Jin X размещена 05.02.2018 в 15:43
Обновил(-а) Jin X 06.02.2018 в 14:29

Оптимизация кода: обходимся без ветвлений

Думаю, ни для кого не секрет, что использование условных переходов (инструкций jcc в ассемблере; конструкций if, while, case, for в языках высокого уровня), т.е. ветвлений, могут значительно снизить скорость работы функций. Несмотря на наличие "умной" системы предсказания переходов в современных процессорах, эта система нередко ошибается. Доказательством тому служит тот факт, что один условный переход порой способен затормозить на десятки процентов код из полсотни строк. "Высокая цена" ветвлений привела сначала к появлению инструкций setcc в процессорах 386, а затем и cmovcc в P6, что позволило ощутимо ускорить некоторые участки кода. Однако есть довольно много мини-алгоритмов, позволяющих обойтись не только без ветвлений, но и без этих инструкций. Несмотря на то, что такие блоки кода оказываются более длинными, работают они, как правило, значительно быстрее, чем короткие, но с условными переходами. Я намеренно пишу "как правило", поскольку оптимизация, особенно громоздкая и применённая бездумно, иногда работает против поставленной цели (ускорения) – надо тестировать.
Помимо приведённой выше пары наборов инструкций архитектура IA-32/Intel 64 имеет множество других, которые могут помочь минимизировать кол-во ветвлений, например, cmpxchg (486+), sbb, расширения SIMD, иногда даже loopz (loopnz) и bsf (bsr).

Рассмотрим некоторые из мини-алгоритмов без ветвлений.

Присвоение значений:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
; Заполнение EAX битами флага CF
sbb eax,eax  ; = cf ? 0xFFFFFFFF : 0
; Таким образом можно заменить недокументированную инструкцию salc на 'sbb al,al'
; (например, в x64, где salc не поддерживается)
 
; Заполнение EAX битами инверсного значения флага CF
cmc          ; invert cf
sbb eax,eax  ; = (source cf==0) ? 0xFFFFFFFF : 0
 
; Заполнение EAX битами флага ZF
setz al
movzx eax,al
neg eax       ; 1 -> 0xFFFFFFFF
; Или так (чуть медленнее, ИМХО):
setnz al      ; inverted condition ('nz' instead of 'z')
movzx eax,al
dec eax       ; 1 -> 0; 0 -> 0xFFFFFFFF
 
; Добавление значения флага CF к EAX
adc eax,0
; Вычитание значения флага CF из EAX
sbb eax,0
 
; Добавление 1 к EAX при значении CF==0
sbb eax,-1
; Вычитание 1 из EAX при значении CF==0
adc eax,-1
 
; Вычитание 1 из EAX при SF==0
setns dl      ; = sf ? 0 : 1
movzx edx,dl
sub eax,edx
Сложение/вычитание с ограничением:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
; Если EAX < N (сравнение беззнаковое), добавить к нему 1
sub eax,N  ; use N+1 for condition EAX <= N
adc eax,N  ; use N+1 for condition EAX <= N
 
; Если EAX > N (сравнение беззнаковое), добавить к нему 1
sub eax,N+1   ; use 'N' for condition EAX >= N
sbb eax,-N-2  ; -N-2 = (not 10)-1; use 'not N' for condition EAX >= N
 
; Если EAX < N (сравнение беззнаковое), вычесть из него 1
add eax,-N   ; use 'not N' for condition EAX <= N
adc eax,N-1  ; use 'N' for condition EAX <= N
 
; Если EAX > N (сравнение беззнаковое), вычесть из него 1
add eax,not N  ; use -N for condition EAX >= N
sbb eax,not N  ; use -N for condition EAX >= N
Работа со знаком:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
; Приведение регистра EAX к абсолютному (положительному) значению [Agner Fog]
cdq          ; copy sign bit of eax to all bits of edx
xor eax,edx  ; invert all bits if negative
sub eax,edx  ; add 1 if negative
 
; Приведение регистра EAX к отрицательному значению [модификация предыдущего кода]
cdq          ; copy sign bit of eax to all bits of edx
not edx      ; inverted all bits in edx
xor eax,edx  ; invert all bits if positive
sub eax,edx  ; add 1 if positive
 
; Инвертирование знака EAX при CF==1
sbb edx,edx  ; copy cf value to all bits of edx
xor eax,edx  ; invert all bits if cf
sub eax,edx  ; add 1 if cf
 
; Установка знака EAX в соответствии с флагом CF (0 - положительное, 1 - отрицательное значение)
cdq          ; copy sign bit of eax to all bits of edx
sbb ecx,ecx  ; copy cf value to all bits of edx
xor edx,ecx  ; 0xFFFFFFFF if need to change sign, 0 if not
xor eax,edx  ; invert all bits if need to change sign
sbb eax,edx  ; add 1 if need to change sign
Минимум, максимум:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
; Нахождение минимума среди EAX (a) и EBX (b), для беззнаковых чисел [Agner Fog, немного модифицированный код]
sub eax,ebx  ; = a-b
sbb edx,edx  ; = (a < b) ? 0xFFFFFFFF : 0
and eax,edx  ; = (a < b) ? a-b : 0
add eax,ebx  ; result is in eax
 
; Нахождение минимума среди EAX (a) и EBX (b), для знаковых чисел [Agner Fog, немного модифицированный код]
; Не работает при переполнении после первой инструкции, т.е. если числа отличаются на 0x80000000 и больше
; в знаковом формате (в этом случае работает наоборот - находит максимум)!
sub eax,ebx  ; will not work if overflow here (it will find maximum - Jin X comment)
cdq          ; = (a < b) ? 0xFFFFFFFF : 0
and eax,edx  ; = (a < b) ? a-b : 0
add eax,ebx  ; result is in eax
 
; Нахождение минимума среди EAX (a) и EBX (b), для знаковых чисел [модифицированный предыдущий код]
; Работает при любых значениях EAX и EBX
xor edx,edx
sub eax,ebx  ; = a-b
setl dl
neg edx      ; = (a < b) ? 0xFFFFFFFF : 0
and eax,edx  ; = (a < b) ? a-b : 0
add eax,ebx  ; result is in eax
 
; Нахождение минимума среди EAX и EBX с использованием cmovcc, для беззнаковых чисел
cmp eax,ebx
cmova eax,ebx  ; = ebx if eax (use cmovg for signed)
 
; Нахождение максимума среди EAX (a) и EBX (b), для беззнаковых чисел [на основе кода поиска минимума]
sub eax,ebx  ; = a-b
cmc          ; invert cf
sbb edx,edx  ; = (a >= b) ? 0xFFFFFFFF : 0
and eax,edx  ; = (a >= b) ? a-b : 0
add eax,ebx  ; result is in eax
 
; Нахождение максимума среди EAX (a) и EBX (b), для знаковых чисел [на основе кода поиска минимума]
; Не работает при переполнении после первой инструкции, т.е. если числа отличаются на 0x80000000 и больше
; в знаковом формате (в этом случае работает наоборот - находит минимум)!
sub eax,ebx  ; will not work if overflow here (it will find minimum - Jin X comment)
cdq          ; = (a < b) ? 0xFFFFFFFF : 0
not edx      ; = (a >= b) ? 0xFFFFFFFF : 0
and eax,edx  ; = (a >= b) ? a-b : 0
add eax,ebx  ; result is in eax
 
; Нахождение максимума среди EAX (a) и EBX (b), для знаковых чисел [модифицированный предыдущий код]
; Работает при любых значениях EAX и EBX
xor edx,edx
sub eax,ebx  ; = a-b
setg dl
neg edx      ; = (a > b) ? 0xFFFFFFFF : 0
and eax,edx  ; = (a > b) ? a-b : 0
add eax,ebx  ; result is in eax
 
; Нахождение максимума среди EAX и EBX с использованием cmovcc, для беззнаковых чисел
cmp eax,ebx
cmovb eax,ebx  ; = ebx if eax (use cmovl for signed)
Условный выбор значений:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
; Выбор между значениями EBX (b) и ECX (c) в зависимости от знака EAX (a), результат в EDX [Agner Fog]
test eax,eax
mov edx,ecx
cmovs edx,ebx  ; = (a < 0) ? b : c
 
; Как вы понимаете, в предыдущем фрагменте можно использовать любые регистры и условия
; Например, выбор между EAX (a) и EDX (d), последний выбирается при EBX (b) != ECX (c), результат в ESI:
cmp ebx,ecx
mov esi,eax
cmovne esi,edx  ; = (b != c) ? d : a
 
; Выбор между значениями EBX (b) и ECX (c) в зависимости от знака EAX (a), без использования cmovcc,
; результат в EDX [Agner Fog]
cdq          ; = (a < 0) ? 0xFFFFFFFF : 0
xor ebx,ecx  ; b ^ c = bits that differ between b and c
and edx,ebx  ; = (a < 0) ? (b ^ c) : 0
xor edx,ecx  ; = (a < 0) ? b : c
 
; Обмен значений EBX (b) и ECX (c) при CF==1 [на основе предыдущего кода]
sbb edx,edx  ; = cf ? 0xFFFFFFFF : 0
xor ebx,ecx  ; b ^ c = bits that differ between b and c
and edx,ebx  ; = cf ? (b ^ c) : 0
xor ecx,edx  ; = cf ? b : c
xor ebx,ecx  ; = cf ? c : b
 
; Код, из предыдущего фрагмента можно адаптировать под любое другое условие, заменив первую инструкцию
; Например, произвести обмен при EAX (a) < 0:
cdq  ; = (a < 0) ? 0xFFFFFFFF : 0
; Произвести обмен при EAX (a) <= 0:
dec eax
cdq      ; = (a <= 0) ? 0xFFFFFFFF : 0
; Произвести обмен при EAX (a) > 0:
neg eax
cdq      ; = (a > 0) ? 0xFFFFFFFF : 0
; Произвести обмен при EAX (a) >= 0:
cdq      ; = (a < 0) ? 0xFFFFFFFF : 0
not edx  ; = (a >= 0) ? 0xFFFFFFFF : 0
; Произвести обмен при CF=0:
cmc          ; invert cf
sbb edx,edx  ; = (source cf==0) ? 0xFFFFFFFF : 0
; Произвести обмен при ESI (s) > EDI (d), беззнаковое сравнение:
xor edx,edx
cmp esi,edi
seta dl  ; = (s > d) ? 1 : 0
neg edx   ; = (s > d) ? 0xFFFFFFFF : 0
; В последнем случае код получается довольно длинным (8 инструкций), и его использование
; может оказаться неоправданным – это необходимо тестировать на реальном коде!
; Вообще, тестирование вариантов кода, критичного к скорости исполнения - хорошая привычка :)
 
; Обмен значений EBX (b) и ECX (c), если EAX (a) == EBX (b)
cmpxchg ebx,ecx  ; if (a==b) { eax=b; b=c; zf=1 }
cmovz ecx,eax    ; c=b if (a==b)
 
; Обмен значений EAX (a) и EDX (d) при CF==1 с использованием cmovcc
mov ecx,eax
cmovc eax,edx  ; = d if cf
cmovc edx,ecx  ; = a if cf
 
; Пример адаптирования предыдущего кода под другие условия
; Обмен значений EAX (a) и EDX (d), если в ECX (c) установлены все биты по маске EBX (b):
and ecx,ebx
xor ecx,ebx    ; zf = 1 if (c & b) == b
mov ecx,eax
cmove eax,edx  ; = d if ((c & b) == b)
cmove edx,ecx  ; = a if ((c & b) == b)
Проверка границ и преобразование:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
; Проверка содержимого AL на символ цифры
sub al,'0'
cmp al,9      ; '9'-'0'
ja .notdigit
 
; Получение 16-ричной цифры (символа) из значения AL (a) == 0..15
add al,256-10  ; cf=1 if a >=10
sbb dl,dl      ; = (a >= 10) ? 0xFF : 0
and dl,7       ; = (a >= 10) ? 7 : 0 (use 27h if you need lower case letters 'a'..'f')
add al,'0'+10  ; convert to char
add al,dl      ; add a break between digits and letters (if a >= 10)
; Этот код работает гораздо быстрее, чем:
cmp al,10
sbb al,69h
das         ; very slow instruction
; Однако он может работать и чуть медленнее, чем:
  cmp al,10
  jb .digit
  add al,7    ; add a break between digits and letters (if a >= 10)
.digit:
  add al,'0'  ; convert to digit char
; Тестируйте!
 
; Приведение строчной буквы AL к заглавной (остальные символы остаются без изменений)
mov dl,al
sub dl,'a'
cmp dl,26   ; alphabet has 26 letters
sbb dh,dh   ; = (al is lower case) ? 0xFF : 0
and dh,20h  ; = (al is lower case) ? 0x20 : 0
sub al,dh   ; convert to upper case
 
; Приведение заглавной буквы AL к строчной (остальные символы остаются без изменений)
mov dl,al
sub dl,'A'
cmp dl,26   ; alphabet has 26 letters
sbb dh,dh   ; = (al is capital) ? 0xFF : 0
and dh,20h  ; = (al is capital) ? 0x20 : 0
add al,dh   ; convert to upper case
 
; Приведение 16 строчных букв к заглавным (остальные символы остаются без изменений) с использованием SSE2
; Блок инициализации (выполняется 1 раз):
mov eax,(127-'z')*01010101h
movd xmm2,eax       ; mov eax value to lower dword of xmm2
mov eax,(127-26)*01010101h
movd xmm3,eax       ; mov eax value to lower dword of xmm3
mov eax,20202020h
movd xmm4,eax       ; mov eax value to lower dword of xmm4
pshufd xmm2,xmm2,0  ; fill entire xmm2 register by lower dword value
pshufd xmm3,xmm3,0  ; fill entire xmm3 register by lower dword value
pshufd xmm4,xmm4,0  ; fill entire xmm4 register by lower dword value
; Преобразование содержимого XMM0, результат будет также в XMM0:
movdqa xmm1,xmm0    ; temp register
paddb xmm1,xmm2     ; shift each byte with lower case letter to high signed short int values
pcmpgtb xmm1,xmm3   ; compare each byte with high 26 signed values and store 0xFF (if in range)
pand xmm1,xmm4      ; mask with 20h (difference between upper and lower case)
psubb xmm0,xmm1     ; convert each byte to upper case
 
; Приведение 16 заглавных букв к строчным (остальные символы остаются без изменений) с использованием SSE2
; Блок инициализации (выполняется 1 раз):
mov eax,(127-'Z')*01010101h
movd xmm2,eax       ; mov eax value to lower dword of xmm2
mov eax,(127-26)*01010101h
movd xmm3,eax       ; mov eax value to lower dword of xmm3
mov eax,20202020h
movd xmm4,eax       ; mov eax value to lower dword of xmm4
pshufd xmm2,xmm2,0  ; fill entire xmm2 register by lower dword value
pshufd xmm3,xmm3,0  ; fill entire xmm3 register by lower dword value
pshufd xmm4,xmm4,0  ; fill entire xmm4 register by lower dword value
; Преобразование содержимого XMM0, результат будет также в XMM0:
movdqa xmm1,xmm0    ; temp register
paddb xmm1,xmm2     ; shift each byte with capital case letter to high signed short int values
pcmpgtb xmm1,xmm3   ; compare each byte with high 26 signed values and store 0xFF (if in range)
pand xmm1,xmm4      ; mask with 20h (difference between upper and lower case)
paddb xmm0,xmm1     ; convert each byte to lower case
Манипуляции с битами:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
; Определить степень двойки значения EAX (с округлением в меньшую сторону), результат в ECX
bsr ecx,eax  ; ecx = most significant bit of eax
 
; Определить степень двойки значения EAX (с округлением в большую сторону), результат в ECX
dec eax
bsr ecx,eax  ; ecx = most significant bit of (eax-1)
inc ecx      ; result in ecx
 
; Определить кол-во идущих подряд нулевых битов в младших разрядах EAX, результат в ECX
mov ecx,32   ; bsf will not modify destination register if source == 0
bsf ecx,eax  ; count of zero low bits
; Вместо этой конструкции можно использовать инструкцию 'tzcnt ecx,eax' из набора BMI1, однако
; я не рекомендую увлекаться этим, поскольку для её корректного использования вы должны быть
; уверены в том, что она поддерживается, иначе рискуете получить ту же bsf (с бессмысленным
; префиксом rep), которая при значении EAX==0 оставит результат в ECX неопределённым.
 
; Определить кол-во идущих подряд единичных битов в младших разрядах EAX, результат в ECX
not eax      ; inverse all bits
mov ecx,32   ; bsf will not modify destination register if source == 0
bsf ecx,eax  ; count of non-zero low bits
 
; Определить кол-во идущих подряд нулевых битов в старших разрядах EAX, результат в ECX
or ecx,-1    ; = -1; bsf will not modify destination register if source == 0
bsr ecx,eax  ; count of zero low bits
not ecx
add ecx,32   ; = 31 - (ecx after bsr)
; Более простой (но опасный, см. ниже) вариант:
lzcnt ecx,eax
; Перед использованием этой инструкции необходимо проверить бит LZCNT в CPUID (уровень 0x80000001, бит 5 в ECX),
; иначе инструкция lzcnt превратиться в bsr (с бессмысленным префиксом rep) и вернёт не кол-во нулевых
; битов в старших разрядах, а номер последнего ненулевого бита (что далеко не одно и то же).
 
; Определить кол-во идущих подряд единичных битов в старших разрядах EAX, результат в ECX
not eax      ; inverse all bits
or ecx,-1    ; = -1; bsf will not modify destination register if source == 0
bsr ecx,eax  ; count of non-zero low bits
not ecx
add ecx,32   ; = 31 - (ecx after bsr)
 
; Определить кол-во единичных битов в EAX, результат в ECX
popcnt ecx,eax  ; requires SSE 4.2
 
; Определить кол-во нулевых битов в EAX, результат в ECX
not eax         ; inverse all bits
popcnt ecx,eax  ; requires SSE 4.2
 
; Определить кол-во общих младших нулевых битов в EAX и EBX, результат в ECX
; (например для 10110000b и 11101100b общее кол-во младших нулевых битов = 2)
or eax,ebx   ; join non-zero bits of eax and ebx
mov ecx,32   ; you can remove this if you're sure that at least one of registers (eax or ebx) is non-zero or if you'll use jz after bsf
bsf ecx,eax  ; minimum of zero bit counts in eax and ebx
 
; Сдвинуть EAX на бит влево при CF==1
setc cl     ; = cf ? 1 : 0
shl eax,cl
 
; Установить бит номер CL в регистре EAX при условии CF==1
setc dl
movzx edx,dl  ; = cf ? 0xFFFFFFFF : 0
shl edx,cl    ; = single bit if cf
or eax,edx    ; set bit if cf
 
; Сбросить бит номер CL в регистре EAX при условии CF==0
setnc dl
movzx edx,dl  ; = cf ? 0 : 0xFFFFFFFF
shl edx,cl    ; = single bit if not cf
not edx       ; inverse bit
and eax,edx   ; clear bit if not cf
 
; Установить бит номер CL в регистре EAX в соответствии со значением флага CF
setc dl      ; = cf ? 1 : 0
bt eax,ecx   ; cf = is bit already set in eax?
sbb edx,0    ; dl = 1 or 0xFF if source cf != bit in eax
and edx,1    ; extract single bit of dl
shl edx,cl   ; = single bit if eax != 0
xor eax,edx  ; inverse if source cf != bit in eax
 
; Обнулить старшие биты в EAX, сохранив CL (0..31) младших
xor edx,edx  ; clear all bits
bts edx,ecx  ; set bit cl in edx
dec edx      ; make mask of cl lower bits
and eax,edx  ; apply mask
 
; Обнулить CL (0..31) младших битов в EAX
or edx,-1    ; set all bits
btr edx,ecx  ; set bit cl in edx
inc edx      ; make mask of cl lower bits
and eax,edx  ; apply mask
 
; Установить CL (0..31) младших битов в EAX
xor edx,edx  ; clear all bits
bts edx,ecx  ; set bit cl in edx
dec edx      ; make mask of cl lower bits
or eax,edx   ; apply mask
 
; Установить старшие биты в EAX, сохранив CL (0..31) младших
or edx,-1    ; set all bits
btr edx,ecx  ; set bit cl in edx
inc edx      ; make mask of cl lower bits
or eax,edx   ; apply mask
Если вас интересуют манипуляции с битами, изучите набор инструкций BMI1, BMI2, которые, правда, присутствуют лишь в новых моделях процессоров Intel (начиная с Haswell).

Манипуляции с флагами:
Assembler
1
2
3
4
5
6
7
8
; Установка флага ZF=1
cmp eax,eax
 
; Установка флага CF=1, если EAX==0 (сброс в противном случае) [Agner Fog]
cmp eax,1
 
; Установка флага CF=1, если EAX!=0 (сброс в противном случае), флаг ZF = not CF [Agner Fog]
neg eax
Оптимизация циклов:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
; Не используйте в критичном к скорости исполнения коде инструкцию loop, она медленнее, чем:
sub ecx,1  ; it's faster a bit than 'dec ecx'
jnz .loop
; Заменив jnz на ja исходное значение ECX==0 не будет порождать 2^32 циклов, цикл завершится на первом же витке
; (использовать 'dec ecx' при этом нельзя).
; Использовав jg, значение ECX будет считаться знаковым (т.е. при значении, скажем, ECX==-1 цикл не будет повторён).
; Использовав jnc, jge или jns можно организовать на 1 цикл больше (т.е. последний виток будет при ECX==0),
; при этом jnc будет считать значение ECX беззнаковым (использовать 'dec ecx' при этом нельзя), а jge и jns - знаковым.
; Разница между ними в том, что при исходном значении ECX==0x80000000 (уменьшенном в конце первого витка цикла до 0x7FFFFFFF)
; jge завершит работу, а jns - нет (при других отрицательных значениях, скажем, 0x80000001, уменьшенном до 0x80000000,
; работу завершат оба варианта).
 
; Инструкция jecxz также медленнее, чем:
test ecx,ecx
jz .break
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
; Для организации цикла for (int i=0; i < n; i++) вместо кода:
  mov ecx,N
  xor eax,eax   ; i = 0
.loop:
  cmp eax,ecx   ; i < N ?
  jge .loopend  ; exit when i >= N
  . . .
  add eax,1     ; i++
  jmp .loop     ; repeat
.loopend:
 
; Лучше убрать лишнюю инструкцию jmp и написать так:
  mov ecx,N
  test ecx,ecx
  jle .loopend  ; skip if N <= 0
  xor eax,eax   ; i = 0
.loop:
  . . .
  add eax,1     ; i++
  cmp eax,ecx
  jl .loop      ; loop if i < N
.loopend:
 
; А ещё лучше - так (если увеличивающееся значение i не используется внутри цикла):
  mov ecx,N
  test ecx,ecx
  jle .loopend  ; skip if N <= 0
.loop:
  . . .
  sub ecx,1     ; N--
  jnz .loop     ; loop if not zero
.loopend:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
; Циклы while(true) {... if (smth) break...} лучше записывать не так:
.next:
  call A
  cmp eax,edx  ; break condition
  je .break    ; break cycle
  call B
  jmp .next
.break:
 
; А вот так (что так же избавит цикл от лишнего jmp):
  jmp .start
.next:
  call B
.start:
  call A
  cmp eax,edx  ; break condition
  jne .next    ; continue if no break
Оптимизация кол-ва ветвлений:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
; Оптимизация if с присвоением в ветке then или else
; Вариант с использованием cmovcc уже рассматривался, поэтому давайте оптимизируем код:
  cmp esi,edi  ; any condition
  jne .else
  mov eax,ecx
  jmp .continue
.else:
  add eax,edx
.continue:
; Следующим образом:
  cmp esi,edi   ; any condition
  mov eax,ecx   ; 'mov' doesn't change any flags
  je .continue
  add eax,edx
 
; Для более сложного (чем простое присвоение) кода в then, но с коротким блоком else
; (размером с байт, слово или двойное слово) можно сделать так:
  cmp esi,edi  ; any condition
  jne .else
  add eax,ebx
  db 0B9h      ; first byte of 'mov ecx,N' instruction (this is equal to 'mov ecx,?' + 'org $-4' in MASM)
.else:
  add eax,edx  ; 2 bytes
  inc ebx      ; 1 byte
  dec edx      ; 1 byte - 4 bytes total
; Поясню: блок else занимает ровно 4 байта, значит блок then можно завершить не инструкцией 'jmp .continue',
; а инструкцией 'mov ecx,N', которая "поглотит" эти 4 байта (т.к. именно они будут записаны внутри
; 'mov ecx,N' в качестве присваиваемого значения) - это работает быстрее
 
; Предположим, нам необходимо выйти из цикла при значениях EAX==0 или EAX==1, но перейти необходимо по разным адресам
; Вместо кода:
  cmp eax,1
  jb .eax_zero
  je .eax_one
; Лучше написать:
  cmp eax,1
  jbe .eax_zero
  . . .
.eax_zero:
  je .eax_one
; Тем самым мы уменьшим кол-во условных инструкций внутри цикла (ведь весь код в нём повторяется многократно)
; с 2 до 1, а проверку на значение 0 или 1 вынесем наружу
 
; Выход из цикла при значении EAX == 0 или EBX > ECX
; Вместо кода:
  test eax,eax
  jz .break
  cmp ebx,ecx
  ja .break
; Можно написать:
  test eax,eax
  setz cl       ; = (eax==0) ? 1 : 0
  cmp ebx,ecx
  seta ch       ; = (ebx>ecx) ? 1 : 0
  or cl,ch      ; zf = not (eax==0 || ebx>ecx)
  jnz .break
; Так можно объединить любое кол-во условий и использовать одну инструкцию условного перехода внутри цикла вместо нескольких.
; Но опять же, используя подобные трюки, тестируйте код, поскольку они могут наоборот привести к замедлению!
; К примеру, пытаясь таким образом оптимизировать 3 условных перехода в алгоритме быстрого вычисления НОД,
; я обнаружил, что "оптимизированный" вариант работает дольше (по крайней мере, на моём компьютере).
; Попытка оптимизировать 2 условных перехода так же не привела к успеху, поэтому я оставил все 3.
; В другом же коде такая оптимизация привела к ускорению.
Если вы поймёте принцип всех этих манипуляций, то сможете модифицировать приведённый выше код под необходимые вам условия.
Тем не менее, используя эти трюки, призываю вас тестировать их на реальном коде (по возможности, на разных процессорах). В некоторых случаях код с ветвлением может оказаться быстрее, а использование инструкций cmovcc хоть и короче, но бывает медленнее более длинных алгоритмов без их использования.

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

p.s. Присылайте в комментариях к этой статье другие трюки, о которых вы знаете (желательно с комментариями), и я добавлю их в этот список (но только если они будут касаться оптимизации ветвлений, всё остальное – в других статьях). Также пишите о найденных неточностях и о том, как можно оптимизировать этот код ещё сильнее

p.p.s. Буду так же рад любому качественному материалу (ссылкам) про оптимизацию.

Эта и другие мои статьи на форуме.
Просмотров 229 Комментарии 0
Всего комментариев 0

Комментарии

 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.