оптимизация — микрооптимизация функции сравнения c ++
у меня есть 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
Я бы сказал, что дело закрыто, избегайте разветвления FTW. Но для полноты я заменил
a[i] = rand()%2;
с:
a[i] = true;
и получил точно такое же измерение ~ 3,14 нс. Предположительно, тогда ветвления не происходит, и компилятор фактически переписывает 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Я заменил «предсказание ветвления» на «ветвление», чтобы сделать мой пост более осмысленным.
Решение
Я написал библиотеку C ++ под названием Celero, предназначенную для тестирования именно таких оптимизаций и альтернатив. (Бесстыдная самореклама: https://github.com/DigitalInBlue/Celero)
Я провел ваши дела, используя следующий код:
class StackOverflowFixture : public celero::TestFixture
{
public:
StackOverflowFixture()
{
}
inline bool NoOp(bool greater, int p1, int p2)
{
return true;
}
inline bool Compare(bool greater, int p1, int p2)
{
if(greater == true)
{
return p1>=p2;
}
return p1<=p2;
}
inline bool Compare2(bool greater, int p1, int p2)
{
bool ret[2] = {p1<=p2,p1>=p2};
return ret[greater];
}
inline bool Compare3(bool greater, int p1, int p2)
{
return (!greater != !(p1 <= p2)) | (p1 == p2);
}
inline bool Compare4(bool greater, int p1, int p2)
{
return (greater ^ (p1 <= p2)) | (p1 == p2);
}
};
BASELINE_F(StackOverflow, Baseline, StackOverflowFixture, 100, 5000000)
{
celero::DoNotOptimizeAway(NoOp(rand()%2, rand(), rand()));
}
BENCHMARK_F(StackOverflow, Compare, StackOverflowFixture, 100, 5000000)
{
celero::DoNotOptimizeAway(Compare(rand()%2, rand(), rand()));
}
BENCHMARK_F(StackOverflow, Compare2, StackOverflowFixture, 100, 5000000)
{
celero::DoNotOptimizeAway(Compare2(rand()%2, rand(), rand()));
}
BENCHMARK_F(StackOverflow, Compare3, StackOverflowFixture, 100, 5000000)
{
celero::DoNotOptimizeAway(Compare3(rand()%2, rand(), rand()));
}
BENCHMARK_F(StackOverflow, Compare4, StackOverflowFixture, 100, 5000000)
{
celero::DoNotOptimizeAway(Compare4(rand()%2, rand(), rand()));
}
Результаты показаны ниже:
[==========]
[ CELERO ]
[==========]
[ STAGE ] Baselining
[==========]
[ RUN ] StackOverflow.Baseline -- 100 samples, 5000000 calls per run.
[ DONE ] StackOverflow.Baseline (0.690499 sec) [5000000 calls in 690499 usec] [0.138100 us/call] [7241140.103027 calls/sec]
[==========]
[ STAGE ] Benchmarking
[==========]
[ RUN ] StackOverflow.Compare -- 100 samples, 5000000 calls per run.
[ DONE ] StackOverflow.Compare (0.782818 sec) [5000000 calls in 782818 usec] [0.156564 us/call] [6387180.672902 calls/sec]
[ BASELINE ] StackOverflow.Compare 1.133699
[ RUN ] StackOverflow.Compare2 -- 100 samples, 5000000 calls per run.
[ DONE ] StackOverflow.Compare2 (0.700767 sec) [5000000 calls in 700767 usec] [0.140153 us/call] [7135039.178500 calls/sec]
[ BASELINE ] StackOverflow.Compare2 1.014870
[ RUN ] StackOverflow.Compare3 -- 100 samples, 5000000 calls per run.
[ DONE ] StackOverflow.Compare3 (0.709471 sec) [5000000 calls in 709471 usec] [0.141894 us/call] [7047504.408214 calls/sec]
[ BASELINE ] StackOverflow.Compare3 1.027476
[ RUN ] StackOverflow.Compare4 -- 100 samples, 5000000 calls per run.
[ DONE ] StackOverflow.Compare4 (0.712940 sec) [5000000 calls in 712940 usec] [0.142588 us/call] [7013212.893091 calls/sec]
[ BASELINE ] StackOverflow.Compare4 1.032500
[==========]
[ COMPLETE ]
[==========]
Учитывая этот тест, выглядит Compare2 это лучший вариант для этой микрооптимизации.
РЕДАКТИРОВАТЬ:
Сравнение 2 сборки (лучший случай):
cmp r8d, r9d
movzx eax, dl
setle BYTE PTR ret$[rsp]
cmp r8d, r9d
setge BYTE PTR ret$[rsp+1]
movzx eax, BYTE PTR ret$[rsp+rax]
Сравнение3 сборки (следующий лучший случай):
xor r11d, r11d
cmp r8d, r9d
mov r10d, r11d
setg r10b
test dl, dl
mov ecx, r11d
sete cl
mov eax, r11d
cmp ecx, r10d
setne al
cmp r8d, r9d
sete r11b
or eax, r11d
Другие решения
Я думаю, я понял большую часть этого.
Когда я разместил сборку для функций в своем редакторе OP, я заметил, что встроенная версия может отличаться. Я не проверял и не публиковал временный код, потому что он был более привлекательным, и потому что я думал, что процесс встраивания не изменится, независимо от того, происходит ли разветвление в Compare(),
Когда я отключил функцию и повторил измерения, я получил следующие результаты:
Compare(): 7.18ns avg
Compare2(): 3.15ns avg
Затем, когда я заменил a[i]=rand()%2 с a[i]=falseЯ получил следующее:
Compare(): 2.59ns avg
Compare2(): 3.16ns avg
Это демонстрирует выгоду от предсказания ветвления. Тот факт, что a[i] замена не дала улучшения, первоначально показывает, что встраивание убрало ветку.
Итак, последний кусочек тайны — почему встроенный Compare2() превосходит встроенный Compare(), Я полагаю, я мог бы опубликовать сборку для временного кода. Кажется достаточно правдоподобным, что некоторые странности в том, как функции встроены, могут привести к этому, так что я рад закончить свое расследование здесь. Я буду заменять Compare() с Compare2() в моем приложении.
Спасибо за много полезных комментариев.
РЕДАКТИРОВАТЬ: я должен добавить, что вероятная причина того, что Compare2 Преимущество всех остальных заключается в том, что процессор способен выполнять оба сравнения параллельно. Это была интуиция, которая привела меня к написанию функции так, как я это сделал. Все остальные варианты по существу требуют двух логически последовательных операций.
Как насчет этого…
inline bool Compare3(bool greater, int p1, int p2)
{
return (!greater != !(p1 <= p2)) | (p1 == p2);
}
или же
inline bool Compare4(bool greater, int p1, int p2)
{
return (greater ^ (p1 <= p2)) | (p1 == p2);
}