微优化c ++比较功能

Question

我有一个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

现在,执行测试的实际代码可能正在使用上述两个函数的内联版本,因此有可能这可能是错误的分析代码.话虽如此,我看到一个jmp命令Compare(),所以我认为这意味着它是分支.如果是的话,我想这个问题就变成了:为什么分支预测不改善的性能Compare()时,我改变a[i]来自rand()%2于true(或false为此事)？

EDIT2:我用"分支"取代了"分支预测",使我的帖子更加明智.

Answer 1

我想我已经弄清楚了大部分内容。

当我在 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是处理器能够并行执行这两种比较。正是这种直觉引导我按照自己的方式编写了该函数。所有其他变体本质上都需要两个逻辑串行操作。