有没有一种代码可以导致50%的分支预测错误？

Question

有没有一种代码可以导致50%的分支预测错误？

cperformancecpu-architecturecompiler-optimizationbranch-prediction

25

问题：

我正在尝试编写一段代码（首选C语言，如果没有其他解决方案，也可以使用汇编语言），使得分支预测在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 = %llu\n", sum);
}

更新 v1：

在 usr 的建议下，我通过在脚本中从命令行变化 LCG_C 参数生成了各种模式。 我能够达到 49.67% 的 BP 未命中率。这已经足够满足我的需求，并且我有办法在不同的架构上实现这一目标。

- VAndrei

10

为什么处理已排序的数组比未排序的数组更快？[Why is processing a sorted array faster than an unsorted array?]这篇文章中的代码是一个微基准测试。除非编译器通过无分支等效方式替换代码。 - CodesInChaos

4

您是如何确定分支预测错误率只有8%的？我很好奇您使用了哪些工具来确定这一点。 - Cornstalks

4

不确定是否相关，但 rand 不是一个好的随机数生成器。它可能会变得非常可预测，以至于分支预测器实际上能够以一致的方式预测其行为。 - Stefano Sanfilippo

1

内联rand()调用，rng不必很好，你只需要不要在其中来回分支。 - jthill

1

如果你想学习一些有启发性的东西，可以打印出你的LCG的前20个输出，所有输出都需要对2取模。 - user1084944

显示剩余19条评论

4个回答

3

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

现在仔细检查处理器的架构和分支预测。填充数组的初始字节，以便在检查完它们后，处理器处于可预知的已知状态。从该已知状态开始，您可以找出下一个分支是否被预测为取到。设置下一个字节使预测错误。再次找出下一个分支是否被预测为取到，设置下一个字节使预测错误，以此类推。

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

例如，在旧的PowerPC处理器上，如果连续三次取到分支，则始终处于“强取到”状态，而不取一次分支就会改为“弱取到”。如果现在有交替的未取/取分支序列，则预测总是错误的，并且在弱未取和弱取之间转换。

当然，这只适用于特定的处理器。大多数现代处理器将看到该序列几乎100％可预测。例如，它们可能使用两个单独的预测器; 一个用于“上一个分支被取到”的情况，另一个用于“上一个分支未取到”的情况。但对于这样的处理器，不同的字节序列将产生相同的100％错误预测率。

- gnasher729

嗯...问题是我需要一段通用代码，可以在所有架构上统计生成50%的分支未命中。我还想知道，如果我关闭中断，那么我就无法测量与分支相关的计数器了...对吧？ - VAndrei

再次感谢。你的回答也是正确的，但是usr的回答更加详细，并且被观众投票选中。 - VAndrei

0

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

如果 for(;;) 循环给您带来问题，请加入 goto。

请注意，注释中的“循环展开技巧”有些误导人。您实际上正在创建数千个分支。每个分支都将单独预测，但它们中可能没有一个被预测为 CPU 可以简单地不能保持数千个不同的预测。这可能对您的真正目标有所好处也可能没有好处。

- MSalters

我相信你的例子实际上是完全可以预测的。这是一种交替的开/关模式。 - Zan Lynx

@ZanLynx：这完全取决于p指向的随机数据数组。即使编译器使用了两个条件分支（这是一种糟糕的实现），两个分支也仅取决于p的最后一个值，这使得两个预测同样毫无意义。 - MSalters

谢谢您的答复。因此，您建议在共享库中拥有2个函数f和g，并随机调用它们。这可能有效。我会尝试一下。关于goto，我仍然需要从模拟循环中退出，因此我需要使用分支检查一些内容。 - VAndrei

还有一件事情。你说手动展开循环可能会导致CPU溢出它的分支目标缓冲区。我想知道，对于只执行一次的分支，是否也会发生这种情况。我认为在我的情况下，一个新的分支只会占用已被逐出历史记录的分支的条目。 - VAndrei

2

@VAndrei：不要试图跳出循环。我的确是想写一个无限循环。从另一个监控线程调用TerminateThread或者你的操作系统使用的其他方法。 - MSalters

0

尝试使用/不使用定义的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 ns\n", difftimespec_ns(start, end));

        return 0;
}

没有定义RAND_BRANCH，接近100%的命中率。现代CPU可以预测TNTNTN...模式。

$ ./br-miss
test_branch takes 467987135 ns

有了RAND_BRANCH定义，近50%的错误。没有模式可言。执行性能慢了8.8倍。

$ ./br-miss
test_branch takes 4130685513 ns

- Changbin Du

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- usr · Accepted Answer

如果您了解分支预测器的工作原理，您可以达到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来获得与真随机数（对于任何人来说）无法区分的数字。