问题标签 [branch-prediction]

所以我了解流水线处理器分支预测中使用的基本技术——比如 2 位饱和计数器、两级自适应预测器等。

以下是我的问题：

1）分支目标预测：为什么这很重要，这里使用了哪些机制？当我想到一个分支时，我会想到“bne r2，r3，LABEL”，它表示如果 r2 ！= r3 然后分支到 LABEL，这意味着 PC（程序计数器）= PC + LABEL。在这里预测目标有什么神秘之处？根据 LABEL 的编译值，您知道它将是什么。我可能以某种方式错过了这一点。

2) 为什么程序计数器值本身（例如 0x4001000C）或至少它的最后几位被用作分支预测方案的一部分？我看到了一个方案，其中 PC 的最后 4 位连接到（4 位）分支历史寄存器，并且该 8 位值用于访问模式历史表。我认为PC非常随意！

感谢您对理解这些问题的任何帮助

这是一段 C++ 代码，它显示了一些非常特殊的行为。出于某种奇怪的原因，对数据进行排序（在定时区域之前）奇迹般地使循环快了近六倍。

• 如果没有std::sort(data, data + arraySize);，代码将在 11.54 秒内运行。
• 使用排序后的数据，代码运行时间为 1.93 秒。

（排序本身比遍历数组需要更多时间，因此如果我们需要为未知数组计算它，实际上不值得这样做。）

最初，我认为这可能只是语言或编译器异常，所以我尝试了 Java：

有类似但不太极端的结果。

我的第一个想法是排序将数据带入缓存，但后来我认为这是多么愚蠢，因为数组刚刚生成。

• 到底是怎么回事？
• 为什么处理排序数组比处理未排序数组更快？

该代码总结了一些独立的术语，因此顺序无关紧要。

关于不同/更高版本的编译器和选项的相同效果的相关/后续问答：

• 为什么处理未排序数组的速度与使用现代 x86-64 clang 处理已排序数组的速度相同？
• gcc 优化标志 -O3 使代码比 -O2 慢

这是我的演示程序：

这是该程序两个版本的程序集差异，一个有qsort一个没有：

据我了解汇编输出，排序后的版本由于将值传递给了更多的代码qsort，但我没有看到任何分支优化/预测/任何东西。也许我看错了方向？

这个问题及其答案最近被标记为史诗般的答案，这让我感到疑惑；我可以根据 CPU 分支预测失败来衡量 Windows 中正在运行的应用程序的性能吗？我知道存在一些静态分析工具，它们可能有助于在分支预测情况下优化代码以获得良好的性能，并且手动技术可以通过简单地进行更改和重新测试来提供帮助，但我正在寻找一些可以在 Windows 应用程序运行时报告一段时间内分支预测失败的总数，我希望 Visual C++ 的一些 Profiler 工具可以帮助我。

对于这个问题，所讨论的应用程序要么是使用原生编译器（例如 Windows 的 Visual C++）构建的，要么是使用其他一些原生编译器（例如 GCC、FreePascal、Delphi 或 TurboAssembler）构建的。可执行文件可能根本没有任何调试信息。我想知道我是否可以检测和计算分支预测失败，可能是通过某些 Windows 服务（如 WMI）读取内部 CPU 信息，或者可能完全在运行 Windows 的虚拟化环境中运行，例如使用 VirtualBox，然后完全运行使用我的测试应用程序在 VirtualBox 中虚拟化 Windows 环境，并对虚拟 CPU 进行运行时分析。或者我不知道的其他一些技术，因此这个问题。

是的，我用谷歌搜索。唯一看起来很有希望的是来自 AMD的PDF 。第 18 页提到了一些非常接近我想做的事情，但似乎是为那些在原始评估硬件平台上没有任何操作系统工作的人编写的：

5.1。分支机构。适用性。条件分支错误预测可能是具有大量决策逻辑的代码中的一个重要问题。

Conditional branches may be mispredicted when the likelihood of choosing the true or false path is random or near a 50-50 split. 分支预测硬件无法“学习”模式，因此无法正确预测分支。收藏。收集此表中的事件以衡量分支预测性能：

分支 使用以下公式计算执行分支的速率和每个分支的指令数比率： 分支执行率 = Taken_branches / Ret_instructions 分支执行率 = Taken_branches / Branches
每个分支的指令 = Ret_instructions / Branches

更新：我想我可以说我正在寻找一种方法来读取英特尔酷睿 i7 PMU 模块或其他 CPU 的等效功能。看起来英特尔 VTUNE（来自 Adrian 的评论）非常接近我的要求。

我的问题来自神秘的回答。据我了解，您有一个分支指令，它可以转到另一条指令，比如，0x123344或者它可以继续执行。

如果分支预测器根据过去的模式从其中任何一个中进行猜测，它如何意识到自己犯了错误并恢复它？

我最近在这里阅读了这个问题为什么处理排序数组比处理未排序数组更快？并发现答案绝对令人着迷，并且在处理基于数据的分支时完全改变了我对编程的看法。

我目前有一个相当基本但功能齐全的解释型 Intel 8080 仿真器，用 C 语言编写，操作的核心是一个 256 长的 switch-case 表，用于处理每个操作码。我最初的想法是，这显然是最快的工作方法，因为操作码编码在整个 8080 指令集中并不一致，并且解码会增加很多复杂性、不一致和一次性情况。一个充满预处理器宏的 switch-case 表非常整洁且易于维护。

不幸的是，在阅读了上述帖子后，我突然想到，我计算机中的分支预测器绝对无法预测开关盒的跳跃。因此，每次切换开关盒被导航时，管道都必须被完全擦除，从而导致原本应该是一个非常快速的程序的几个周期延迟（我的代码中甚至没有乘法）。

我相信你们中的大多数人都在想“哦，这里的解决方案很简单，转向动态重新编译”。是的，这似乎确实会削减大部分开关盒并大大提高速度。不幸的是，我的主要兴趣是模拟较旧的 8 位和 16 位时代的控制台（这里的英特尔 8080 只是一个示例，因为它是我最简单的一段模拟代码），其中与视频和声音一样，保持精确指令的周期和时间很重要必须根据这些确切的时间进行处理。

当处理这种级别的准确性时，性能成为一个问题，即使对于较旧的控制台也是如此（例如，查看 bSnes）。在处理具有长管道的处理器时，是否有任何追索权，或者这只是一个事实？

这两个代码片段之间会有明显的速度差异吗？天真地，我认为第二个片段会更快，因为遇到的分支指令要少得多，但另一方面，分支预测器应该可以解决这个问题。还是尽管有可预测的模式，但它会产生明显的开销？假设没有使用条件移动指令。

片段1：

片段 2：

我不打算自己优化这些案例，但我想更多地了解分支的开销，即使具有可预测的模式。

The application that I'm dealing with has a large number of a if-statements with the characteristics that in any one execution, only one of the branches is executed 90% of the time.

Now, I can test the impact of branch prediction on a single if-statement for a specific CPU by doing something like this :-

My question is, is there a way of testing the scalability and impact of branch prediction with multiple if-statements in an actual large application for a given CPU?

Basically, I want to be able to figure out how much branch mispredicts are costing on various CPUs and their impact on the application.

所以我正在创建一个包含类 someBase {}; 的库。它将由下游用户在多个类中派生。

我还有一个指向 someBase 的指针向量，我正在这样做：-

现在分析表明，对虚拟调用的分支错误预测是我的代码中的一个（几个）瓶颈。我想做的是以某种方式访问​​对象的 RTTI，并使用它根据类类型对子向量进行排序，以改善指令缓存局部性和分支预测。

关于如何做到这一点的任何建议/解决方案？

要记住的主要挑战是：-

1.) 我真的不知道哪些类或多少类将从 someBase 派生。假设，我可以在某个公共文件的某个地方有一个全局枚举，下游用户可以编辑它以添加他们自己的类类型，然后对其进行排序（基本上实现我自己的 RTTI）。但这是一个丑陋的解决方案。

2.) PiotrNycz 在下面的回答中建议使用 type_info。但是，只有 != 和 == 是为此定义的。关于如何在 type_info 上得出严格的弱排序的任何想法？

3.) 我真的很想改进分支预测和指令缓存局部性，所以如果有替代解决方案，那也将受到欢迎。

从这里 - 一个分支预测问题，我开始编写程序的 Python 版本来检查 Python 中排序/未排序版本的运行时。我试过先排序。

这是代码：

我不确定我的简单计时方法的准确性，但它似乎已经足够好了。当我设置时，arraysize = 32768我第一次等了> 20分钟！超过20分钟！但是arraysize = 327，我得到了一个时间8.141656691s。

如果我在代码中的某个地方有错误，或者以某种方式使用 Numpy/Scipy 是否会加快速度，请纠正我。谢谢。