分支感知编程

Question

我正在阅读这个分支错误预测可能是影响应用程序性能的一个热点瓶颈。正如我所看到的，人们经常会显示出揭示问题的汇编代码，并且声明程序员通常能够预测分支在大多数情况下会走到哪里，并避免分支错误预测。

我的问题是：

1. 是否有可能使用一些高级编程技术(即、no程序集、)来避免分支错误预测？
2. 在用高级编程语言(我最感兴趣的是C和C++)中生成分支友好代码时，我应该记住什么？

欢迎使用代码示例和基准测试。

Answer 1

人们经常..。并且声明程序员通常可以预测一个分支的去向。

(*)经验丰富的程序员经常提醒说，人类程序员在预测这一点上非常糟糕。

1-是否有可能使用一些高级编程技术(即不装配)来避免分支错误预测？

不适用于标准的c++或c.至少对单个分支不适用。您可以做的是最小化依赖链的深度，这样分支错误预测就不会产生任何影响。现代cpus将执行分支的两种代码路径，并删除未选择的路径。然而，这是有限度的，这就是为什么分支预测只在深依赖链中起作用。

一些编译器提供了一些扩展，例如gcc中的期望。这是一个关于它的堆栈过流问题。更好的是，一些编译器(例如gcc)支持分析代码并自动检测最优预测。使用分析而不是手工工作是明智的，因为(*)。

2-在使用高级编程语言(我最感兴趣的是C和C++)中生成分支友好代码时，我应该记住什么？

首先，您应该记住，分支错误预测只会在程序中最关键的性能部分影响到您，并且在您测量并发现问题之前不要担心它。

但是我能做些什么呢?当一些分析器(val差儿，VTune，.)告诉我们，在foo.cpp的第n行，我得到了一个分支预测惩罚？

隆丁给出了非常明智的建议

1. 衡量它是否重要。
2. 如果有关系的话，那么
   • 最小化计算的依赖链的深度。如何做到这一点可能是相当复杂的，超出了我的专业知识，没有什么你可以做的不深入组装。在高级语言中，您可以做的是尽量减少有条件检查的数量(**)。否则，您将任由编译器优化决定。避免深度依赖链也允许更有效地使用无序的超标量处理器.
   • 让你的分支机构始终如一地可预测。这一点的影响可以在这个堆栈过流问题中看到。在这个问题中，数组上有一个循环。循环包含一个分支。分支取决于当前元素的大小。当数据被排序时，当使用特定的编译器编译并在特定的cpu上运行时，可以证明循环要快得多。当然，保持所有数据的排序也将花费cpu时间，可能比分支错误预测要多，所以，度量。

​

1. 如果仍然存在问题，请使用轮廓引导优化 (如果可用)。

2及3的次序可予更改。手工优化代码是一项很大的工作。另一方面，一些程序也很难收集分析数据。

(**)这样做的一种方法是通过例如展开循环来转换循环。您也可以让优化器自动完成它。但是，您必须进行度量，因为展开将影响您与缓存交互的方式，很可能最终会导致悲观。

Answer 2

Linux内核基于likely gcc构建器定义了__builtin_expect和unlikely宏：

    #define likely(x)   __builtin_expect(!!(x), 1)
    #define unlikely(x) __builtin_expect(!!(x), 0)

(关于这里中的宏定义，请参阅include/linux/compiler.h)

你可以像这样使用它们：

if (likely(a > 42)) {
    /* ... */
} 

或

if (unlikely(ret_value < 0)) {
    /* ... */
}

Answer 3

一般来说，保持热的内部循环与最常见的缓存大小相匹配是个好主意。也就是说，如果您的程序一次以小于32 k字节的块处理数据，并在其上做了大量的工作，那么您就很好地利用了L1缓存。

相反，如果您的热内循环通过100 most的数据而只对每个数据项执行一次操作，那么CPU将花费大部分时间从DRAM中获取数据。

这一点很重要，因为CPU之所以有分支预测，首先是为了能够为下一条指令预取操作数。通过排列代码，可以减少分支错误预测的性能后果，这样无论使用哪个分支，下一个数据都很有可能来自L1缓存。虽然不是一种完美的策略，但L1缓存大小似乎普遍停留在32或64K上；在整个行业中，这几乎是一件不变的事情。诚然，以这种方式编写代码通常并不简单，依赖于配置文件驱动的优化等可能是前面最简单的方法。

不管其他什么，是否会出现分支错误预测问题，取决于CPU的缓存大小、机器上还运行着什么、主内存带宽/延迟是什么等等。