17

我试图通过测量运行带有可预测分支的循环与带有随机分支的循环的时间来很好地理解分支预测。

所以我写了一个程序，它采用以不同顺序排列的 0 和 1 的大数组（即全 0，重复 0-1，全 rand），并根据当前索引是 0 还是 1 迭代数组分支，做时间- 浪费工作。

我预计难以猜测的数组会花费更长的时间来运行，因为分支预测器会更频繁地猜测错误，并且无论时间长短，两组数组上运行之间的时间增量都将保持不变 -浪费工作。

然而，随着浪费时间的工作量增加，阵列之间的运行时间差异增加了很多。

哟，这张图没有意义

（X 轴是浪费时间的工作量，Y 轴是运行时间）

有人理解这种行为吗？您可以在以下代码中看到我正在运行的代码：

#include <stdlib.h>
#include <time.h>
#include <chrono>
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
static const int s_iArrayLen = 999999;
static const int s_iMaxPipelineLen = 60;
static const int s_iNumTrials = 10;

int doWorkAndReturnMicrosecondsElapsed(int* vals, int pipelineLen){
        int* zeroNums = new int[pipelineLen];
        int* oneNums = new int[pipelineLen];
        for(int i = 0; i < pipelineLen; ++i)
                zeroNums[i] = oneNums[i] = 0;

        chrono::time_point<chrono::system_clock> start, end;
        start = chrono::system_clock::now();
        for(int i = 0; i < s_iArrayLen; ++i){
                if(vals[i] == 0){
                        for(int i = 0; i < pipelineLen; ++i)
                                ++zeroNums[i];
                }
                else{
                        for(int i = 0; i < pipelineLen; ++i)
                                ++oneNums[i];
                }
        }
        end = chrono::system_clock::now();
        int elapsedMicroseconds = (int)chrono::duration_cast<chrono::microseconds>(end-start).count();

        //This should never fire, it just exists to guarantee the compiler doesn't compile out our zeroNums/oneNums
        for(int i = 0; i < pipelineLen - 1; ++i)
                if(zeroNums[i] != zeroNums[i+1] || oneNums[i] != oneNums[i+1])
                        return -1;
        delete[] zeroNums;
        delete[] oneNums;
        return elapsedMicroseconds;
}

struct TestMethod{
        string name;
        void (*func)(int, int&);
        int* results;

        TestMethod(string _name, void (*_func)(int, int&)) { name = _name; func = _func; results = new int[s_iMaxPipelineLen]; }
};

int main(){
        srand( (unsigned int)time(nullptr) );

        vector<TestMethod> testMethods;
        testMethods.push_back(TestMethod("all-zero", [](int index, int& out) { out = 0; } ));
        testMethods.push_back(TestMethod("repeat-0-1", [](int index, int& out) { out = index % 2; } ));
        testMethods.push_back(TestMethod("repeat-0-0-0-1", [](int index, int& out) { out = (index % 4 == 0) ? 0 : 1; } ));
        testMethods.push_back(TestMethod("rand", [](int index, int& out) { out = rand() % 2; } ));

        int* vals = new int[s_iArrayLen];

        for(int currentPipelineLen = 0; currentPipelineLen < s_iMaxPipelineLen; ++currentPipelineLen){
                for(int currentMethod = 0; currentMethod < (int)testMethods.size(); ++currentMethod){
                        int resultsSum = 0;
                        for(int trialNum = 0; trialNum < s_iNumTrials; ++trialNum){
                                //Generate a new array...
                                for(int i = 0; i < s_iArrayLen; ++i)  
                                        testMethods[currentMethod].func(i, vals[i]);

                                //And record how long it takes
                                resultsSum += doWorkAndReturnMicrosecondsElapsed(vals, currentPipelineLen);
                        }

                        testMethods[currentMethod].results[currentPipelineLen] = (resultsSum / s_iNumTrials);
                }
        }

        cout << "\t";
        for(int i = 0; i < s_iMaxPipelineLen; ++i){
                cout << i << "\t";
        }
        cout << "\n";
        for (int i = 0; i < (int)testMethods.size(); ++i){
                cout << testMethods[i].name.c_str() << "\t";
                for(int j = 0; j < s_iMaxPipelineLen; ++j){
                        cout << testMethods[i].results[j] << "\t";
                }
                cout << "\n";
        }
        int end;
        cin >> end;
        delete[] vals;
}

Pastebin 链接：http://pastebin.com/F0JAu3uw

4

2 回答 2

20

我认为您可能正在测量缓存/内存性能，而不是分支预测。您的内部“工作”循环正在访问越来越多的内存。这可以解释线性增长、周期性行为等。

我可能是错的，因为我没有尝试复制你的结果，但如果我是你，我会在计时其他事情之前考虑内存访问。也许将一个 volatile 变量与另一个变量相加，而不是在数组中工作。

另请注意，根据 CPU 的不同，分支预测可能比仅记录上次执行分支的时间要智能得多——例如，重复模式并不像随机数据那么糟糕。

好的，我在茶歇时进行了一个快速而肮脏的测试，它试图反映您自己的测试方法，但不会破坏缓存，如下所示：

在此处输入图像描述

是不是更符合你的预期？

如果我以后有空的话，还有其他我想尝试的东西，因为我还没有真正看过编译器在做什么......

编辑：

而且，这是我的最终测试——我在汇编程序中重新编码以删除循环分支，确保每条路径中的指令数量准确，等等。

更多分支预测结果

我还添加了一个 5 位重复模式的额外案例。似乎很难扰乱我老化的 Xeon 上的分支预测器。

于 2013-01-04T08:08:44.517 回答
2

除了 JasonD 指出的，我还要注意for循环内部有条件，这可能会影响分支预测：

if(vals[i] == 0)
{
    for(int i = 0; i < pipelineLen; ++i)
        ++zeroNums[i];
}

i < 管道长度；是一个像你if的条件。当然编译器可能会展开这个循环，但是 pipelineLen 是传递给函数的参数，所以它可能不会。

我不确定这是否可以解释您的结果的波浪模式，但是：

由于 BTB 在 Pentium 4 处理器中只有 16 个条目长，因此对于长于 16 次迭代的循环，预测最终将失败。这个限制可以通过展开一个循环来避免，直到它只有 16 次迭代。完成此操作后，循环条件将始终适合 BTB，并且在循环退出时不会发生分支错误预测。以下是循环展开的示例：

阅读全文： http: //software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts

因此，您的循环不仅在测量内存吞吐量，而且还在影响 BTB。

如果您0-1在列表中传递了模式，但随后使用您的 BTB 执行了一个 for 循环，pipelineLen = 2则会填充类似的0-1-1-0 - 1-1-1-0 - 0-1-1-0 - 1-1-1-0内容，然后它将开始重叠，因此这确实可以解释您的结果的波浪模式（某些重叠会比其他重叠更有害）。

以此为例说明可能发生的情况，而不是字面解释。您的 CPU 可能具有更复杂的分支预测架构。

于 2013-01-04T15:43:43.013 回答