是否存在导致50％分支预测未命中的代码？
问题：
我试图找出如何编写代码（C优先，仅在没有其他解决方案的情况下 ASM），这将使分支预测在50％的情况下失败 。
所以它必须是一段代码“对于与分支相关的编译器优化”是“imune”的，并且所有HW分支预测都不应该优于50％（掷硬币）。 即使是更大的挑战，也能够在多个CPU架构上运行代码并获得相同的50％缺失率。
我设法编写了一个在x86平台上达到47％分支未命中率的代码。 我怀疑失踪可能有3％来自：
- 已经分支的程序启动开销（尽管很小）
- Profiler开销 – 基本上对于每个计数器读取都会引发中断，因此可能会添加其他可预测的分支。
- 在后台运行的系统调用包含循环和可预测的分支
我编写了自己的随机数生成器，以避免调用rand，其实现可能隐藏了可预测的分支。 当可用时它也可以使用rdrand 。 延迟对我来说无关紧要。
问题：
- 我能比我的代码版做得更好吗？ 更好的意思是为所有CPU架构获得更高的分支错误预测和相同的结果。
- 这段代码可以预测吗？ 那是什么意思？
代码：
#include #include #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_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错过 。 这对我的目的来说已经足够了，我有了在各种架构上产生这种方法的方法。
如果你知道分支预测器是如何工作的，你可以得到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(); if (*++p) f(); else g(); 假设p指向随机布尔数组（这可以避开rand()的分支预测问题 – 只需在测量之前执行此操作，即可成为一个真正不可预测的分支
如果for(;;)循环给你带来问题，只需输入一个goto 。
请注意，评论中的“循环展开技巧”有些误导。 你实际上创建了数千个分支。 每个分支都将被单独预测，除了它们可能都不会被预测，因为CPU根本无法容纳数千个不同的预测。 这可能会或可能不会对您的真正目标有益。