如何禁用分支预测C++/Mac/英特尔

Question

我正在为学校做作业。从本质上讲，我们正在分析排序算法及其在大型数字集上的成本。我们有最佳情况(已经按顺序(、最坏情况(反向顺序(和平均情况(随机顺序(。但是，对于几乎所有的排序算法，对最坏情况进行排序所需的时间比平均情况要少。阅读后，似乎肯定是分支预测导致了这种情况。它识别模式(降序(并比理论上更快地执行代码(大 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;
            }
        }
    }
}

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

Answer 1

Big-O表示法都是关于渐近行为的。换句话说，它描述了随着问题规模变大，哪些因素变得占主导地位。

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

因此，不要费心猜测或担心分支预测的效果。只需放大您的阵列即可。尝试对包含 100 万个元素的数组进行排序。或10亿。我向你保证：如果你对一种情况是最坏情况是正确的，它会比最好的情况慢。(提示：你说得不对。