Правильный if для ускорения работы
Поводом для размышления по этой теме послужил пост где поясняется на примерах два разных пути работы условного оператора if. Приводится генерируемый ассемблер где показано, что в одном случае после кода сравнения идет блок с кодом положительного решения, а в другом случае после сравнения идет отрицательная ветка. Я решил провести свои тесты в разных вариациях, чтобы проанализировать закономерность и как это можно использовать в оптимизации кода.
В общем случае, компилятор генерирует ассемблер с таким предположением, что условие внутри if маловероятно и после кода самой инструкции ifставит условный переход (je, jneи прочие) на случай если когда-нибудь условие будет истинным. После строки с переходом идут следующие за оператором if инструкции. Метка блока кода, соответствующего истинному решению if, обычно расположен по тексту где-то дальше от самого оператора if. Поэтому процессору, загрузив в кэш часть кода функции где расположен блок ifи близлежащий код придется, в случае положительного решения, if отбрасывать то что он уже загрузил и загружать код по адресу метки перехода с положительным решением. А уже после его выполнения возвращаться обратно, отбрасывая то, что есть сейчас и загружая то место где он был, анализируя блок if. Так же это может привести к остановке конвейера процессора, следовательно, увеличит время выполнения кода.
Помимо описанного случая может быть и по другому (об этом и статья). Для того, чтобы подсказать компилятору какую ветвь if считать приоритетной есть инструкция __builtin_expect (ling, long). Где в первый операнд ставится анализируемое условие, а вторым 1 или 0 — приоритетное или нет.
Пример: https://godbolt.org/z/7PnrWPvxe
Из примера функция b ():
bool b(bool ptr) {
if(__builtin_expect(ptr, 1)){
std::cout << " true )" << std::endl;
return true;
}
std::cout << " false (" << std::endl;
return false;
}Ее ASM:
Hidden text
.LC0:
.string " true )"
.LC1:
.string " false ("
b(bool):
push rbp
mov ebp, edi
push rbx
sub rsp, 8
test dil, dil
je .L12
mov edx, 7
mov esi, OFFSET FLAT:.LC0
.L32:
mov edi, OFFSET FLAT:std::cout
call std::basic_ostream >& std::__ostream_insert >(std::basic_ostream >&, char const*, long)
mov rax, QWORD PTR std::cout[rip]
mov rax, QWORD PTR [rax-24]
mov rbx, QWORD PTR std::cout[rax+240]
test rbx, rbx
je .L33
cmp BYTE PTR [rbx+56], 0
je .L18
movsx esi, BYTE PTR [rbx+67]
.L19:
mov edi, OFFSET FLAT:std::cout
call std::basic_ostream >::put(char)
mov rdi, rax
call std::basic_ostream >::flush()
add rsp, 8
mov eax, ebp
pop rbx
pop rbp
ret
.L18:
mov rdi, rbx
call std::ctype::_M_widen_init() const
mov rax, QWORD PTR [rbx]
mov esi, 10
mov rax, QWORD PTR [rax+48]
cmp rax, OFFSET FLAT:std::ctype::do_widen(char) const
je .L19
mov rdi, rbx
call rax
movsx esi, al
jmp .L19
.L12:
mov edx, 8
mov esi, OFFSET FLAT:.LC1
jmp .L32
.L33:
call std::__throw_bad_cast()
Интересует следующая часть:
test dil, dil
je .L12
mov edx, 7
mov esi, OFFSET FLAT:.LC0 Если вам неизвестна инструкция test то сюда. Если условие false то прыгаем на метку .L12 (которая очень далеко, расположены после тела функции). Если true то продолжаем двигаться дальше по строкам — загружаем .string » true)», выводим на экран и возвращаем результат. Если все будет как мы задумали, то есть ptr будет true то весь наш код — это набор последовательных строк, которые достаточно один раз загрузить в кеш и последовательно исполнять.
Однако, если посмотреть аналог этой функции — функцию c ():
bool c(bool ptr) {
if(ptr){
std::cout << " true )" << std::endl;
return true;
}
std::cout << " false (" << std::endl;
return false;
}Ее ASM уже другой:
Hidden text
c(bool):
push rbp
mov edx, 8
mov ebp, edi
mov esi, OFFSET FLAT:.LC1
push rbx
sub rsp, 8
test dil, dil
je .L55
mov edx, 7
mov esi, OFFSET FLAT:.LC0
.L55:
mov edi, OFFSET FLAT:std::cout
call std::basic_ostream >& std::__ostream_insert >(std::basic_ostream >&, char const*, long)
mov rax, QWORD PTR std::cout[rip]
mov rax, QWORD PTR [rax-24]
mov rbx, QWORD PTR std::cout[rax+240]
test rbx, rbx
je .L56
cmp BYTE PTR [rbx+56], 0
je .L41
movsx esi, BYTE PTR [rbx+67]
.L42:
mov edi, OFFSET FLAT:std::cout
call std::basic_ostream >::put(char)
mov rdi, rax
call std::basic_ostream >::flush()
add rsp, 8
mov eax, ebp
pop rbx
pop rbp
ret
.L41:
mov rdi, rbx
call std::ctype::_M_widen_init() const
mov rax, QWORD PTR [rbx]
mov esi, 10
mov rax, QWORD PTR [rax+48]
cmp rax, OFFSET FLAT:std::ctype::do_widen(char) const
je .L42
mov rdi, rbx
call rax
movsx esi, al
jmp .L42
.L56:
call std::__throw_bad_cast()
Интересны следующие строки:
mov esi, OFFSET FLAT:.LC1
push rbx
sub rsp, 8
test dil, dil
je .L55
mov edx, 7
mov esi, OFFSET FLAT:.LC0
.L55:
mov edi, OFFSET FLAT:std::coutВ самом начале функции, даже до блока if подгружается строка .LC1, соответствующая. string » false (». После выполняется анализ условия и в случае false перепрыгиваем две строки и делаем вывод на экран, а в случае true заменяем загруженное ранее условие на метку .LC0 и двигаемся дальше, выводя на экран. В этой функции ничего критичного не случиться при любой раскладке, разве что будет лишняя перезапись регистра в случае положительного исхода. Это при условии, что функция из примера довольно мала. Видим так же, что компилятор здесь выбрал другую ветвь if в качестве приоритета.
Посмотрим функцию main где разница между двумя условными переходами будет более существенна.
int main(int argc, char **argv) {
std::cout << " main" << std::endl;
if(__builtin_expect(b(true),1))
{
std::cout << " main true" << std::endl;
}
if(c(true))
{
std::cout << " main false" << std::endl;
}
return EXIT_SUCCESS;
}Начало функции main и первый if генерит такой ASM код:
Hidden text
.LC2:
.string " main"
.LC3:
.string " main true"
.LC4:
.string " main false"
main:
sub rsp, 8
mov esi, OFFSET FLAT:.LC2
mov edi, OFFSET FLAT:std::cout
call std::basic_ostream >& std::operator<< >(std::basic_ostream >&, char const*)
mov rdi, rax
call std::basic_ostream >& std::endl >(std::basic_ostream >&) [clone .isra.0]
mov edi, 1
call b(bool)
test al, al
je .L58
mov edi, OFFSET FLAT:std::cout
mov esi, OFFSET FLAT:.LC3
call std::basic_ostream >& std::operator<< >(std::basic_ostream >&, char const*)
mov rdi, rax
call std::basic_ostream >& std::endl >(std::basic_ostream >&) [clone .isra.0]
.L58:
mov edi, 1
call c(bool)
Суть самой проверки:
call b(bool)
test al, al
je .L58
mov edi, OFFSET FLAT:std::cout
mov esi, OFFSET FLAT:.LC3Если условие true то двигаемся построчно выводим результат и переходим к следующему условию.
Если условие false то перепрыгиваем несколько строк и идем к следующему условию. Все логично и предсказуемо.
Посмотрим второе условие:
.L58:
mov edi, 1
call c(bool)
test al, al
jne .L67
.L59:
xor eax, eax
add rsp, 8
ret
.L67:
mov esi, OFFSET FLAT:.LC4
mov edi, OFFSET FLAT:std::cout
call std::basic_ostream >& std::operator<< >(std::basic_ostream >&, char const*)
mov rdi, rax
call std::basic_ostream >& std::endl >(std::basic_ostream >&) [clone .isra.0]
jmp .L59
Проверяем условие, в случае false двигаемся дальше и завершаем программу. В случае true прыгаем сначала на .L67 где подгружаем и выводим текст, затем прыгаем обратно на третью строку после if где завершаем программу. В данном случае тело блока с true было маленьким, поэтому его метка .L67 не очень далеко от условия, но в реальной программе все блоки могут быть больше.
Однако не все так однозначно в современных оптимизациях. Возьмем пример: https://godbolt.org/z/3W9r1s3d8 . Две простейшие функции foo () и bar () почти с одинаковым телом и одним условным оператором if в каждой:
bool foo(int i)
{
if(i != 1)
{
fprintf(stderr, "error foo");
return false;
}
fprintf(stdout, "good foo");
return true;
}
bool bar(int i)
{
if(i == 1)
{
fprintf(stderr, "error bar");
return false;
}
fprintf(stdout, "good bar");
return true;
}Основная часть ассемблера первой:
.LC0:
.string "error foo"
.LC1:
.string "good foo"
foo(int):
subq $8, %rsp
cmpl $1, %edi
je .L2
movl $9, %edx
movl $1, %esi
movl $.LC0, %ediЗдесь условие »!=» считается наиболее вероятным. В функции bar () наоборот:
.LC2:
.string "error bar"
.LC3:
.string "good bar"
bar(int):
subq $8, %rsp
cmpl $1, %edi
je .L10
movl $8, %edx
movl $1, %esi
movl $.LC3, %ediУсловие »==» считается менее вероятным, чем все остальные случаи.
Такой же логикой обладают условия в функции main ():
.LC4:
.string "Unexpected number"
.LC5:
.string "--error"
.LC6:
.string "error"
.LC7:
.string "fail"
.LC8:
.string "main good"
main:
pushq %rbx
cmpl $2, %edi
jne .L24
movq 8(%rsi), %rdi
movl $.LC5, %esi
call strcmp
testl %eax, %eax
je .L25
movl $1, %edi
call foo(int)
movl $2, %edi
movl %eax, %ebx
call bar(int)
testb %bl, %bl
je .L16
testb %al, %al
je .L16
movl $4, %edx
movl $1, %esi
movl $.LC7, %ediЗдесь вперемешку: какие-то условия считаются компилятором как наиболее частые, какие-то нет. В процессе выполнения «штатного» режима работы не получится последовательно бежать по строкам.
Таким образом компилятор пытается предугадать логику обработки условий, в общем случае считает, что если в условии идет сравнение с каким-либо значением, то это маловероятный исход и скорее всего будут далее выполнятся инструкции после условного оператора. Но как видно из примера функций foo () и bar () компилятор может построить логику отличную от нашего замысла, поэтому лучше ему явно сказать при помощи __builtin_expect какая ветка условного перехода является наиболее часто выбираемой с нашей точки зрения. С применением этого макроса в примере (та часть где определен -DUSE_EXPECTED) видим, что сначала функций поставлены условия и следующие за ними инструкции, а обработка срабатывания условий вынесена в конец функций, чтобы в нормальном режиме выполняя код функций компилятор не спотыкался о блоки с обработкой редких ошибок.
