标签: branch-prediction

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

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

我读过的所有内容似乎都表明分支错误预测总会导致整个管道被刷新,这意味着浪费了很多周期.我从来没有听到任何人提到短期if条件的任何例外情况.

这似乎在某些情况下会非常浪费.例如,假设您有一个单独的if语句,其中包含一个非常简单的主体,该主体被编译为1个CPU指令.if子句将被编译为一条指令的条件跳转.如果CPU预测分支不被采用,则它将开始执行if-body指令,并可立即开始执行以下指令.现在,一旦if条件的评估已经到达管道的末端,也就是说,例如,12个周期之后,CPU现在知道它的预测是对还是错.如果它被错误预测,并且分支实际被占用,则CPU实际上只需要丢弃来自管道的1条指令(if-body中的指令).但是,如果它刷新整个管道,那么在以下指令中完成的所有工作也都被浪费了,并且必须无缘无故地重复.这是一个深度流水线架构上浪费的大量周期.

那么现代CPU有没有任何机制可以只丢弃短if体内的少数指令？或者它真的冲洗整个管道？如果是后者,那么我认为使用条件移动指令会获得更好的性能.顺便说一下,有没有人知道现代编译器是否善于将短if语句转换为cmov指令？

大多数(如果不是全部)现代处理器都使用一种称为"分支预测"的技术,用它来猜测if-then-else分支的方法.

我有一个问题考虑这个计划.假设我们有这段代码,没有特定的语言:

if(someCondition)
{
    // some action
    return someValue;
}
// some other action
return someOtherValue;

从逻辑上讲,该代码等同于此代码:

if(someCondition)
{
    // some action
    return someValue;
}
else
{
    // some other action
    return someOtherValue;
}

分支预测器将在第二个示例中"预测"分支,但第一个示例又如何呢？会猜到吗？什么将被加载到管道？是否有任何速度可以通过任何一个例子忽略块中实际代码的影响？

我的猜测,它取决于编译器:如果使用跳转实现语句(在汇编中),只有在寄存器中的compare标志置位时才进行跳转.现在汇编指令究竟是什么样的取决于编译器.除非每个编译器都有一种常用的处理方式,我怀疑它是否存在,否则这是编译器依赖的.在这种情况下,最新的Visual Studio C++和GC++编译器会发生什么？

作为hexafraction指出,以及如何返回值之间的关系someCondition确定...分支预测器可能不踢.我们只考虑true和false作为返回值.对于条件,让我们假设它是一个已经预定的字段,在函数内部或外部,局部变量和一些算术语句.

老实说,我并不怀疑条件是局部变量的情况与该字段已在同一函数中预定的情况之间存在很大差异.

我的代码经常调用具有多个(不可预测的)分支的函数.当我分析时,我发现它是一个小瓶颈,在条件JMP上使用了大部分CPU时间.

考虑以下两个函数,其中原始函数具有多个显式分支.

void branch_example_original(void* mem, size_t s)
{
    if(!(s & 7)) {
        /* logic in _process_mem_64 inlined */
    }
    else if(!(s & 3)) {
        /* logic in _process_mem_32 inlined */
    }
    else if(!(s & 1)) {
        /* logic in _process_mem_16 inlined */
    }
    else {
        /* logic in _process_mem_8 inlined */
    }
}

这是新功能,我尝试删除导致瓶颈的分支.

void branch_example_new(void* mem, size_t s)
{
    const fprocess_mem mem_funcs[] = {_process_mem_8, _process_mem_16, _process_mem_32, _process_mem_64};
    const uint32_t magic = 3 - !!(s & 7) - !!(s & …

从这里我知道英特尔近年来实施了几种静态分支预测机制:

• 80486年龄:永远不被采取

• Pentium4年龄:未采取后退/前锋

• 像Ivy Bridge,Haswell这样的新型CPU变得越来越无形,请参阅Matt G的实验.

英特尔似乎不想再谈论它,因为我在英特尔文档中找到的最新资料大约是十年前写的.

我知道静态分支预测(远远不是)比动态更重要,但在很多情况下,CPU将完全丢失,程序员(使用编译器)通常是最好的指南.当然,这些情况通常不是性能瓶颈,因为一旦频繁执行分支,动态预测器就会捕获它.

由于英特尔不再在其文档中明确声明动态预测机制,因此GCC的builtin_expect()只能从热路径中删除不太可能的分支.

我不熟悉CPU的设计,我不知道究竟是什么机制,目前英特尔使用其静态预测,但我还是觉得英特尔的最佳机制应该清楚地记录他的CPU",我打算去当动态预测失败,向前或向后',因为通常程序员是当时最好的指南.

更新:
我发现你提到的主题逐渐超出我的知识范围.这里涉及一些动态预测机制和CPU内部细节,我在两三天内无法学习.所以请允许我暂时退出你的讨论并充电.
这里仍然欢迎任何答案,也许会帮助更多人

一些参考：

_{这是对为什么处理排序数组比处理未排序数组更快？}

_{我发现在r标签中与分支预测有些相关的唯一帖子是为什么采样矩阵行很慢？}

问题说明：

我正在调查是否处理排序后的数组比处理一个未排序的一个（相同测试的问题更快Java和C-第一连杆），看看是否分支预测是影响R以相同的方式。

请参阅下面的基准示例：

set.seed(128)
#or making a vector with 1e7
myvec <- rnorm(1e8, 128, 128)  

myvecsorted <- sort(myvec)

mysumU = 0
mysumS = 0

SvU <- microbenchmark::microbenchmark(
  Unsorted = for (i in 1:length(myvec)) {
    
    if (myvec[i] > 128) {
      mysumU = mysumU + myvec[i]
    }
    
  } ,
  Sorted = for (i in 1:length(myvecsorted)) {
    
    if (myvecsorted[i] > 128) {
      mysumS = mysumS + myvecsorted[i]
    }
    
  } , …

X几乎99.9%的时间都是真的,但我也需要处理Y和Z. 虽然X条件的主体是空的,但我认为如果省略X条件,它应该比检查2个其他条件Y和Z更快.你怎么看？

if (likely(X))
{
}
else if (unlikely(Y))
{
...
}
else if (unlikely(Z))
{
...
}

我在if条件旁边看到了这条评论:

// branch prediction favors most often used condition

在JavaFX SkinBase类的源代码中.

protected double computeMinWidth(double height, double topInset, double rightInset, double bottomInset, double leftInset) {

    double minX = 0;
    double maxX = 0;
    boolean firstManagedChild = true;
    for (int i = 0; i < children.size(); i++) {
        Node node = children.get(i);
        if (node.isManaged()) {
            final double x = node.getLayoutBounds().getMinX() + node.getLayoutX();
            if (!firstManagedChild) {  // branch prediction favors most often used condition
                minX = Math.min(minX, x);
                maxX …

我只是偶然发现了这个问题,我真的很好奇,如果现代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 …

Linux 定义了一个BX在支持它的 CPU上使用的汇编宏，这让我怀疑有一些性能原因。

这个答案和Cortex-A7 MPCore 技术参考手册也指出它有助于分支预测。

然而，我的基准测试工作未能发现与 ARM1176、Cortex-A17、Cortex-A72 和 Neoverse-N1 cpu 的性能差异。

有没有因此任何理由，更喜欢BX过MOV pc,上了MMU的CPU，并实现了32位ARM指令集，比Thumb代码交互等？

编辑添加基准代码，全部对齐到 64 字节：

执行无用的计算lr并使用返回BX：

div_bx
        mov  r9, #2
        mul  lr, r9, lr
        udiv lr, lr, r9
        mul  lr, r9, lr
        udiv lr, lr, r9
        bx   lr

在另一个寄存器上执行无用的计算并使用BX以下方法返回：

div_bx2
        mov  r9, #2
        mul  r3, r9, lr
        udiv r3, r3, r9
        mul  r3, r9, r3
        udiv r3, r3, r9
        bx   lr …