У меня есть функция Compare(), которая выглядит так:
inline bool Compare(bool greater, int p1, int p2) {
if (greater) return p1>=p2;
else return p1<=p2;
}
Я решил оптимизировать, чтобы избежать ветвления:
inline bool Compare2(bool greater, int p1, int p2) {
bool ret[2] = {p1<=p2,p1>=p2};
return ret[greater];
}
Затем я протестировал это:
bool x = true;
int M = 100000;
int N = 100;
bool a[N];
int b[N];
int c[N];
for (int i=0;i<N; ++i) {
a[i] = rand()%2;
b[i] = rand()%128;
c[i] = rand()%128;
}
// Timed the below loop with both Compare() and Compare2()
for (int j=0; j<M; ++j) {
for (int i=0; i<N; ++i) {
x ^= Compare(a[i],b[i],c[i]);
}
}
Результаты:
Compare(): 3.14ns avg
Compare2(): 1.61ns avg
Я бы сказал, что case-closed, избегайте ветвления FTW. Но для полноты я заменил
a[i] = rand()%2;
с:
a[i] = true;
и получил то же самое измерение ~ 3.14ns. Предположительно, тогда не происходит ветвления, и компилятор фактически переписывает Compare(), чтобы избежать инструкции if. Но тогда, почему Compare2() быстрее?
К сожалению, я ассемблер-неграмотный, иначе я бы попытался ответить на него сам.
РЕДАКТИРОВАТЬ: Ниже приведена некоторая сборка:
_Z7Comparebii:
.LFB4:
.cfi_startproc
.cfi_personality 0x3,__gxx_personality_v0
pushq %rbp
.cfi_def_cfa_offset 16
movq %rsp, %rbp
.cfi_offset 6, -16
.cfi_def_cfa_register 6
movl %edi, %eax
movl %esi, -8(%rbp)
movl %edx, -12(%rbp)
movb %al, -4(%rbp)
cmpb $0, -4(%rbp)
je .L2
movl -8(%rbp), %eax
cmpl -12(%rbp), %eax
setge %al
jmp .L3
.L2:
movl -8(%rbp), %eax
cmpl -12(%rbp), %eax
setle %al
.L3:
leave
ret
.cfi_endproc
.LFE4:
.size _Z7Comparebii, .-_Z7Comparebii
.section .text._Z8Compare2bii,"axG",@progbits,_Z8Compare2bii,comdat
.weak _Z8Compare2bii
.type _Z8Compare2bii, @function
_Z8Compare2bii:
.LFB5:
.cfi_startproc
.cfi_personality 0x3,__gxx_personality_v0
pushq %rbp
.cfi_def_cfa_offset 16
movq %rsp, %rbp
.cfi_offset 6, -16
.cfi_def_cfa_register 6
movl %edi, %eax
movl %esi, -24(%rbp)
movl %edx, -28(%rbp)
movb %al, -20(%rbp)
movw $0, -16(%rbp)
movl -24(%rbp), %eax
cmpl -28(%rbp), %eax
setle %al
movb %al, -16(%rbp)
movl -24(%rbp), %eax
cmpl -28(%rbp), %eax
setge %al
movb %al, -15(%rbp)
movzbl -20(%rbp), %eax
cltq
movzbl -16(%rbp,%rax), %eax
leave
ret
.cfi_endproc
.LFE5:
.size _Z8Compare2bii, .-_Z8Compare2bii
.text
Теперь фактический код, который выполняет тест, может использовать встроенные версии указанных выше двух функций, поэтому есть вероятность, что это может быть неправильный код для анализа. С учетом сказанного я вижу команду jmp в Compare(), поэтому я думаю, что это означает, что она является ветвящейся. Если это так, я думаю, этот вопрос становится следующим: почему предиктор ветки не улучшает производительность Compare(), когда я изменяю a[i] от rand()%2 до true (или false, если на то пошло)?
EDIT2: я заменил "предсказание ветвей" на "ветвление", чтобы сделать сообщение более разумным.
