AskOverflow.Dev

AskOverflow.Dev Logo AskOverflow.Dev Logo

AskOverflow.Dev Navigation

  • 主页
  • 系统&网络
  • Ubuntu
  • Unix
  • DBA
  • Computer
  • Coding
  • LangChain

Mobile menu

Close
  • 主页
  • 系统&网络
    • 最新
    • 热门
    • 标签
  • Ubuntu
    • 最新
    • 热门
    • 标签
  • Unix
    • 最新
    • 标签
  • DBA
    • 最新
    • 标签
  • Computer
    • 最新
    • 标签
  • Coding
    • 最新
    • 标签
主页 / coding / 问题 / 79595067
Accepted
OopsUser
OopsUser
Asked: 2025-04-27 21:24:35 +0800 CST2025-04-27 21:24:35 +0800 CST 2025-04-27 21:24:35 +0800 CST

为什么分支(未命中)预测不会影响性能(C++)?

  • 772

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

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

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

  • 用随机数填充数组
  • 计算 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++
  • 1 1 个回答
  • 78 Views

1 个回答

  • Voted
  1. Best Answer
    Jérôme Richard
    2025-04-27T22:20:22+08:002025-04-27T22:20:22+08:00

    TL;DR: GCC、MSVC 和 Clang 都生成无分支汇编代码,因此没有实际分支,也不会受到分支(未命中)预测的影响。


    在我的机器上,使用 GCC 14.2.0 的 Linux 系统上,分支预测不会带来任何影响,因为实际上没有分支。事实上, GCC使用 SIMD 指令生成了无分支的汇编代码:

    180:   
        movdqu  xmm2,XMMWORD PTR [rax]   ; Load a block of items from the array `vec`
        movdqa  xmm1,XMMWORD PTR [rsp]   ; Reload xmm1 from memory
        add     rax,0x10                 ; Move the `rax` pointer to the next block
        pcmpgtd xmm1,xmm2                ; Compare items of the block with 5 and move the mask in `xmm1`
        psubd   xmm0,xmm1                ; Increment the number of item found in `xmm0`
        cmp     rax,rbp                  ; Loop until we reach the last block
        jne     180            
    

    在Godbolt上,我们可以看到 MSVC 和 Clang 都生成了无分支代码。以下是 MSVC 生成的代码(没有使用 SIMD 指令,而是cmovge使用了效率较低的指令):

    $LL7@main:
        lea     eax, DWORD PTR [rdi+1]
        cmp     DWORD PTR [rsi+rcx*4], 5
        cmovge  eax, edi
        mov     edi, eax
        inc     rcx
        cmp     rcx, r14
        jb      SHORT $LL7@main
    

    这里是 Clang 生成的代码(使用 SIMD 指令并展开循环 4 次):

    .LBB0_10:
        movdqu  xmm0, xmmword ptr [rbx + 4*r12 - 48]
        movdqu  xmm1, xmmword ptr [rbx + 4*r12 - 32]
        movdqu  xmm2, xmmword ptr [rbx + 4*r12 - 16]
        movdqu  xmm3, xmmword ptr [rbx + 4*r12]
        movdqa  xmm4, xmm5
        pcmpgtd xmm4, xmm0
        psubd   xmm6, xmm4
        movdqa  xmm0, xmm5
        pcmpgtd xmm0, xmm1
        psubd   xmm7, xmm0
        movdqa  xmm0, xmm5
        pcmpgtd xmm0, xmm2
        psubd   xmm6, xmm0
        movdqa  xmm0, xmm5
        pcmpgtd xmm0, xmm3
        psubd   xmm7, xmm0
        add     r12, 16
        cmp     r12, 100012
        jne     .LBB0_10
    
    • 6

相关问题

  • 为什么编译器在这里错过矢量化?

  • 使用带有库的 CMake 编译错误[关闭]

  • 每次我尝试运行预制时都会抛出错误

  • 如何在 C++ 中创建类似于 std::byte 的八位字节类型?

  • C++17 中 std::byte 只能按位运算?

Sidebar

Stats

  • 问题 205573
  • 回答 270741
  • 最佳答案 135370
  • 用户 68524
  • 热门
  • 回答
  • Marko Smith

    重新格式化数字,在固定位置插入分隔符

    • 6 个回答
  • Marko Smith

    为什么 C++20 概念会导致循环约束错误,而老式的 SFINAE 不会?

    • 2 个回答
  • Marko Smith

    VScode 自动卸载扩展的问题(Material 主题)

    • 2 个回答
  • Marko Smith

    Vue 3:创建时出错“预期标识符但发现‘导入’”[重复]

    • 1 个回答
  • Marko Smith

    具有指定基础类型但没有枚举器的“枚举类”的用途是什么?

    • 1 个回答
  • Marko Smith

    如何修复未手动导入的模块的 MODULE_NOT_FOUND 错误?

    • 6 个回答
  • Marko Smith

    `(表达式,左值) = 右值` 在 C 或 C++ 中是有效的赋值吗?为什么有些编译器会接受/拒绝它?

    • 3 个回答
  • Marko Smith

    在 C++ 中,一个不执行任何操作的空程序需要 204KB 的堆,但在 C 中则不需要

    • 1 个回答
  • Marko Smith

    PowerBI 目前与 BigQuery 不兼容:Simba 驱动程序与 Windows 更新有关

    • 2 个回答
  • Marko Smith

    AdMob:MobileAds.initialize() - 对于某些设备,“java.lang.Integer 无法转换为 java.lang.String”

    • 1 个回答
  • Martin Hope
    Fantastic Mr Fox msvc std::vector 实现中仅不接受可复制类型 2025-04-23 06:40:49 +0800 CST
  • Martin Hope
    Howard Hinnant 使用 chrono 查找下一个工作日 2025-04-21 08:30:25 +0800 CST
  • Martin Hope
    Fedor 构造函数的成员初始化程序可以包含另一个成员的初始化吗? 2025-04-15 01:01:44 +0800 CST
  • Martin Hope
    Petr Filipský 为什么 C++20 概念会导致循环约束错误,而老式的 SFINAE 不会? 2025-03-23 21:39:40 +0800 CST
  • Martin Hope
    Catskul C++20 是否进行了更改,允许从已知绑定数组“type(&)[N]”转换为未知绑定数组“type(&)[]”? 2025-03-04 06:57:53 +0800 CST
  • Martin Hope
    Stefan Pochmann 为什么 {2,3,10} 和 {x,3,10} (x=2) 的顺序不同? 2025-01-13 23:24:07 +0800 CST
  • Martin Hope
    Chad Feller 在 5.2 版中,bash 条件语句中的 [[ .. ]] 中的分号现在是可选的吗? 2024-10-21 05:50:33 +0800 CST
  • Martin Hope
    Wrench 为什么双破折号 (--) 会导致此 MariaDB 子句评估为 true? 2024-05-05 13:37:20 +0800 CST
  • Martin Hope
    Waket Zheng 为什么 `dict(id=1, **{'id': 2})` 有时会引发 `KeyError: 'id'` 而不是 TypeError? 2024-05-04 14:19:19 +0800 CST
  • Martin Hope
    user924 AdMob:MobileAds.initialize() - 对于某些设备,“java.lang.Integer 无法转换为 java.lang.String” 2024-03-20 03:12:31 +0800 CST

热门标签

python javascript c++ c# java typescript sql reactjs html

Explore

  • 主页
  • 问题
    • 最新
    • 热门
  • 标签
  • 帮助

Footer

AskOverflow.Dev

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

Language

  • Pt
  • Server
  • Unix

© 2023 AskOverflow.DEV All Rights Reserve