问题标签 [branch-prediction]

给定一些汇编代码，已知应该采用 90% 的分支。

我对分支条件一无所知。关于每个分支的采取或不采取的决定应该仅基于概率来完成。

分支的偏移量可以是正数或负数。

什么是正确的算法来做到这一点？

据Intel称，删除分支是优化 C 代码以在紧密循环中使用的最有效方法之一。但是，链接页面中的示例仅涵盖循环展开和将不变分支移动到循环之外。

是否有其他和不同（之前和之后）的分支删除示例以进行优化？

It's useful when execute this routine when LOOPS > BTB_SIZE, eg,

from

to

can reduce branch misses.

BTB ref:http://www-ee.eng.hawaii.edu/~tep/EE461/Notes/ILP/buffer.html but it doesn't tell how to get the BTB size.

所以今天早上我决定第一次玩基准测试。

我很好奇具有“do-end”块格式与“{}”格式的代码之间的速度差异。

所以我将 Benchmark 代码存储在 Proc 中，这样我就可以连续多次调用它：

当我运行一次时，我们的结果是预期的。

但后来又跑了。

对我来说，这看起来与我的预期完全相反。我熟悉分支预测的概念。这是分支预测的经典例子吗？如果不是，那是什么？有没有办法防止这样的不准确（如果这甚至被认为是一个）？

编辑：经过一些建议，我确实运行了这段代码超过 30 次。通常它会在两个结果之间交替。数据样本可在此处找到：

gist.github.com/TheLarkInn/5599676

在现代奔腾上，似乎不再可能向处理器提供分支提示。假设像 gcc 这样的配置文件编译器具有配置文件引导优化获得有关可能的分支行为的信息，它可以做些什么来生成执行更快的代码？

我知道的唯一选择是将不太可能的分支移动到函数的末尾。还有别的事吗？

更新。

http://download.intel.com/products/processor/manual/325462.pdf第 2a 卷，第 2.1.1 节说

“分支提示前缀 (2EH, 3EH) 允许程序向处理器提示最可能的分支代码路径。仅将这些前缀与条件分支指令 (Jcc) 一起使用。其他使用分支提示前缀和/或其他带有 Intel 64 或 IA-32 指令的未定义操作码被保留；这样的使用可能会导致不可预知的行为。”

我不知道这些是否真的有任何影响。

另一方面，第 3.4.1 节。http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf说_

" 编译器生成的代码可提高英特尔处理器中分支预测的效率。英特尔 C++ 编译器通过以下方式完成此任务：

• 将代码和数据保存在不同的页面上
• 使用条件移动指令消除分支
• 生成与静态分支预测算法一致的代码
• 在适当的地方内联
• 如果迭代次数是可预测的，则展开

通过配置文件引导优化，编译器可以布置基本块以消除函数最常执行路径的分支，或者至少提高它们的可预测性。分支预测不必是源级别的关注点。有关详细信息，请参阅英特尔 C++ 编译器文档。"

http://cache-www.intel.com/cd/00/00/40/60/406096_406096.pdf在“PGO 的性能改进”中说

" PGO 最适用于具有许多在编译时难以预测的频繁执行分支的代码。一个示例是具有密集错误检查的代码，其中错误条件大部分时间都是错误的。不经常执行（冷）错误处理代码可以重新定位，因此很少会错误地预测分支。将交错到频繁执行（热）代码中的冷代码最小化可以改善指令缓存行为。

我在 StackOverflow 上读到使用

由于容易受到分支错误预测的影响，可能效率低下（例如，请参阅此问题）。

-结构也是如此switch，例如，

在这方面有什么不同（除了我允许三种可能性之外）？

Matlab 是否使用分支预测来提高性能？也就是说，如果我们像这样扁平化 if 语句：

它会加快速度吗？

PS：我确实理解这个具体的例子可能永远不会用任何语言加速事情，但想象一些更复杂的事情，即嵌套 if 或多个具有多个条件的 else 语句......

为了了解 if 语句与选择性乘法，我尝试了下面的代码，发现将结果乘以 0 而不是 failed-if-statement(false) 并乘以 1 而不是 pass-if-statement(true) ，如果只有 3-4 个双精度乘法，if 语句会更慢，并且计算总是更快。

问题：虽然这种乘法即使在 cpu 上也更快，但它在 GPU(opencl/cuda) 上会如何执行？我的投票是绝对加速。单精度乘法的精度损失如何？我知道不可能总是有 1.00000，乘以 0.999999。可以说我不介意第 5 位的 sp 精度损失。

这更适合整数，但这至少对浮点数有意义吗？如果 float/half 比双倍更快/更快，那么这将更快。

结果：

任何人都可以重现类似的结果吗？if(){} 是第二个测试，所以 JIT 不能作弊？

代码：

CPU 为 FX8150 @ 4GHz

这是一篇很棒的文章，它讨论了低级优化技术，并展示了一个作者将昂贵的除法转换为便宜的比较的例子。 https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920

对于那些不想点击的人，基本上他转换了这个：

进入这个：

导致高达 6 倍的加速。

虽然比较非常便宜，但我一直听说分支非常昂贵，因为它们会导致管道停顿。由于关于分支的传统智慧，我永远不会考虑这样的方法。

为什么在这种情况下分支不是瓶颈？是因为我们在每次比较之后立即返回吗？是因为这里的代码很小，因此处理器不会有太多的错误预测吗？在什么情况下它会成为瓶颈并开始主导部门的成本？作者从不谈论这个。

谁能解决廉价比较和昂贵分支之间的明显争论？当然，优化的黄金法则是必须始终衡量。但是，至少对这个问题有一些直觉是很好的，这样人们就可以在尝试提出使代码更快的新方法时智能地使用比较。

谢谢！

我目前正在使用带有 SSE-2 指令的 x86-64 程序集编写一些 C99 标准库字符串函数的高度优化版本，例如strlen(),memset()等。

到目前为止，我已经在性能方面取得了出色的成绩，但是当我尝试进行更多优化时，有时会出现奇怪的行为。

例如，添加甚至删除一些简单的指令，或者只是重新组织一些与跳转一起使用的本地标签，会完全降低整体性能。就代码而言，绝对没有理由。

所以我的猜测是代码对齐和/或错误预测的分支存在一些问题。

我知道，即使使用相同的架构（x86-64），不同的 CPU 也有不同的分支预测算法。

但是，在 x86-64 上开发高性能时，是否有一些关于代码对齐和分支预测的一般建议？

特别是关于对齐，我是否应该确保跳转指令使用的所有标签都在 DWORD 上对齐？

在前面的代码中，我是否应该在之前使用 align 指令.label:，例如：

如果是这样，在使用 SSE-2 时对齐 DWORD 是否足够？

关于分支预测，是否有一种“首选”方式来组织跳转指令使用的标签，以帮助 CPU，或者今天的 CPU 是否足够聪明，可以在运行时通过计算分支的次数来确定这一点？

编辑

好的，这是一个具体的例子 - 这是strlen()SSE-2 的开始：

使用 1000 个字符的字符串运行 10'000'000 次大约需要 0.48 秒，这很好。
但它不检查 NULL 字符串输入。很明显，我将添加一个简单的检查：

同样的测试，它现在在 0.59 秒内运行。但是，如果我在此检查后对齐代码：

原来的表演又回来了。我使用 8 进行对齐，因为 4 不会改变任何东西。
谁能解释一下，并就何时对齐或不对齐代码段提供一些建议？

编辑 2

当然，并不是把每个分支目标都对齐那么简单。如果我这样做，性能通常会变得更糟，除非像上面的某些特定情况。