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

问题：

我正在尝试弄清楚如何编写代码（C 首选，仅在没有其他解决方案的情况下使用 ASM），这将使分支预测在 50% 的情况下丢失。

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

我设法编写了一个代码，该代码在 x86 平台上的分支未命中率达到 47%。我怀疑失踪者可能 3% 来自：

具有分支的程序启动开销（尽管非常小）
探查器开销 - 基本上，对于每个计数器读取，都会引发一个中断，因此这可能会添加其他可预测的分支。
在后台运行的包含循环和可预测分支的系统调用

我编写了自己的随机数生成器，以避免调用其实现可能隐藏可预测分支的 rand。如果可用，它也可以使用 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 = %llun", sum);
}

更新 v1：

根据 usr 的建议，我通过在脚本中改变命令行中的 LCG_C 参数来生成各种模式。我能够达到 49.67% 的 BP 失误。这对于我的目的来说已经足够了，我有在各种架构上生成它的方法。

如果你知道分支预测器是如何工作的，你可以得到 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

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

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

现在非常仔细地检查处理器的体系结构及其分支预测。填充数组的初始字节，以便在检查它们后，处理器处于可预测的已知状态。从该已知状态中，您可以了解是否预测下一个分支。设置下一个字节，以便预测错误。再次，找出是否预测下一个分支，并设置下一个字节，以便预测错误，依此类推。

如果同时禁用中断（这可能会更改分支预测），则可以接近 100% 错误预测的分支。

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

当然，这仅适用于该特定处理器。大多数现代处理器认为该序列几乎是 100% 可预测的。例如，他们可能使用两个单独的预测变量;一个用于"最后一个分支被拿走"的情况，一个用于"最后一个分支没有被拿走"的情况。但是对于这样的处理器，不同的字节序列将给出相同的 100% 错误预测率。

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

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

请注意，评论中的"循环展开技巧"有些误导。您实际上是在创建数千个分支。每个分支都将被单独预测，除了可能没有一个分支会被预测，因为CPU根本无法容纳数千个不同的预测。这对您的真正目标可能是也可能不是好处。

尝试使用/不使用RAND_BRANCH定义：

/* gcc -DRAND_BRANCH -O0 -g -o br-miss br-miss.c */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int number[1000000000];
int test_branch(void)
{
        int x = 0;
        for (int i = 0; i < sizeof(number)/sizeof(int); i++) {
                if (number[i] > 0) {
                        x++;
                };
        }
        return x;
}
long difftimespec_ns(const struct timespec start, const struct timespec end)
{
    return ((int64_t)end.tv_sec - (int64_t)start.tv_sec) * (int64_t)1000000000
        + ((int64_t)end.tv_nsec - (int64_t)start.tv_nsec);
}
int main(int argc, char *argv[])
{
        for (int i = 0; i < sizeof(number)/sizeof(int); i++) {
#ifdef RAND_BRANCH
                number[i] = rand() % 2 ? 0 : 1;
#else
        number[i] = i % 2 ? 0 : 1;
#endif
        }
        struct timespec start, end;
        clock_gettime(CLOCK_MONOTONIC, &start);
        test_branch();
        clock_gettime(CLOCK_MONOTONIC, &end);
        printf("test_branch takes %ld nsn", difftimespec_ns(start, end));
        return 0;
}

如果没有定义RAND_BRANCH，接近 ~100% 命中率。天地网...模式可以通过现代 CPU 预测。

$ ./br-miss
test_branch takes 467987135 ns

定义RAND_BRANCH后，接近 ~50% 的失误。没有模式。执行性能慢 8.8 倍。

$ ./br-miss
test_branch takes 4130685513 ns

相关内容

最新更新

热门标签：

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

相关内容

最新更新

热门标签：

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