标签: branch-prediction

这是一段看似非常特殊的C++代码.出于某种奇怪的原因,奇迹般地对数据进行排序使得代码几乎快了六倍.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c) …

我正在用Java编写一些代码,在某些时候,程序的流程是由两个int变量"a"和"b"是否为非零来确定的(注意:a和b从不是负数,并且从不在整数溢出范围内).

我可以评估它

if (a != 0 && b != 0) { /* Some code */ }

或者

if (a*b != 0) { /* Some code */ }

因为我希望每段代码运行数百万次,所以我想知道哪一段会更快.我通过在一个巨大的随机生成的数组上进行比较来做实验,我也很想知道数组的稀疏性(数据的分数= 0)会如何影响结果:

long time;
final int len = 50000000;
int arbitrary = 0;
int[][] nums = new int[2][len];

for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) {
    for(int i = 0 ; i < 2 ; i++) {
        for(int j = 0 ; j < len ; j++) …

具体来说,如果我有一系列if... else if语句,并且我事先知道每个语句将评估的相对概率,true它按照概率的顺序对它们进行排序有多大差异？例如,我应该更喜欢这个:

if (highly_likely)
  //do something
else if (somewhat_likely)
  //do something
else if (unlikely)
  //do something

对此？:

if (unlikely)
  //do something
else if (somewhat_likely)
  //do something
else if (highly_likely)
  //do something

很明显,排序版本会更快,但是为了便于阅读或存在副作用,我们可能希望对它们进行非最佳排序.在您实际运行代码之前,很难判断CPU在分支预测方面的表现如何.

因此,在尝试这个过程中,我最终回答了我自己的问题,但我还想听听其他意见/见解.

重要提示:此问题假定if语句可以任意重新排序,而不会对程序的行为产生任何其他影响.在我的回答中,三个条件测试是互斥的,不会产生副作用.当然,如果必须按某种顺序评估陈述以达到某些预期的行为,那么效率问题就没有实际意义.

我发现了这个流行的大约 9 岁的SO 问题，并决定仔细检查其结果。

所以，我有 AMD Ryzen 9 5950X、clang++ 10 和 Linux，我从问题中复制粘贴了代码，这是我得到的：

排序 - 0.549702s：

~/d/so_sorting_faster$ cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
    std::sort(data, data + arraySize);
0.549702
sum = 314931600000

未分类 - 0.546554s：

~/d/so_sorting_faster $ cat main.cpp | grep "std::sort" && clang++ -O3 main.cpp && ./a.out
    // std::sort(data, data + arraySize);
0.546554
sum = 314931600000

我很确定 unsorted 版本比 3ms 快的事实只是噪音，但它似乎不再慢了。

那么，CPU 的架构发生了什么变化（使其不再慢一个数量级）？

以下是多次运行的结果：

Unsorted: 0.543557 0.551147 0.541722 0.555599
Sorted: …

对于英特尔架构,是否有一种方法可以指示GCC编译器生成的代码总是强制分支预测在我的代码中采用特定方式？英特尔硬件是否支持此功能？那么其他编译器或硬件呢？

我会在C++代码中使用它,我知道我希望快速运行的情况,并且不关心当另一个分支需要被采取时,即使它最近采用了该分支.

for (;;) {
  if (normal) { // How to tell compiler to always branch predict true value?
    doSomethingNormal();
  } else {
    exceptionalCase();
  }
}

作为Evdzhan Mustafa的后续问题,该提示是否可以在处理器第一次遇到指令时指定一个提示,所有后续的分支预测都能正常运行？

在我的生活中,我不能记住那天老师说的话,我希望你可能知道.

该模块是"数据结构和算法",他告诉我们的一些事情:

该if声明是最昂贵的[东西.[东西]注册[东西].

是的,我确实有一个可怕的记忆,我真的很抱歉,但我一直在谷歌搜索几个小时,没有任何事情发生.有任何想法吗？

在阅读了这篇文章后(在StackOverflow上回答)(在优化部分),我想知道为什么条件移动不容易受到分支预测失败的影响.我在一篇关于cond移动的文章中找到了(PDF由AMD提供).在那里,他们声称cond的性能优势.移动.但为什么会这样呢？我没有看到它.在评估ASM指令的时刻,前面的CMP指令的结果尚未知晓.

谢谢.

在这段代码中:

if (value >= x && value <= y) {

什么时候value >= x和value <= y没有特定模式的情况一样真假,使用&运算符会比使用更快&&吗？

具体来说,我正在考虑如何&&懒惰地评估右侧表达式(即,仅当LHS为真),这意味着条件,而&在此上下文中的Java 保证严格评估两个(布尔)子表达式.值结果是相同的两种方式.

不过,虽然一个>=或<=运营商将使用一个简单的比较指令时,&&必须包括一个分支,该分支是易受分支预测失败 -按本非常著名的问题:为什么快处理有序数组不是一个排序的数组？

因此,强制表达式没有惰性组件肯定会更具确定性,并且不容易受到预测失败的影响.对？

笔记:

• 很明显,如果代码看起来如此,我的问题的答案就是否定:if(value >= x && verySlowFunction()).我专注于"足够简单"的RHS表达.
• 无论如何,那里有一个条件分支(if声明).我无法向自己证明这是无关紧要的,而且替代配方可能是更好的例子,比如boolean b = value >= x && value <= y;
• 这一切都落入了可怕的微观优化世界.是的,我知道:-) ......虽然很有趣？

更新 只是为了解释为什么我感兴趣:我一直在盯着马丁汤普森在他的机械同情博客上撰写的系统,在他来到并谈到 Aeron之后.其中一个关键信息是我们的硬件中包含了所有这些神奇的东西,我们的软件开发人员不幸地无法利用它.别担心,我不打算在我的所有代码上使用///// :-) ...但是这个网站上有很多关于通过删除分支来改进分支预测的问题,并且它发生了对我来说,条件布尔运算符是测试条件的核心.

当然,@ StephenC提出了一个奇妙的观点,即将代码弯曲成奇怪的形状可以使JIT更容易发现常见的优化 - 如果不是现在,那么将来也是如此.并且上面提到的非常着名的问题是特殊的,因为它推动预测复杂性远远超出实际优化. …

我正在读Fedor Pikus 的这本书，他有一些非常非常有趣的例子，对我来说是一个惊喜。
特别是这个基准测试吸引了我，唯一的区别是在其中一个我们使用 || 在 if 和另一个中我们使用 |。

void BM_misspredict(benchmark::State& state)
{

    std::srand(1);
    const unsigned int N = 10000;;
    std::vector<unsigned long> v1(N), v2(N);
    std::vector<int> c1(N), c2(N);

    for (int i = 0; i < N; ++i) 
    {
        v1[i] = rand();
        v2[i] = rand();
        c1[i] = rand() & 0x1;
        c2[i] = !c1[i];
    }

    unsigned long* p1 = v1.data();
    unsigned long* p2 = v2.data();
    int* b1 = c1.data();
    int* b2 = c2.data();

    for (auto _ : state)
    {
        unsigned long a1 …

我刚刚阅读了有关Branch-Prediction的内容,并想尝试使用Java 8 Streams.

然而,Streams的性能总是比传统的循环更差.

int totalSize = 32768;
int filterValue = 1280;
int[] array = new int[totalSize];
Random rnd = new Random(0);
int loopCount = 10000;

for (int i = 0; i < totalSize; i++) {
    // array[i] = rnd.nextInt() % 2560; // Unsorted Data
    array[i] = i; // Sorted Data
}

long start = System.nanoTime();
long sum = 0;
for (int j = 0; j < loopCount; j++) {
    for (int c = 0; c < totalSize; …