c++ - 如何禁用分支预测C++/Mac/Intel

我正在为学校做作业。本质上，我们正在分析排序算法及其在大量数字上的成本。我们有一个最佳情况(按顺序排列)，最坏情况(逆向排列)和平均情况(随机排列)。但是，对于我几乎所有的排序算法，对最坏情况进行排序所花的时间都比平均情况少。阅读后，肯定似乎是分支预测导致了这种情况。它正在识别模式(降序)，并且比理论上(大的O表示法)应该更快地执行代码。

我已经对分支预测进行了一些研究，虽然似乎有一些方法可以使它更快地进行优化，但是在完全禁用它方面我找不到任何东西。我可以使用G++标志吗？还是终端命令？

这是我的气泡排序算法的一个示例:

void bubble(vector<long> &vector) {
    for (int i = 0; i < vector.size() - 1; i++){
        for (int j = 0; j < vector.size() - i - 1; j++) {
            if (vector[j] > vector[j + 1]) {
                long tmp = vector[j];
                vector[j] = vector[j+1];
                vector[j+1] = tmp;
            }
        }
    }
}

对于最坏的情况，我的平均时间几乎是原来的两倍。

最佳答案

Big-O表示法与渐近行为有关。换句话说，它描述了随着问题规模的增大，哪些因素成为主导。

诸如预取和分支预测之类的CPU微优化可以在较小的尺寸下产生较大的相对影响。但是O(n ^ 2)过程相对于O(n)过程的本质是，一旦问题大小足够大，它将变得更慢。

因此，不要理会猜测或担心分支预测的影响。只是增加您的数组。尝试对一百万个元素进行排序。或十亿。我向您保证:如果您认为一种情况是最坏的情况是正确的，那它将比最好的情况慢。 (提示:您对此不对。)

关于c++ - 如何禁用分支预测C++/Mac/Intel，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56974967/