分支预测免费？

Question

我只是偶然发现了这个问题,我真的很好奇,如果现代CPU(当前的CPU,也许是移动的CPU(嵌入式))在下面的情况下实际上没有分支成本.

我们说我们有这个:

x += a; // let's assume they are both declared earlier as simple ints  
if (flag)  
   do A  // let's assume A is not the same as B  
else  
   do B  // and of course B is different than A  

2.与此相比:

if (flag)  
{  
  x += a   
  do A  
}  
else  
{  
   x += a  
   do B  
}

假设A和B管道指令(获取,解码,执行等)完全不同:

1. 第二种方法会更快吗？

2. CPU是否足够聪明,无论标志是什么,下一条指令都是相同的(因此,由于分支未命中预测,它们不必为此丢弃流水线级)？

注意:

在第一种情况下,CPU没有选择,但放弃做的前几个流水线阶段A或做B如果分支预测小姐发生了,因为他们是不同的.我看到第二个例子作为某种方式延迟分支如:"我要检查那个标志,即使我不知道标志,我可以继续下一条指令,因为它是相同的,无论标志是什么是的,我已经有了下一条指令,我可以使用它."

编辑:
我做了一些研究,我有一些不错的结果.你会如何解释这种行为？对不起,我的最新编辑,但据我所知,我有一些缓存问题,这些是更准确的结果和代码示例,我希望.

这是使用-O3使用gcc版本4.8.2(Ubuntu 4.8.2-19ubuntu1)编译的代码.

情况1.

#include <stdio.h>

extern int * cache;
extern bool * b;
extern int * x;
extern int * a;
extern unsigned long * loop;

extern void A();
extern void B();

int main()
{
    for (unsigned long i = 0; i < *loop; ++i)
    {
        ++*cache;

        *x += *a;

        if (*b)
        {
            A();
        }
        else
        {
            B();
        }
    }

    delete b;
    delete x;
    delete a;
    delete loop;
    delete cache;

    return 0;
}

int * cache = new int(0);
bool * b = new bool(true);
int * x = new int(0);
int * a = new int(0);
unsigned long * loop = new unsigned long(0x0ffffffe);

void A() { --*x; *b = false; }
void B() { ++*x; *b = true; }

案例2

#include <stdio.h>

extern int * cache;
extern bool * b;
extern int * x;
extern int * a;
extern unsigned long * loop;

extern void A();
extern void B();

int main()
{
    for (unsigned long i = 0; i < *loop; ++i)
    {
        ++*cache;

        if (*b)
        {
            *x += *a;
            A();
        }
        else
        {
            *x += *a;
            B();
        }
    }

    delete b;
    delete x;
    delete a;
    delete loop;
    delete cache;

    return 0;
}

int * cache = new int(0);
bool * b = new bool(true);
int * x = new int(0);
int * a = new int(0);
unsigned long * loop = new unsigned long(0x0ffffffe);

void A() { --*x; *b = false; }
void B() { ++*x; *b = true; }

两种方法的-O3版本之间几乎没有明显区别,但没有-O3,第二种情况的运行速度稍快,至少在我的机器上运行.我已经测试了没有-O3和loop = 0xfffffffe.
最佳时间:
alin @ ubuntu:〜/ Desktop $ time./ 1

真正的0m20.231s
用户0m20.224s
sys 0m0.020s

alin @ ubuntu:〜/桌面$ time ./2

实际0m19.932s
用户0m19.890s
sys 0m0.060s

Answer 1

这有两个部分:

首先,编译器是否优化了这个？

我们来做一个实验:

test.cc

#include <random>
#include "test2.h"

int main() {
  std::default_random_engine e;
  std::uniform_int_distribution<int> d(0,1);
  int flag = d(e);

  int x = 0;
  int a = 1;

  if (flag) {
    x += a;
    doA(x);
    return x;
  } else {
    x += a;
    doB(x);
    return x;
  }
}

test2.h

void doA(int& x);
void doB(int& x);

test2.cc

void doA(int& x) {}
void doB(int& x) {}

test2.cc和test2.h都只是为了防止编译器优化掉一切.编译器无法确定没有副作用,因为这些函数存在于另一个翻译单元中.

现在我们编译成汇编:

gcc -std=c++11 -S test.cc

让我们跳到有趣的程序集部分:

  call  _ZNSt24uniform_int_distributionIiEclISt26linear_congruential_engineImLm16807ELm0ELm2147483647EEEEiRT_
  movl  %eax, -40(%rbp); <- setting flag
  movl  $0, -44(%rbp);   <- setting x
  movl  $1, -36(%rbp);   <- setting a
  cmpl  $0, -40(%rbp);   <- first part of if (flag)
  je    .L2;             <- second part of if (flag)
  movl  -44(%rbp), %edx  <- setting up x
  movl  -36(%rbp), %eax  <- setting up a
  addl  %edx, %eax       <- adding x and a
  movl  %eax, -44(%rbp)  <- assigning back to x
  leaq  -44(%rbp), %rax  <- grabbing address of x
  movq  %rax, %rdi       <- bookkeeping for function call
  call  _Z3doARi         <- function call doA
  movl  -44(%rbp), %eax
  jmp   .L4
.L2:
  movl  -44(%rbp), %edx  <- setting up x
  movl  -36(%rbp), %eax  <- setting up a
  addl  %edx, %eax       <- perform the addition
  movl  %eax, -44(%rbp)  <- move it back to x
  leaq  -44(%rbp), %rax  <- and so on
  movq  %rax, %rdi
  call  _Z3doBRi
  movl  -44(%rbp), %eax
.L4:

所以我们可以看到编译器没有优化它.但我们实际上并没有要求它.

g++ -std=c++11 -S -O3 test.cc

然后有趣的集会:

main:
.LFB4729:
  .cfi_startproc
  subq  $56, %rsp
  .cfi_def_cfa_offset 64
  leaq  32(%rsp), %rdx
  leaq  16(%rsp), %rsi
  movq  $1, 16(%rsp)
  movq  %fs:40, %rax
  movq  %rax, 40(%rsp)
  xorl  %eax, %eax
  movq  %rdx, %rdi
  movl  $0, 32(%rsp)
  movl  $1, 36(%rsp)
  call  _ZNSt24uniform_int_distributionIiEclISt26linear_congruential_engineImLm16807ELm0ELm2147483647EEEEiRT_RKNS0_10param_typeE
  testl %eax, %eax
  movl  $1, 12(%rsp)
  leaq  12(%rsp), %rdi
  jne   .L83
  call  _Z3doBRi
  movl  12(%rsp), %eax
.L80:
  movq  40(%rsp), %rcx
  xorq  %fs:40, %rcx
  jne   .L84
  addq  $56, %rsp
  .cfi_remember_state
  .cfi_def_cfa_offset 8
  ret
.L83:
  .cfi_restore_state
  call  _Z3doARi
  movl  12(%rsp), %eax
  jmp   .L80

这有点超出了我在程序集和代码之间干净地显示1对1关系的能力,但是您可以从对doA和doB的调用中看出,设置是常见的并且在if语句之外完成.(在线路上方.L83).所以,是的,编译器会执行此优化.

第2部分:

如果给出第一个代码,我们怎么知道CPU是否进行了这种优化？

我实际上并不知道有一种测试方法.所以我不知道.鉴于存在乱序和投机执行,我认为这是合理的.但证据是在布丁,我没有办法测试这个布丁.所以我不愿意以这种或那种方式提出索赔.

Answer 2

在当天,CPU明确地支持了类似的东西 - 在分支指令之后,无论分支是否实际被采用,下一条指令都将被执行(查找"分支延迟槽").

我很确定现代CPU只会将整个管道转储到分支错误预测上.如果编译器可以在编译时轻松完成,那么在执行时尝试进行优化是没有意义的.