c++ - 分支感知编程

Question

我正在阅读有关分支错误预测可能成为应用程序性能的热门瓶颈的信息。正如我所看到的，人们经常展示揭示问题的汇编代码，并声明程序员通常可以预测一个分支最多可以去哪里，并避免分支错误预测。

我的问题是:

1. 是否可以使用一些高级编程技术(即无汇编)避免分支错误预测？

2. 使用高级编程语言(我对 C 和 C++ 最感兴趣)生成对分支友好的代码应该注意什么？

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

Answer 1

people often ... and state that programmers usually can predict where a branch could go

(*) 有经验的程序员经常提醒人类程序员非常不擅长预测。

1- Is it possible to avoid branch mispredictions using some high level programming technique (i.e. no assembly)?

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

一些编译器提供了手动建议预测的扩展，例如 __builtin_expect在 gcc 中。这是 stackoverflow question关于它。更好的是，一些编译器(例如 gcc)支持分析代码并自动检测最佳预测。由于 (*)，使用分析而不是手动工作是明智的。

2- What should I keep in mind to produce branch-friendly code in a high level programming language (I'm mostly interested in C and C++)?

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

But what can I do when some profiler (valgrind, VTune, ...) tells that on line n of foo.cpp I got a branch prediction penalty?

Lundin 给出了非常明智的建议

1. 衡量是否重要。
2. 如果这很重要，那么
   • 尽量减少计算的依赖链深度。如何做到这一点可能非常复杂，超出了我的专业知识，如果不深入组装，您将无能为力。您可以在高级语言中做的是尽量减少条件检查的数量(**)。否则，您将受到编译器优化的摆布。避免深度依赖链还可以更有效地使用无序超标量处理器。
   • 让您的分支始终具有可预测性。可以在此 stackoverflow question 中看到其效果。 .在问题中，数组上有一个循环。循环包含一个分支。分支取决于当前元素的大小。对数据进行排序后，可以证明使用特定编译器编译并在特定 cpu 上运行时循环要快得多。当然，保持所有数据排序也会花费 cpu 时间，可能比分支错误预测更多，所以，测量。
3. 如果仍然有问题，请使用 profile guided optimization (如果有)。

2. 和 3. 的顺序可以互换。手动优化你的代码需要做很多工作。另一方面，对于某些程序来说，收集分析数据也很困难。

(**) 一种方法是通过例如展开循环来转换循环。您也可以让优化器自动执行此操作。但是您必须进行测量，因为展开会影响您与缓存交互的方式，并且很可能最终成为一种悲观化。