标签: branch-prediction

我正在阅读那个分支错误预测可能是应用程序性能的热门瓶颈.正如我所看到的,人们经常会显示汇编代码来揭示问题,并指出程序员通常可以预测分支在大多数时间内的位置并避免分支错误预测.

我的问题是:

1-是否可以使用某种高级编程技术(即无汇编)来避免分支错误预测？

2-我应该记住用高级编程语言生成分支友好的代码(我最感兴趣的是C和C++)？

欢迎使用代码示例和基准测试!

有没有可行的分支预测提示方法？请考虑以下示例:

  if (unlikely_condition) {
    /* ..A.. */
  } else {
    /* ..B.. */
  }

这有什么不同于:

  if (!unlikely_condition) {
    /* ..B.. */
  } else {
    /* ..A.. */
  }

或者是使用编译器特定提示的唯一方法？(例如海湾合作委员会的__builtin_expect)

编译器会根据if条件的顺序对条件进行不同的处理吗？

我最近询问了有关Code Review 的问题,以检查名为QuickMergeSort的排序算法.我不会详细介绍,但在某些时候算法执行内部mergesort:它不是使用额外的内存来存储要合并的数据,而是交换元素以与原始序列的另一部分中的元素合并,这不是否则就合并而言.这是我关注的算法的一部分:执行合并的函数:

template<
    typename InputIterator1,
    typename InputIterator2,
    typename OutputIterator,
    typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result, Compare compare={})
    -> void
{
    for (; first1 != last1; ++result) {
        if (first2 == last2) {
            std::swap_ranges(first1, last1, result);
            return;
        }

        if (compare(*first2, *first1)) {
            std::iter_swap(result, first2);
            ++first2;
        } else {
            std::iter_swap(result, first1);
            ++first1;
        }
    }
    // first2 through last2 are already in the right spot
}

该函数改编自libc …

让A是包含奇数个零和一的数组.如果n是大小A,则A构造为使得第一ceil(n/2)元素0和剩余元素1.

所以如果n = 9,A看起来像这样:

0,0,0,0,0,1,1,1,1

目标是找到1s数组中的总和,我们使用此函数执行此操作:

s = 0;
void test1(int curIndex){
    //A is 0,0,0,...,0,1,1,1,1,1...,1

    if(curIndex == ceil(n/2)) return;

    if(A[curIndex] == 1) return;

    test1(curIndex+1);
    test1(size-curIndex-1);

    s += A[curIndex+1] + A[size-curIndex-1];

}

对于给出的问题,这个函数相当愚蠢,但它是一个不同函数的模拟,我希望看起来像这样,并产生相同数量的分支误预测.

以下是整个实验代码:

#include <iostream>
#include <fstream>

using namespace std;


int size;
int *A;
int half;
int s;

void test1(int curIndex){
    //A is 0,0,0,...,0,1,1,1,1,1...,1

    if(curIndex == half) return;
    if(A[curIndex] == …

从我的大学课程中,我听说,按照惯例,最好放置更多可能的条件if而不是in else,这可能有助于静态分支预测器.例如:

if (check_collision(player, enemy)) { // very unlikely to be true
    doA();
} else {
    doB();
}

可以改写为:

if (!check_collision(player, enemy)) {
    doB();
} else {
    doA();
}

我发现了一篇博客文章分支模式,使用GCC,它更详细地解释了这种现象:

为if语句生成前向分支.使它们不可能被采用的基本原理是处理器可以利用分支指令之后的指令可能已经被放置在指令单元内的指令缓冲器中的事实.

旁边,它说(强调我的):

在编写if-else语句时,总是使"then"块比else块更可能被执行,因此处理器可以利用已经放在指令获取缓冲区中的指令.

最终,有一篇由英特尔,分支和循环重组编写的文章,以防止错误预测,其中总结了两个规则:

当微处理器遇到分支时没有收集数据时使用静态分支预测,这通常是第一次遇到分支.规则很简单:

• 正向分支默认不采用
• 向后分支默认采用

为了有效地编写代码以利用这些规则,在编写if-else或switch语句时,首先检查最常见的情况,然后逐步处理最不常见的情况.

据我所知,这个想法是流水线CPU可以遵循指令缓存中的指令,而不会通过跳转到代码段内的另一个地址来破坏它.但是,我知道,在现代CPU微体系结构的情况下,这可能会过于简单化.

但是,看起来GCC不尊重这些规则.鉴于代码:

extern void foo();
extern void bar();

int some_func(int n)
{
    if (n) {
        foo();
    }
    else {
        bar();
    }
    return 0; …

我写的代码看起来像以下......

if(denominator == 0){
    return false;
}
int result = value / denominator;

...当我考虑CPU中的分支行为时.

/sf/answers/785953171/ 这个答案说CPU将尝试正确猜测分支将走向哪个方向,并且如果发现分支错误地猜测分支,那么只停下该分支停止.

但是如果CPU预测上面的分支不正确,它将在以下指令中除以零.虽然这不会发生,我想知道为什么？CPU是否实际执行除零并在执行任何操作之前等待分支是否正确,还是可以告诉它在这些情况下不应该继续？这是怎么回事？

我目前编码的一些C99标准库字符串函数高度优化的版本,例如strlen(),memset()等等,采用x86-64的组件,SSE-2指令.

到目前为止,我已经在性能方面取得了很好的成绩,但是当我尝试优化更多时,我有时会遇到奇怪的行为.

例如,添加或甚至删除一些简单的指令,或者只是重新组织一些用于跳转的本地标签会完全降低整体性能.在代码方面绝对没有理由.

所以我的猜测是代码对齐存在一些问题,和/或有错误预测的分支.

我知道,即使使用相同的架构(x86-64),不同的CPU也有不同的分支预测算法.

但是,在开发x86-64的高性能时,是否存在一些关于代码对齐和分支预测的一般建议？

特别是关于对齐,我应该确保跳转指令使用的所有标签都在DWORD上对齐吗？

_func:
    ; ... Some code ...
    test rax, rax
    jz   .label
    ; ... Some code ...
    ret
    .label:
        ; ... Some code ...
        ret

在前面的代码中,我之前应该使用align指令.label:,例如:

align 4
.label:

如果是这样,使用SSE-2时是否足以对齐DWORD？

关于分支预测,是否有一种"优先"的方式来组织跳转指令使用的标签,以帮助CPU,或者今天的CPU是否足够聪明,可以通过计算分支的计数来确定在运行时？

编辑

好的,这是一个具体的例子 - 这是strlen()SSE-2 的开始:

_strlen64_sse2:
    mov         rsi,    rdi
    and         rdi,    -16
    pxor        xmm0,   xmm0
    pcmpeqb     xmm0,   [ rdi ]
    pmovmskb    rdx,    xmm0
    ; ...

使用1000个字符串运行10'000'000次约为0.48秒,这很好.
但它不会检查NULL字符串输入.显然,我会添加一个简单的检查:

_strlen64_sse2:
    test       rdi,    rdi
    jz          .null
    ; ... …

由于对性能的巨大影响,我不知道我当前的桌面CPU是否有分支预测.当然可以.但各种ARM产品怎么样？iPhone或Android手机有分支预测吗？旧版的Nintendo DS？基于PowerPC的Wii怎么样？PS 3？

它们是否具有复杂的预测单元并不是那么重要,但是如果它们至少具有一些动态预测,以及它们是否在预期分支之后执行一些指令.

具有分支预测的CPU的截止点是多少？几十年前的手持计算器显然没有一个,而我的桌面确实没有.但是,任何人都能更清楚地概述可以预期动态分支预测的位置吗

如果不清楚,我说的是条件变化的预测类型,在运行时改变预期的路径.

在最新的英特尔软件开发手册中,它描述了两个操作码前缀:

Group 2 > Branch Hints

    0x2E: Branch Not Taken
    0x3E: Branch Taken

这些允许跳转指令的显式分支预测(像操作码一样Jxx)

我记得在几年前读过x86显式分支预测本质上是gccs分支谓词内在函数上下文中的无操作.

我现在还不清楚这些x86分支提示是否是一个新功能,或者它们在实践中是否基本上是无操作.

任何人都可以清除这个吗？

(那就是:gccs分支预测函数会生成这些x86分支提示吗？ - 并且当前的Intel CPU不会忽略它们吗？ - 这是什么时候发生的？)

更新:

我创建了一个快速测试程序:

int main(int argc, char** argv)
{
    if (__builtin_expect(argc,0))
        return 1;

    if (__builtin_expect(argc == 2, 1))
        return 2;

    return 3;
}

拆卸以下内容:

00000000004004cc <main>:
  4004cc:   55                      push   %rbp
  4004cd:   48 89 e5                mov    %rsp,%rbp
  4004d0:   89 7d fc                mov    %edi,-0x4(%rbp)
  4004d3:   48 89 75 f0             mov    %rsi,-0x10(%rbp)
  4004d7:   8b 45 fc                mov    -0x4(%rbp),%eax
  4004da: …

编辑:我的混乱是因为肯定通过预测采取了哪个分支,你是否也在有效地进行目标预测？

这个问题与我关于这个主题的第一个问题有着内在的联系:

分支预测与分支目标预测

看看接受的答案:

无条件分支,固定目标

• 无限循环
• goto 声明
• break或continue声明
• if/else声明的'then'子句结束(跳过该else子句)
• 非虚函数调用

无条件分支,变量目标

• 从函数返回
• 虚函数调用
• 函数指针调用
• switch 语句(如果编译成跳转表)

条件分支,固定目标

• if 声明
• switch声明(如果汇编成一系列if/else声明)
• 循环条件测试
• 在&&与||运营商
• 三元?:运算符

条件分支,变量目标

• 在正常情况下不太可能出现,但编译器可能会综合一个作为优化,结合上述两种情况.例如,在x86上,编译器可以将代码优化if (condition) { obj->VirtualFunctionCall(); }为条件间接跳转,就像jne *%eax它由于尾调用优化而出现在函数末尾一样.

如果我有以下代码:

if(something){
    //a
}
else{
    //b
}

(BP ="分支预测"和BTP ="分支目标预测")

其非常明显的BP用于评估条件something.但是,我试图了解BTP是否也参与确定分支中发生的情况a.BTP是否也恰好确定位于branch a/ 的代码的地址b,具体取决于BP的结果？

我问这个维基百科页面(http://en.wikipedia.org/wiki/Branch_target_predictor):

在计算机体系结构中,分支目标预测器是处理器的一部分,其在由处理器的执行单元计算分支指令的目标之前预测所采用的条件分支或无条件分支指令的目标.

它表明BTP用于在预测条件后预测目标.

1)有人可以澄清以上内容吗？

第二个相关问题 - BP和BTP如何与CPU的fetch/decode/execute/write-back管道交互方式不同？BP是从获取还是解码阶段开始的？在条件代码的执行阶段之后,我们可以检查预测是否正确并更新分支预测缓存.

2)BTP如何处理fetch/decode/execute/write-back …