是否有导致 50% 分支预测未命中的代码？

Question

问题：

我想弄清楚如何编写代码（C 优先，ASM 仅当没有其他解决方案时）使分支预测在 50% 的情况下失误.

因此它必须是 "is imune" 与分支相关的编译器优化的一段代码，而且所有硬件分支预测都不应超过 50%（掷硬币）。更大的挑战是能够运行 多个 CPU 架构 上的代码并获得相同的 50% 未命中率。

我设法在 x86 平台上编写了 47% 分支未命中率 的代码。我怀疑丢失的 3% 可能来自：

其中有分支的程序启动开销（虽然很小）
探查器开销 - 基本上每次计数器读取都会引发中断，因此这可能会添加额外的可预测分支。
系统调用运行在后台包含循环和可预测的分支

我编写了自己的随机数生成器以避免调用其实现可能隐藏可预测分支的随机数。如果可用，它也可以使用 rdrand。延迟对我来说不重要。

题目：

我可以做得比我的代码版本更好吗？更好意味着获得更高的分支预测错误和所有 CPU 架构的相同结果。
这段代码可以预测吗？那是什么意思？

代码：

#include <stdio.h>
#include <time.h>

#define RDRAND
#define LCG_A   1103515245
#define LCG_C   22345
#define LCG_M   2147483648
#define ULL64   unsigned long long

ULL64 generated;

ULL64 rand_lcg(ULL64 seed)
{
#ifdef RDRAND
    ULL64 result = 0;
    asm volatile ("rdrand %0;" : "=r" (result));
    return result;
#else
    return (LCG_A * seed + LCG_C) % LCG_M;
#endif
}

ULL64 rand_rec1()
{
    generated = rand_lcg(generated) % 1024;

    if (generated < 512)
        return generated;
    else return rand_rec1();
}

ULL64 rand_rec2()
{
    generated = rand_lcg(generated) % 1024;

    if (!(generated >= 512))
        return generated;
    else return rand_rec2();
}

#define BROP(num, sum)                  \
    num = rand_lcg(generated);          \
    asm volatile("": : :"memory");      \
    if (num % 2)                        \
        sum += rand_rec1();             \
    else                                \
        sum -= rand_rec2();

#define BROP5(num, sum)     BROP(num, sum) BROP(num, sum) BROP(num, sum) BROP(num, sum) BROP(num, sum)
#define BROP25(num, sum)    BROP5(num, sum) BROP5(num, sum) BROP5(num, sum) BROP5(num, sum) BROP5(num, sum)
#define BROP100(num, sum)   BROP25(num, sum) BROP25(num, sum) BROP25(num, sum) BROP25(num, sum)

int main()
{
    int i = 0;
    int iterations = 500000;    
    ULL64 num = 0;
    ULL64 sum = 0;

    generated = rand_lcg(0) % 54321;

    for (i = 0; i < iterations; i++)
    {
        BROP100(num, sum);
        // ... repeat the line above 10 times
    }

    printf("Sum = %llu\n", sum);
}

更新 v1：

根据 usr 的建议，我通过在脚本中改变命令行中的 LCG_C 参数生成了各种模式。 我能够达到 49.67% BP 未命中。这足以满足我的目的，而且我有在各种架构上生成它的方法。

Answer 1

避免编译器优化的最简单方法是在另一个翻译单元中使用 void f(void) { } 和 void g(void) { } 虚拟函数，并禁用 link 时间优化。这将迫使 if (*++p) f(); else g(); 成为一个真正不可预测的分支，假设 p 指向一个随机布尔数组（这回避了 rand() 内部的分支预测问题 - 在测量之前这样做）

如果 for(;;) 循环给您带来问题，只需输入 goto。

请注意，评论中的 "loop unrolling trick" 有点误导。您实际上是在创建数千个分支。每个分支都将被单独预测，除了它们中的 none 可能会被预测，因为 CPU 根本无法容纳数千个不同的预测。这可能对您的真正目标有益，也可能不有益。

Answer 2

用字节填充一个数组，并编写一个循环来检查每个字节并根据字节的值进行分支。

现在仔细检查处理器的体系结构及其分支预测。填充数组的初始字节，以便在检查它们之后，处理器处于可预测的已知状态。从该已知状态，您可以确定下一个分支是否被预测为采用。设置下一个字节，使预测错误。再次，找出下一个分支是否被预测采用，并设置下一个字节以使预测错误等。

如果您也禁用中断（这可能会改变分支预测），您可能会接近 100% 错误预测的分支。

作为一个简单的例子，在具有 strong/weak 预测的旧 PowerPC 处理器上，在三个采用的分支之后它将始终处于状态 "strong taken" 并且一个未采用的分支将其更改为 "weak taken".如果您现在有一系列交替的未采用/采用分支，则预测总是错误的，并且会在弱未采用和弱采用之间切换。

这当然只适用于该特定处理器。大多数现代处理器会认为该序列几乎是 100% 可预测的。例如，他们可能使用两个独立的预测器；一种用于案例 "last branch was taken"，另一种用于案例 "last branch was not taken"。但是对于这样的处理器，不同的字节序列将给出相同的 100% 错误预测率。

Answer 3

如果你知道分支预测器是如何工作的，你就可以得到 100% 的错误预测。每次只取预测器的预期预测，反其道而行之。问题是我们不知道它是如何实现的。

我读到，典型的预测器能够预测 0,1,0,1 等模式。但我确信模式的长度是有限制的。我的建议是尝试给定长度（例如 4）的每个模式，看看哪个最接近您的目标百分比。您应该能够同时瞄准 50% 和 100%，并且非常接近。此分析需要针对每个平台进行一次或在运行次进行。

我怀疑分支总数的3%是像你说的那样在系统代码中。内核不会对纯 CPU 绑定的用户代码产生 3% 的开销。将调度优先级调到最大。

您可以通过生成一次随机数据并多次迭代相同的数据来将 RNG 从游戏中移除。分支预测器不太可能检测到这一点（尽管它显然可以）。

我将通过用我描述的零-一模式填充 bool[1 << 20] 来实现这一点。然后，您可以运行以下循环多次：

int sum0 = 0, sum1 = 0;
for (...) {
 //unroll this a lot
 if (array[i]) sum0++;
 else sum1++;
}
//print both sums here to make sure the computation is not being optimized out

您需要检查反汇编以确保编译器没有做任何巧妙的事情。

我不明白为什么需要您现在进行的复杂设置。 RNG 可以排除在外，我不明白为什么需要比这个简单的循环更多的东西。如果编译器玩花样，您可能需要将变量标记为 volatile，这使得编译器（更好：大多数编译器）将它们视为外部函数调用。

由于 RNG 现在不再重要，因为它几乎从未被调用过，您甚至可以调用 OS 的加密 RNG 来获取（对任何人而言）与真正的随机数无法区分的数字。

是否有导致 50% 分支预测未命中的代码？

Is there a code that results in 50% branch prediction miss?

c++

c

performance

compiler-optimization

computer-architecture