标签: branch-prediction

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

在"英特尔手册"第3卷中,它包含硬件事件计数器的说明:

BACLEAR_FORCE_IQ

计算指令队列强制BACLEAR的次数. IQ还负责基于由L2分支预测单元提供的静态方案和动态数据来提供条件分支预测方向.如果在目标阵列中找不到条件分支目标并且IQ预测分支被采用,则IQ将强制分支地址计算器发出BACLEAR.BAC声明的每个BACLEAR在指令获取管道中产生大约8个周期的气泡.

我一直以为分支地址计算器执行静态预测算法(当分支目标缓冲区不包含分支条目时)？

任何人都可以确认上述哪两个是正确的？我找不到任何东西.

该GCC手册仅示出了其中__builtin_expect()被置于围绕"如果"语句的所有条件的示例.

我还注意到GCC不会抱怨,如果我使用它,例如,使用三元运算符,或任何任意积分表达式,即使是未在分支上下文中使用的表达式.

所以,我想知道它的实际使用的基本限制是什么.

在这样的三元运算中使用时是否会保持其效果:

int foo(int i)
{
  return __builtin_expect(i == 7, 1) ? 100 : 200;
}

那么这个案子呢:

int foo(int i)
{
  return __builtin_expect(i, 7) == 7 ? 100 : 200;
}

还有这个:

int foo(int i)
{
  int j = __builtin_expect(i, 7);
  return j == 7 ? 100 : 200;
}

在以下伪代码中:

if (rdtscp supported by hardware) {
    Invoke "rdtscp" instruction
} else {
    Invoke "rdtsc" instruction
}

假设CPU不支持该rdtscp指令,因此我们回退到else语句.

如果CPU错误预测分支,指令管道是否可能尝试执行rdtscp并抛出Illgal Instruction错误？

最后一个分支记录是指寄存器对(MSR)的集合,它存储与最近执行的分支相关的源和目标地址.http://css.csail.mit.edu/6.858/2012/readings/ia32/ia32-3b.pdf文档提供了更多信息,以备您感兴趣.

• a)有人可以知道LBR会减慢程序执行程序执行的程度 - CPU和IO密集型吗？
• b)当LBR跟踪开启时,是否将分支预测关闭？

我正在写一些音频代码,基本上所有东西都是微小的循环.我理解它们的分支预测失败是一个足够大的性能问题,我很难保持代码分支免费.但是到目前为止,只有这一点可以带我,这让我想知道不同种类的分支.

在c ++中,条件分支到固定目标:

int cond_fixed(bool p) {
    if (p) return 10;
    return 20;
}

并且(如果我正确理解了这个问题),无条件分支到变量目标:

struct base {
    virtual int foo() = 0;
};

struct a : public base {
    int foo() { return 10; }
};

struct b : public base {
    int foo() { return 20; }
};

int uncond_var(base* p) {
    return p->foo();
}

是否存在性能差异？在我看来,如果两种方法中的一种明显比另一种方法快,编译器只会将代码转换为匹配.

对于分支预测非常重要的情况,有关性能的详细信息对于了解有用吗？

编辑:实际操作x : 10 ? 20只是一个占位符.分支之后的实际操作至少足够复杂,以至于两者都是低效的.此外,如果我有足够的信息可以合理使用__builtin_expect,在这种情况下,分支预测将不是问题.

我目前正在查看CPU管道的各个部分,它们可以检测分支错误预测.我发现这些是:

1. 分支目标缓冲区(BPU CLEAR)
2. 分支地址计算器(BA CLEAR)
3. 跳转执行单元(这里不确定信号名称？)

我知道2和3检测到了什么,但我不明白在BTB中检测到了什么错误预测.BAC检测BTB错误地预测非分支指令的分支的位置,其中BTB未能检测到分支,或者BTB错误预测了x86 RET指令的目标地址.执行单元评估分支并确定它是否正确.

在分支目标缓冲区中检测到什么类型的错误预测？究竟在这里发现了什么错误预测？

我能找到的唯一线索是英特尔开发者手册第3卷(底部的两个BPU CLEAR事件计数器):

BPU在错误地认为未采取分支后预测了一个分支.

这似乎暗示预测并非"同步",而是"异步",因此"在错误地假设"之后？

更新:

Ross,这是CPU分支电路,来自最初的英特尔专利(如何用于"阅读"？):

我在任何地方都看不到"分支预测单位"？读过这篇论文的人会认为"BPU"是将BTB电路,BTB缓存,BAC和RSB分组在一起的懒惰方式吗？

所以我的问题仍然存在,哪个组件会引发BPU CLEAR信号？

如果我理解正确的分支(x86),处理器有时会推测性地采用代码路径并执行指令并"取消"错误路径的结果.如果错误的代码路径中的操作非常昂贵,例如导致高速缓存未命中的内存读取或某些昂贵的数学运算,该怎么办？处理器是否会提前尝试执行昂贵的操作？处理器通常如何处理这个问题？

if (likely) {
    // do something lightweight (addition, subtraction, etc.)
} else {
    // do something expensive (cache-miss, division, sin/cos/tan etc.)
}

在代码的关键部分考虑条件函数调用时,我发现gcc和clang都会在调用中分支.例如,对于以下(通常是微不足道的)代码:

int32_t __attribute__((noinline)) negate(int32_t num) {
    return -num;
}

int32_t f(int32_t num) {
    int32_t x = num < 0 ? negate(num) : num;
    return 2*x + 1;
}

GCC和clang都基本上编译如下:

.global _f
_f:
    cmp     edi, 0
    jg      after_call
    call    _negate
after_call:
    lea     rax, [rax*2+1]
    ret

这让我想到:如果x86有一个像ARM这样的条件调用指令怎么办？想象一下,如果有这样的指令"ccall cc "与语义如cmov cc.然后你可以这样做:

.global _f
_f:
    cmp     edi, 0
    ccalll  _negate
    lea     rax, [rax*2+1]
    ret

虽然我们无法避免分支预测,但我们确实消除了分支.也就是说,在实际的GCC/clang输出中,我们被迫分支,无论是否num < 0.如果num < 0我们必须分支两次.这似乎很浪费.

现在这样的指令在amd64中不存在,但我设计了一种模拟这种指令的方法.我通过分解call func其组成部分来做到这一点:( push rip技术上很好[rip+label_after_call_instruction])然后jmp …

我是否理解这一点,if语句更依赖于分支预测,而v-table查找更依赖于分支目标预测？关于v表,没有"分支预测",只有目标预测？

试图了解CPU如何处理v表.