标签: branch-prediction

我有一个简单的问题,假设我有以下代码,并且它以类似的方式重复10次,例如.

if blah then
    number = number + 2^n
end if

评估会更快吗？

number = number + blah*2^n?

这也带来了问题,你可以将一个布尔值乘以一个整数(虽然我不确定从2 ^ n返回的类型,是整数还是unsigned..etc)？(我在Ada工作,但是我们可以尝试概括一下吗？)

编辑:对不起我应该澄清我正在考虑2的力量n,并且我把c放在那里因为我对将来自己的学习感兴趣如果我遇到c中的这个问题并且我认为还有更多的c那些程序员在这些板上然后Ada(我假设你知道这意味着什么),但是我目前的问题是Ada语言,但问题应该是相当语言独立的(我希望).

我想知道如何为C64,C++或汇编语言编写x64处理器的高效跳转表.输入事先已知,但无法通过算法预测.假设我可以在输入流中看起来像我想要的那样遥远,有什么办法可以动态地告诉CPU下一个分支将要去哪个地址？

基本上,我想以编程方式更新分支目标缓冲区.但是,如果程序员事先知道下一个分支在哪里查看数据但处理器无法从过去的模式中确定这一点,那么我会解决任何允许我避免冲洗管道的问题.

意识到这是一个非常具体的问题,我可能无法正确地传达它,这里有一些替代措辞:

hbr在Cell处理器上是否有x64等效于分支的提示？

cmp像Itanium一样,它比条件分支更早地移动程序集是否有帮助？

间接跳转的预测目标是否基于寄存器值而不是最后使用的地址？

谢谢!

我的想法是给出一个优雅的代码示例,它将演示指令缓存限制的影响.我编写了以下代码,使用模板元编程创建了大量相同的函数.

volatile int checksum;
void (*funcs[MAX_FUNCS])(void);

template <unsigned t> 
__attribute__ ((noinline)) static void work(void) { ++checksum; }

template <unsigned t> 
static void create(void) { funcs[t - 1] = &work<t - 1>; create<t - 1>(); }

template <> void create<0>(void) {  }

int main()
{
    create<MAX_FUNCS>();

    for (unsigned range = 1; range <= MAX_FUNCS; range *= 2)
    {
        checksum = 0;
        for (unsigned i = 0; i < WORKLOAD; ++i)
        {
            funcs[i % range]();
        }
    }

    return 0;
}

外循环使用跳转表改变要调用的不同函数的数量.对于每个循环传递,WORKLOAD …

我switch在一些时间关键代码中有一个声明.我试图用它来优化它__builtin_expect,但它似乎没有起作用.我想知道是否有人可以告诉我,我是否遗漏了一些细节,或者编译器是否只是没有针对它进行优化.我在我的主机上尝试了以下内容:

int main() {
    volatile int v=0;
    long i = 0;

    for (i=0; i<1000000000L; i++) {
            switch(__builtin_expect(v, EXPT)) {
            case 7:
                    v=7;
                    break;
            default:
                    v=7;
                    break;
            }
    }
    return v;
}

然后我编译并运行如下:

~/code/builtinexpect> gcc bie.c -o bie -D EXPT=0 && time ./bie 

real    0m2.092s  
user    0m2.086s
sys     0m0.000s
~/code/builtinexpect> gcc bie.c -o bie -D EXPT=7 && time ./bie 

real    0m2.092s
user    0m2.086s
sys     0m0.000s

我使用的是GCC 4.5.1版.

我有一个循环运行一遍又一遍。该循环内的逻辑取决于程序所处的模式。为了提高性能，我认为可以初始化函数指针数组，functionPtr[]，这样就可以调用运行正确逻辑的 functionPtrmode。循环将在许多周期内保持相同的模式（数量未知，但有数千个）。该程序仅在 intel x64 机器上运行，不需要可移植性。

我希望 CPU 能够利用分支预测，但由于我的分支不是有条件的（在程序集级别上），但分支的位置确实取决于一个变量（functionPtr+mode）。CPU 会尝试计算 functionPtr+mode 并在管道中开始提取这些指令吗？

好吧，所以我知道，如果特定的条件分支有一个需要时间来计算的条件（例如内存访问），CPU 会假定一个条件结果并沿着该路径推测执行。但是，如果沿着该路径弹出另一个缓慢的条件分支（当然，假设第一个条件尚未解决并且 CPU 无法提交更改），会发生什么情况？难道CPU只是在猜测里面猜测吗？如果最后一个条件预测错误但第一个条件没有预测会发生什么？难道只是一路回滚吗？

我正在谈论这样的事情：

if (value_in_memory == y){
   // computations
   if (another_val_memory == x){
      //computations
   }
}

我写了这个非常简单的 Rust 函数：

fn iterate(nums: &Box<[i32]>) -> i32 {
    let mut total = 0;
    let len = nums.len();
    for i in 0..len {
        if nums[i] > 0 {
            total += nums[i];
        } else {
            total -= nums[i];
        }
    }

    total
}

我编写了一个基本的基准测试，它使用一个有序数组和一个无序数组调用该方法：

fn criterion_benchmark(c: &mut Criterion) {
    const SIZE: i32 = 1024 * 1024;

    let mut group = c.benchmark_group("Branch Prediction");

    // setup benchmarking for an ordered array
    let mut ordered_nums: Vec<i32> = vec![];
    for i in 0..SIZE {
        ordered_nums.push(i - …

C++20 具有指导代码生成的方便[[likely]]/[[unlikely]]属性。例如，您可以指定一个分支可能被以下人员采用：

if (b) [[likely]] { /*...*/ }

同样，可以在switchstatements 中使用这些属性。. . 不知何故？ 文档建议使用以下示例（稍微格式化）：

if (b) [[likely]] { /*...*/ }

其含义显然是[[likely]]/[[unlikely]]在case语句之前。互联网似乎几乎普遍宣传这种用法。

但是，请考虑以下类似的代码（我所做的只是将 the[[likely]]移到 other case）：

switch (i) {
    case 1:
        [[fallthrough]];
    [[likely]] case 2:
        return 1;
}

这无法在 clang 上编译！虽然这可能与编译器错误有关[[fallthrough]]，但它让我查看了标准。在相关的标准有如下的例子（见§VII）：

鼓励实现针对正在执行的情况进行优化（例如，以下代码中的值为 1）：

switch (i) {
    [[likely]] case 1:
        [[fallthrough]];
    case 2:
        return 1;
}

也就是说，该属性出现在案例标签之后，而不是之前。

所以 。. . …

我是用于程序分析的cachegrind的长期用户，最近又再次查看了官方文档： https: //valgrind.org/docs/manual/cg-manual.html

其中多次引用了 2000 年代中期的 CPU 模型、实现决策和仿真模型，并且还声明“现代”处理器上的某些行为发生了变化：

LL 高速缓存通常会复制 L1 高速缓存的所有条目[...]这是奔腾芯片上的标准，但 AMD Opterons、Athlons 和 Durons 使用专用的 LL 高速缓存[...]

Cachegrind 模拟了 2004 年左右主流桌面/服务器处理器的典型分支预测器。

较新的处理器具有更好的分支预测器 [...] Cachegrind 的预测器设计故意保守，以便代表大量已安装的处理器，这些处理器早于更复杂的间接分支预测器的广泛部署。特别是，最新型号的 Pentium 4s (Prescott)、Pentium M、Core 和 Core 2 具有比 Cachegrind 建模更复杂的间接分支预测器。

现在我想知道

• 在最新一代 CPU 上进行开发时，有多少选择在 2021 年仍然适用，
• cachegrind 的实现是否已更新以反映最新的 CPU，但手册已过时，
• 由于对遗留行为的模拟，cachegrind 在现代 CPU 上是否会显示出偏差的结果。

任何见解都将不胜感激！

让我们尝试定义一个返回两个值 x 和 y 中的最大值的函数。这些公式有效的充分条件是，对于有符号整数，\xe2\x80\x932^30 <= x, y <= 2^30 \xe2\x80\x93 1，对于无符号整数，0 <= x, y <= 2^31 \xe2\x80\x93 1（即，只需要处理有效减少一位的缩小整数范围）。最通用（且最简单）的实现是：

int max(int x, int y) {\n    return (x > y) ? x : y\n}\n

在 Pentium Pro 之前，这将是 x86 中生成的程序集：

max:  # GCC -O3 -march=pentium -m32\n  mov eax, DWORD PTR [esp+8]\n  cmp eax, DWORD PTR [esp+4]\n  jge .L4\n  mov eax, DWORD PTR [esp+4]\n.L4:\n  ret\n

但从 Pentium Pro 开始，CMOVcc r32,r/m引入了一条新指令，它根据某些指定的状态标志执行条件移动： …