主页 / user-443878

OopsUser's questions

Martin Hope
OopsUser
Asked: 2025-04-27 21:24:35 +0800 CST
  • 7

在尝试衡量分支未命中预测的影响时，我注意到分支未命中预测根本没有任何惩罚。

根据著名的堆栈溢出问题： 为什么处理排序数组比处理未排序数组更快？

我写了一段简单的代码来测量分支预测的惩罚。

  • 用随机数填充数组
  • 计算 5 以上的数字（应该有很多预测错误） - 测量它
  • 对数组进行排序
  • 计算 5 以上的数字（应该很少有预测失误）——测量它

运行代码后，我得到了两次测量几乎相同的结果。

已测试：

  1. Visual Studio 2017，发布（最大优化（优先速度）（/O2）），Windows。
  2. Linux，g++-Ofast

然后，我取出了上面链接的问题中的原始代码，排序后的数组仍然没有任何改进。这是为什么呢？分支预测的好处又在哪里呢？

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

int main()
{
    // Step 1: Allocate a vector of size 1 million
    std::vector<int> vec(100'000'000);

    // Step 2: Fill it with random numbers between 0 and 10
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, 10);

    for (auto& val : vec)
    {
        val = dis(gen);
    }

    // Step 3: Count numbers above 5 (and measure time)
    auto start = std::chrono::high_resolution_clock::now();
    int count_above_5 = 0;
    for (size_t i = 0; i < vec.size(); i++)
    {
        if (vec[i] < 5)
        {
            ++count_above_5;
        }
    }

    auto end = std::chrono::high_resolution_clock::now();

    auto duration_before_sort = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();

    std::cout << "Count of numbers above 5 (before sorting): " << count_above_5 << std::endl;
    std::cout << "Time taken (before sorting): " << duration_before_sort << " ns" << std::endl;

    // Step 4: Sort the array
    std::sort(vec.begin(), vec.end());

    // Step 5: Count numbers above 5 in the sorted array (and measure time)

    start = std::chrono::high_resolution_clock::now();
    count_above_5 = 0;
    for (size_t i = 0; i < vec.size(); i++)
    {
        if (vec[i] < 5)
        {
            ++count_above_5;
        }
    }
    end = std::chrono::high_resolution_clock::now();


    auto duration_after_sort = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();

    std::cout << "Count of numbers above 5 (after sorting): " << count_above_5 << std::endl;
    std::cout << "Time taken (after sorting):  " << duration_after_sort << " ns" << std::endl;

    return 0;
}
c++