我有一个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.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
现在，执行测试的实际代码可能使用上述两个函数的内联版本，因此这可能是要分析的错误代码。话虽如此，我在Compare（）中看到了一个jmp命令，所以我认为这意味着它正在分支。如果是这样，我想这个问题变成了：当我将a[i]从rand（）%2更改为true（或false时，为什么分支预测器没有提高Compare（）的性能？
编辑2：我用“分支”代替了“分支预测”，以使我的帖子更明智。
我想我明白了大部分。
当我在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（）。我想我可以发布定时代码的程序集。似乎有足够的理由认为函数如何内联可能会导致这种情况，所以我很满意在这里结束我的调查。我将在我的应用程序中用Compare2（）替换Compare（）。
感谢您的许多有用的评论。
编辑：我应该补充一点，Compare2胜过所有其他版本的可能原因是处理器能够并行执行这两个比较。这是我编写函数的直觉。所有其他变体本质上都需要两个逻辑串行操作。
我编写了一个名为Celero的C库，旨在测试此类优化和替代方案。（无耻的自我推销：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似乎是此微优化的最佳选择。
编辑：
Compare2 Assembly（最佳情况）：
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]
Compare3 Assembly（次佳情况）：
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
这个怎么样…
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);
}
