我有一个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 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
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,-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,%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命令,所以我认为这意味着它是分支.如果是这样,我猜这个问题就变成了：为什么当我将一个[i]从rand()％2更改为true(或者对于该事情是false)时,为什么分支预测器不能提高Compare()的性能？
编辑2：我用“分支”代替“分支预测”,使我的帖子更加明智.
解决方法
我写了一个名为Celero的C库,旨在测试这样的优化和替代方案. (无耻自我推销：
https://github.com/DigitalInBlue/Celero)
我使用以下代码运行您的案例：
class StackOverflowFixture : public celero::TestFixture
{
public:
StackOverflowFixture()
{
}
inline bool NoOp(bool greater,int p2)
{
return true;
}
inline bool Compare(bool greater,int p2)
{
if(greater == true)
{
return p1>=p2;
}
return p1<=p2;
}
inline bool Compare2(bool greater,int p2)
{
bool ret[2] = {p1<=p2,p1>=p2};
return ret[greater];
}
inline bool Compare3(bool greater,int p2)
{
return (!greater != !(p1 <= p2)) | (p1 == p2);
}
inline bool Compare4(bool greater,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,5000000)
{
celero::DoNotOptimizeAway(Compare(rand()%2,Compare2,5000000)
{
celero::DoNotOptimizeAway(Compare2(rand()%2,Compare3,5000000)
{
celero::DoNotOptimizeAway(Compare3(rand()%2,Compare4,5000000)
{
celero::DoNotOptimizeAway(Compare4(rand()%2,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装配(最好的情况)：
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