什么是根据概率排序if...else if语句的效果？

问题的原因是作者想探索if...else if语句的排序对程序性能的影响。作者通过对四个不同排序的if...else if语句进行基准测试来研究以下因素的影响：

1. 每个if语句的概率。

2. 迭代次数，以便分支预测器能够起作用。

3. 可能/不可能的编译器提示，即代码布局。

作者给出了四个不同排序的if...else if语句的示例代码，并通过基准测试来比较它们的性能。还有数据数组的初始化代码和基准测试的结果。

经过分析，作者得出以下结论：

1. if...else if语句的排序确实会影响程序的性能，不同的排序可能会导致性能差异。

2. 迭代次数对程序性能也有影响，迭代次数越多性能越差。

3. 编译器提示可以在一定程度上改善程序性能，但效果有限。

作者建议在进行代码优化之前进行基准测试，因为实际结果可能会与预期不同。

文章最后，作者提到了自己的处理器型号和编译器选项，并强调了测量性能的重要性。

通过基准测试来评估代码性能对于优化代码非常重要，因为预期结果可能与实际结果不同。

文章标题：if...else if语句按概率排序的影响是什么？

在上述代码中，我测试了两个不同的按概率排序和按相反顺序排序的if...else if代码块的执行时间。经过测试，使用按概率排序的代码块比使用按相反顺序排序的代码块快约28%。值得一提的是，我还调换了两个测试的顺序，发现这样做也会有明显的差异（22%和28%）。这段代码在Windows7上的Intel Xeon E5-2697 v2处理器上运行。当然，这只是一个特定问题的测试结果，并不能作为定论。

然而，需要注意的是，更改if...else if语句的顺序可能会对代码的逻辑流程产生重大影响。尽管不太可能出现的情况可能不会经常发生，但在检查其他条件之前，可能有业务需求需要首先检查不太可能的条件。

测试中使用了一个随机数向量来干扰分支预测。我还使用了一个有序向量进行测试，结果显示在性能上几乎没有差异。

某些情况下，测试结果可能不具有可移植性，因此我使用了MSVC2017编译器进行测试，测试结果表明按概率排序的条件语句比按相反顺序排序的条件语句快约30%。这一结果在不同的编译器、CPU等环境下可能会有所不同。

另外，我尝试过改变测试的顺序，但结果并没有明显的差异，这也是一个有趣的发现。

这个微基准测试存在一个问题，即当你重复循环时，CPU会计算出哪个分支最有可能出现，并将其缓存起来。如果这些分支在一个小的紧凑循环中没有被检查到，分支预测缓存可能不会包含它们，如果CPU对分支的预测错误，那么开销可能会更高。

这个测试在某种程度上是非常悲观的（我们在分支中基本上没有做任何工作，所以额外的比较会非常明显），但同时又是非常乐观的（任何现代x86 CPU中的分支预测器都会确保错误预测的惩罚在两个代码片段之间是相同的）。你可以通过调整两个参数来使得这个基准测试返回任何你想要的结果。

实际上，我可以想到一个不太可能的场景需要首先检查。检查null值。它可能不太可能发生，但你绝对必须首先检查它，否则你的程序将崩溃。

这个基准测试并不太可靠。使用gcc 6.3.0进行编译，对于调试版本，排序后的条件语句稍微占优势，但大多数情况下，两次运行之间的百分比差异约为5%。有几次，速度实际上更慢（因为存在差异）。我相信按照这种顺序排序if语句不值得担心，PGO（Profile-Guided Optimization）可能会完全处理任何这样的情况。

有趣的是，一旦我开启了PGO，排序后的版本往往运行得更慢。编译器能够为反向排序的版本生成更小的汇编代码。这并不意味着你应该按照概率排序的顺序编写代码，但如果你正在考虑这个问题，你应该首先开启编译器优化（设置目标架构、使用LTO（Link Time Optimization）等）。

我更新了测试代码，以更好地代表我的实际用例。主要的区别是每次重复比较测试时，我都会生成一个新的随机向量。旧的代码对于每个测试都使用相同的随机数序列。

在MacOS上使用clang进行测试时，我发现在调试版本中差异约为17%，但在发布版本中，差异降低到1-2%。我认为你的编译器没有意识到第一个循环中的(i >= 20 && i < 95)总是为真。删除这个不必要的条件，差异应该基本消失。

我在Ubuntu上使用GCC 5.4进行了相同的测试，运行在Core i7处理器上。结果与Windows/MSVC版本相差很大。现在，我发现按照相反顺序排序的if语句比按概率排序的if语句运行得更快（约为3%）。不清楚两者之间为什么会有这么大的差异。

"sorted version"这句话的意思是什么？它们都是排序的。这个陈述含糊不清，让人困惑。

这是一个例子，说明不应该手动优化编译器已经设计好的优化方法（如PGO）。在这里，最佳解决方案是使用胡-塔克(Hu-Tucker)形状的分支树（一种保持顺序的最佳深度树）。在这个简单的例子中，只需要进行2次比较（而不是4次），而且这段代码可以很容易地写成无分支的形式（某些编译器可能会这样做）。PGO会为你处理所有这些。

任何优秀的优化器都会提升i < 20和i < 95（或等价的）的判断。所以性能差异很可能是由于分支的位置不同。但是，基于单个编译器和目标架构的广泛陈述至少是不明智的。

当然，这个结果是可以理解的，因为最小化要执行的操作的数量是优化的目的。我认为这仍然是一个有用的结果，因为很多人似乎认为编译器会自动找到所有可能的优化，因此手动优化没有意义。这是一个明确的例子，证明这种情况并非如此。

"比未排序的版本快约28%" - 你是指"比按相反顺序排序的版本快"吗？正如前面的评论者指出的，它们都是排序的。

在编写代码时，if...else if语句的顺序会影响到分支预测的效果。分支预测是指处理器在执行分支指令时，根据之前的历史记录来预测下一次分支的方向，从而提高指令的执行效率。

一般来说，大多数Intel CPU在首次遇到分支指令时会默认不采取分支。之后，分支会进入分支预测缓存，并根据过去的行为来进行下一次分支预测。所以在一个紧密的循环中，分支指令顺序的错位效果相对较小。分支预测器会学习到哪个分支的可能性最大，如果循环中有相当数量的工作，这些小的差异不会对性能产生太大的影响。

在一般的代码中，大多数编译器默认情况下会按照代码中的顺序生成机器代码。因此，if语句在失败时相当于是向前的分支。因此，为了获得最佳的分支预测效果，应该按照可能性递减的顺序来编写if语句。

对于一个紧密循环中多次遍历一组条件并进行简单操作的微基准测试，由于指令数量等微小差异的影响较小，并且相对分支预测问题来说影响较小，所以在这种情况下，你必须进行性能分析，因为经验法则可能不可靠。

此外，向量化和许多其他优化也适用于小型紧密循环。

因此，在一般的代码中，将最有可能出现的情况放在if语句块中，这样可以减少未缓存的分支预测错误。在紧密循环中，按照一般规则开始，如果需要了解更多信息，除了进行性能分析外别无选择。

当然，如果某些测试比其他测试便宜得多，那么也值得考虑测试本身的开销：如果一个测试只是略微更有可能发生，但开销很大，那么将另一个测试放在前面可能更值得，因为不进行昂贵的测试所节省的开销可能会超过分支预测的节省等。

CPU在处理分支指令时不再像过去那样使用静态预测。现代的Intel CPU可能使用类似概率TAGE（Tagged Geometric History Length Predictor）的预测器。它会将分支历史记录哈希到不同的历史表中，并选择与最长历史记录匹配的表来进行预测。它使用一个"标签"来避免别名问题，但标签只有几个比特。如果在所有历史长度上都没有命中，可能会进行一些默认的预测，这不一定依赖于分支方向（在Haswell上可以明确说不依赖）。

根据提供的链接，不支持你的结论"大多数Intel CPU在首次遇到分支指令时会默认不采取分支"。事实上，这只适用于相对较为冷门的Arrendale CPU，而主流的Ivy Bridge和Haswell CPU的结果并不支持这一结论。Haswell CPU看起来非常接近"总是预测不采取分支"，而Ivy Bridge则并不明确。

if...else if语句的顺序会影响到分支预测的效果。为了获得最佳的分支预测效果，应该按照可能性递减的顺序编写if语句。在紧密循环中，一般规则是首选，如果需要更多信息，则必须进行性能分析。此外，还应考虑测试本身的开销和不同CPU架构的特点。