分支感知编程
Branch-aware programming
我了解到分支预测错误可能是应用程序性能的一个热点瓶颈。正如我所看到的，人们经常展示 assembly 代码来揭示问题，并指出程序员通常可以预测大部分时间分支可以去哪里并避免分支错误预测。
我的问题是：
是否可以使用一些高级编程技术避免分支错误预测（即没有集会)?
要使用高级编程语言（我最感兴趣的是 C 和 C++）生成 分支友好 代码，我应该记住什么？
欢迎使用代码示例和基准。
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 in gcc. Here is a 关于它。更好的是，一些编译器（例如 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?
伦丁给出了非常明智的建议
- 衡量一下是否重要。
- 如果重要，那么
- 最小化计算的依赖链深度。如何做到这一点可能非常复杂，超出了我的专业知识范围，而且如果不深入组装，您将无能为力。你可以用高级语言做的是尽量减少条件检查的数量（**）。否则，您将受到编译器优化的支配。避免深度依赖链还允许更有效地使用乱序超标量处理器。
- 使您的分支始终可预测。其效果可见于此Whosebug question。在问题中，数组有一个循环。循环包含一个分支。分支取决于当前元素的大小。当数据被排序时，可以证明循环在使用特定编译器和 运行 在特定 cpu 上编译时要快得多。当然，保持所有数据排序也会花费 cpu 时间，可能比分支错误预测花费的时间更多，因此，measure.
- 如果问题仍然存在，请使用 profile guided optimization（如果可用）。
2.和3.的顺序可能会调换。手动优化代码需要大量工作。另一方面，收集分析数据对于某些程序来说也很困难。
(**) 一种方法是通过展开循环来转换循环。您也可以让优化器自动执行。但是您必须进行衡量，因为展开会影响您与缓存交互的方式，并且很可能最终成为一种悲观情绪。
Linux 内核定义 likely 和 unlikely 宏基于 __builtin_expect gcc builtins:
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
（include/linux/compiler.h 中的宏定义参见 here）
您可以像这样使用它们：
if (likely(a > 42)) {
/* ... */
}
或
if (unlikely(ret_value < 0)) {
/* ... */
}
一般来说，让热内循环与最常遇到的缓存大小保持良好的比例是个好主意。也就是说，如果您的程序一次处理小于 32kbytes 的块状数据，并且对其进行相当多的工作，那么您就充分利用了 L1 缓存。
相比之下，如果您的热内循环咀嚼 100MByte 的数据并且对每个数据项只执行一个操作，那么 CPU 将花费大部分时间从 DRAM 中获取数据。
这很重要，因为 CPU 首先进行分支预测的部分原因是能够为下一条指令预取操作数。可以通过安排代码来减少分支预测错误的性能后果，这样无论采用哪个分支，下一个数据都有可能来自 L1 缓存。虽然不是一个完美的策略，但 L1 缓存大小似乎普遍停留在 32 或 64K；这几乎是整个行业的常态。诚然，以这种方式编码通常并不直接，而依靠其他人推荐的配置文件驱动优化等可能是最直接的方法。
不管别的，是否会出现分支预测错误的问题取决于CPU的缓存大小，运行在机器上还有什么，什么主存带宽/延迟等
1- Is it possible to avoid branch mispredictions using some high level programming technique (i.e. no assembly)?
回避？也许不是。减少？当然...
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++)?
值得注意的是，对一台机器的优化不一定是对另一台机器的优化。考虑到这一点，profile-guided optimisation 相当擅长根据您提供的任何测试输入重新排列分支。这意味着你不需要任何编程来执行这个优化，而且它应该相对适合你正在分析的任何机器.显然，当您的测试输入和您分析的机器大致符合常见期望时，将获得最佳结果……但这些也是任何其他优化、分支预测相关或其他方面的考虑因素。
也许最常见的技术是对正常和错误使用不同的方法returns。 C没有选择，但C++有例外。编译器知道异常分支是异常的，因此是意外的。
这意味着异常分支确实很慢，因为它们是不可预测的，但非错误分支变得更快。平均而言，这是净赢。
请注意，我不是微优化向导。我不确切知道硬件分支预测器是如何工作的。对我来说，它是一种神奇的野兽，我可以和它玩剪刀布石头游戏，它似乎能够读懂我的想法并一直打败我。我是设计和建筑类型。
尽管如此，由于这个问题是关于高层次的心态，我也许可以提供一些提示。
分析
如前所述，我不是计算机体系结构向导，但我确实知道如何使用 VTune 分析代码并测量诸如分支预测错误和缓存未命中之类的事情，并且在性能关键领域一直这样做。如果您不知道如何执行此操作（分析），那么这是您应该研究的第一件事。这些微观热点中的大多数都是事后发现最好的方法，手头有探查器。
分支消除
很多人就如何提高分支机构的可预测性提供了一些极好的低级建议。在某些情况下，您甚至可以手动尝试帮助分支预测器并优化静态分支预测（编写 if 语句以首先检查常见情况，例如）。这里有一篇来自英特尔的关于细节的综合文章：https://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts。
然而，在基本的常见 case/rare 案例预测之外做到这一点非常困难，而且几乎总是最好保存以供以后 测量之后使用。人类很难准确预测分支预测器的性质。它比页面错误和缓存未命中之类的事情更难预测，甚至那些在复杂的代码库中几乎不可能完全由人工预测。
但是，有一种更简单的高级方法可以减少分支预测错误，那就是完全避免分支。
逃课Small/Rare工作
我在职业生涯早期经常犯的一个错误是，看到很多同行在刚起步时，在他们学会分析并且仍然凭直觉行事之前，试图做的是尝试跳过小的或稀有的工作。
这方面的一个例子是记忆大型查找 table 以避免重复执行一些相对便宜的计算，例如使用跨越兆字节的查找 table 以避免重复调用cos 和 sin。对人脑来说，这似乎节省了计算一次并存储它的工作量，除了经常从这个巨大的 LUT 加载内存，通过内存层次结构向下加载到寄存器中，结果往往比预期的计算成本更高保存。
另一种情况是添加一堆小分支以避免在整个代码中进行不必要的小计算（不会影响正确性）作为天真的优化尝试，结果发现分支成本不仅仅是做不必要的计算。
这种将分支作为优化的幼稚尝试也适用于成本稍高但很少见的工作。以这个 C++ 为例：
struct Foo
{
...
Foo& operator=(const Foo& other)
{
// Avoid unnecessary self-assignment.
if (this != &other)
{
...
}
return *this;
}
...
};
请注意，这有点像 simplistic/illustrative 示例，因为大多数人使用复制和交换对按值传递的参数执行复制分配，并且无论如何都避免分支不管怎样
在本例中，我们进行分支以避免自我赋值。然而，如果自赋值只是在做多余的工作并且不影响结果的正确性，那么简单地允许自复制通常可以提高实际性能：
struct Foo
{
...
Foo& operator=(const Foo& other)
{
// Don't check for self-assignment.
...
return *this;
}
...
};
...这会有所帮助，因为自我分配往往很少见。我们通过冗余自分配来减缓罕见情况，但我们通过避免检查所有其他情况来加快常见情况。当然，这不太可能显着减少分支预测错误，因为在分支方面存在 common/rare 案例偏差，但是嘿，一个不存在的分支不会被错误预测。
小向量的幼稚尝试
作为个人故事，我以前在一个大型 C 代码库中工作，其中经常有很多这样的代码：
char str[256];
// do stuff with 'str'
...自然而然，由于我们拥有相当广泛的用户群，一些稀有用户最终会在我们的软件中输入长度超过 255 个字符的 material 的名称并溢出缓冲区，导致段错误。我们的团队开始使用 C++ 并开始将大量这些源文件移植到 C++ 并用以下代码替换此类代码：
std::string str = ...;
// do stuff with 'str'
... 毫不费力地消除了那些缓冲区溢出。然而，至少在那时，像 std::string 和 std::vector 这样的容器是堆（自由存储）分配的结构，我们发现自己用 correctness/safety 来换取效率。其中一些替换区域对性能至关重要（在紧密循环中调用），虽然我们通过这些大规模替换消除了很多错误报告，但用户开始注意到速度变慢。
然后我们想要一种类似于这两种技术的混合体。我们希望能够在其中添加一些东西以实现 C 风格固定缓冲区变体的安全性（对于常见情况来说非常好并且非常有效），但仍然适用于缓冲区不存在的罕见情况足够大以供用户输入。我是团队中的性能极客之一，也是为数不多的使用分析器的人之一（不幸的是，我和很多认为他们太聪明而不能使用分析器的人一起工作），所以我被召集到这个任务中。
我第一次天真的尝试是这样的（大大简化了：实际使用的是 placement new 等等，并且是一个完全符合标准的序列）。它涉及为常见情况使用固定大小的缓冲区（在编译时指定大小），如果大小超过该容量则使用动态分配的缓冲区。
template <class T, int N>
class SmallVector
{
public:
...
T& operator[](int n)
{
return num < N ? buf[n]: ptr[n];
}
...
private:
T buf[N];
T* ptr;
};
这次尝试彻底失败了。虽然它没有为构建 heap/free 商店付出代价，但 operator[] 中的分支使其比 std::string 和 std::vector<char> 更糟糕，并且显示为分析hotspot 而不是 malloc（我们的 std::allocator 和 operator new 的供应商实现在幕后使用 malloc。所以我很快想到在构造函数中简单地将 ptr 分配给 buf 。现在 ptr 即使在常见情况下也指向 buf，现在 operator[] 可以这样实现：
T& operator[](int n)
{
return ptr[n];
}
...通过简单的分支消除，我们的热点消失了。我们现在有了一个通用的、符合标准的容器，我们可以使用它，它的速度与以前的 C 风格、固定缓冲区解决方案差不多（唯一的区别是构造函数中多了一个指针和几条指令），但是可以处理那些大小需要大于 N 的罕见情况。现在我们使用它的次数甚至超过 std::vector（但这只是因为我们的用例偏爱一堆极小的、临时的、连续的、随机访问的容器）。让它变快归结为只删除 operator[].
中的一个分支
常见 Case/Rare 大小写倾斜
经过多年的分析和优化后学到的一件事是，没有 "absolutely-fast-everywhere" 代码这样的东西。很多优化行为是用那里的低效率换取这里的更高效率。用户可能会认为您的代码处处绝对快速，但这是来自智能权衡，其中优化与常见情况保持一致（常见情况既符合实际的用户端场景又符合实际情况）来自测量这些常见场景的分析器指出的热点）。
当您将性能偏向常见情况而远离罕见情况时，往往会发生好事。为了使常见情况变得更快，罕见情况通常必须变得更慢，但这是一件好事。
零成本异常处理
常见 case/rare 大小写倾斜的一个例子是许多现代编译器中使用的异常处理技术。他们应用零成本 EH，这并不是真正的 "zero-cost" 全面。在抛出异常的情况下，它们现在比以往任何时候都慢。然而，在没有抛出异常的情况下，它们现在比以往任何时候都更快，而且在成功的场景中通常比这样的代码更快：
if (!try_something())
return error;
if (!try_something_else())
return error;
...
当我们在这里使用零成本 EH 并避免手动检查和传播错误时，在非异常情况下，事情往往比上面这种代码风格更快。粗略地说，这是由于分支减少。然而，作为交换，抛出异常时必须发生更昂贵的事情。然而，常见案例和罕见案例之间的偏差往往有助于现实世界的场景。我们不太关心加载文件失败（罕见情况）的速度，而是成功加载文件（常见情况）的速度，这就是为什么许多现代 C++ 编译器实现 "zero-cost" EH 的原因。这又是为了歪曲常见情况和罕见情况，使它们在性能方面相距更远。
虚拟调度和同质化
面向对象代码中的大量分支，其中依赖项流向抽象（例如，stable 抽象原则），可以有大量的分支（当然除了循环，循环很好到分支预测器）以动态调度（虚函数调用或函数指针调用）的形式。
在这些情况下，一个常见的诱惑是将所有类型的子类型聚合到一个存储基指针的多态容器中，遍历它并在该容器中的每个元素上调用虚拟方法。这可能会导致很多分支预测错误，尤其是当这个容器一直在更新的时候。伪代码可能如下所示：
for each entity in world:
entity.do_something() // virtual call
避免这种情况的策略是开始根据其子类型对该多态容器进行排序。这是游戏行业中流行的一种相当老式的优化。我不知道它今天有多大帮助，但它是一种高级优化。
即使在最近的案例中，我发现另一种绝对有用的方法也能达到类似的效果，那就是将多态容器分解为每个子类型的多个容器，导致代码如下：
for each human in world.humans():
human.do_something()
for each orc in world.orcs():
orc.do_something()
for each creature in world.creatures():
creature.do_something()
...自然这就妨碍了代码的可维护性，降低了可扩展性。但是，您不必为这个世界上的每个子类型都这样做。我们只需要做最常见的。例如，这个想象中的视频游戏可能到目前为止由人类和兽人组成。它也可能有仙女、妖精、巨魔、精灵、侏儒等，但它们可能不像人类和兽人那么普遍。所以我们只需要将人类和兽人分开即可。如果您负担得起，您还可以拥有一个多态容器来存储所有这些子类型，我们可以将其用于对性能要求较低的循环。这有点类似于 hot/cold 用于优化参考位置的拆分。
面向数据的优化
优化分支预测和优化内存布局往往有点模糊。我很少尝试特别是 分支预测器的优化，那是在我用尽所有其他方法之后。然而，我发现非常关注内存和参考位置确实使我的测量导致更少的分支预测错误（通常不知道确切原因）。
这里可以帮助学习面向数据的设计。我发现一些与优化相关的最有用的知识来自于在面向数据的设计环境中研究内存优化。面向数据的设计倾向于强调更少的抽象（如果有的话），以及处理大块数据的更庞大的高级接口。从本质上讲，此类设计倾向于减少代码中不同分支和跳转的数量，并使用更多循环代码处理大块同类数据。
即使您的目标是减少分支预测错误，也可以更专注于更快地使用数据，这通常会有所帮助。例如，我之前从无分支 SIMD 中发现了一些巨大的收获，但是我的心态仍然是更快地消耗数据（它确实做到了，并且感谢像 Harold 这样的 SO 的一些帮助）。
TL;DR
所以无论如何，这些是一些策略，可以从高层的角度减少整个代码中的分支预测错误。他们在计算机体系结构方面缺乏最高水平的专业知识，但我希望鉴于所问问题的级别，这是一种适当的有用回答。很多这样的建议在一般情况下都与优化有些模糊，但我发现分支预测的优化通常需要与超越它的优化（内存、并行化、矢量化、算法）相混淆。无论如何，最安全的做法是在你深入探索之前确保你手上有一个剖面仪。
无分支并不总是更好，即使分支的两边都很微不足道。 When branch prediction works, it's faster than a loop-carried data dependency.
请参阅 以了解 gcc -O3 将 if() 转换为无分支代码的情况，因为它非常可预测，因此速度较慢。
有时您确信条件是不可预测的（例如在排序算法或二进制搜索中）。或者你更关心最坏情况不慢 10 倍，而不是快速情况快 1.5 倍。
一些习语更有可能编译成无分支形式（如 cmov x86 条件移动指令）。
x = x>limit ? limit : x; // likely to compile branchless
if (x>limit) x=limit; // less likely to compile branchless, but still can
第一种方式总是写入 x，而第二种方式不修改其中一个分支中的 x。这似乎是某些编译器倾向于为 if 版本发出分支而不是 cmov 的原因。即使 x 是一个已经存在于寄存器中的局部 int 变量，这也适用，因此 "writing" 它不涉及存储到内存，只是更改寄存器中的值。
编译器仍然可以为所欲为，但我发现这种习惯用法的差异会产生影响。根据您正在测试的内容， 我在那个答案中做到了，因为我知道编译器将拥有用一条指令生成掩码所需的东西（并通过查看 clang 是如何做到的）。
TODO：关于 http://gcc.godbolt.org/
的示例
为了回答您的问题，让我解释一下分支预测是如何工作的。
首先，当处理器正确预测采取的分支时，会有分支惩罚。如果处理器预测一个分支被采用，那么它必须知道预测分支的目标，因为执行流将从该地址继续。假设分支目标地址已经存储在分支目标缓冲区（BTB）中，它必须从 BTB 中找到的地址获取新指令。所以即使正确预测了分支，你仍然在浪费几个时钟周期。
由于 BTB 具有关联缓存结构，目标地址可能不存在，因此可能会浪费更多时钟周期。
另一方面，如果 CPU 预测一个分支没有被采纳，并且如果它是正确的，那么就没有惩罚，因为 CPU 已经知道连续的指令在哪里。
正如我上面所解释的，预测未采用的分支比预测采用的分支具有更高的吞吐量。
Is it possible to avoid branch misprediction using some high level programming technique (i.e. no assembly)?
是的，这是可能的。您可以通过组织代码的方式避免所有分支都具有重复的分支模式，例如总是采用或不采用。
但是如果你想获得更高的吞吐量，你应该按照我上面解释的最有可能不被采用的方式组织分支。
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++)?
如果可能的话尽量去掉分支。如果在编写 if-else 或 switch 语句时不是这种情况，请首先检查最常见的情况，以确保最有可能不采用的分支。尝试使用 __builtin_expect(condition, 1) 函数强制编译器生成条件，将其视为未采用。
我了解到分支预测错误可能是应用程序性能的一个热点瓶颈。正如我所看到的，人们经常展示 assembly 代码来揭示问题，并指出程序员通常可以预测大部分时间分支可以去哪里并避免分支错误预测。
我的问题是：
是否可以使用一些高级编程技术避免分支错误预测（即没有集会)?
要使用高级编程语言（我最感兴趣的是 C 和 C++）生成 分支友好 代码，我应该记住什么？
欢迎使用代码示例和基准。
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 in gcc. Here is a
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?
伦丁给出了非常明智的建议
- 衡量一下是否重要。
- 如果重要，那么
- 最小化计算的依赖链深度。如何做到这一点可能非常复杂，超出了我的专业知识范围，而且如果不深入组装，您将无能为力。你可以用高级语言做的是尽量减少条件检查的数量（**）。否则，您将受到编译器优化的支配。避免深度依赖链还允许更有效地使用乱序超标量处理器。
- 使您的分支始终可预测。其效果可见于此Whosebug question。在问题中，数组有一个循环。循环包含一个分支。分支取决于当前元素的大小。当数据被排序时，可以证明循环在使用特定编译器和 运行 在特定 cpu 上编译时要快得多。当然，保持所有数据排序也会花费 cpu 时间，可能比分支错误预测花费的时间更多，因此，measure.
- 如果问题仍然存在，请使用 profile guided optimization（如果可用）。
2.和3.的顺序可能会调换。手动优化代码需要大量工作。另一方面，收集分析数据对于某些程序来说也很困难。
(**) 一种方法是通过展开循环来转换循环。您也可以让优化器自动执行。但是您必须进行衡量，因为展开会影响您与缓存交互的方式，并且很可能最终成为一种悲观情绪。
Linux 内核定义 likely 和 unlikely 宏基于 __builtin_expect gcc builtins:
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
（include/linux/compiler.h 中的宏定义参见 here）
您可以像这样使用它们：
if (likely(a > 42)) {
/* ... */
}
或
if (unlikely(ret_value < 0)) {
/* ... */
}
一般来说，让热内循环与最常遇到的缓存大小保持良好的比例是个好主意。也就是说，如果您的程序一次处理小于 32kbytes 的块状数据，并且对其进行相当多的工作，那么您就充分利用了 L1 缓存。
相比之下，如果您的热内循环咀嚼 100MByte 的数据并且对每个数据项只执行一个操作，那么 CPU 将花费大部分时间从 DRAM 中获取数据。
这很重要，因为 CPU 首先进行分支预测的部分原因是能够为下一条指令预取操作数。可以通过安排代码来减少分支预测错误的性能后果，这样无论采用哪个分支，下一个数据都有可能来自 L1 缓存。虽然不是一个完美的策略，但 L1 缓存大小似乎普遍停留在 32 或 64K；这几乎是整个行业的常态。诚然，以这种方式编码通常并不直接，而依靠其他人推荐的配置文件驱动优化等可能是最直接的方法。
不管别的，是否会出现分支预测错误的问题取决于CPU的缓存大小，运行在机器上还有什么，什么主存带宽/延迟等
1- Is it possible to avoid branch mispredictions using some high level programming technique (i.e. no assembly)?
回避？也许不是。减少？当然...
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++)?
值得注意的是，对一台机器的优化不一定是对另一台机器的优化。考虑到这一点，profile-guided optimisation 相当擅长根据您提供的任何测试输入重新排列分支。这意味着你不需要任何编程来执行这个优化，而且它应该相对适合你正在分析的任何机器.显然，当您的测试输入和您分析的机器大致符合常见期望时，将获得最佳结果……但这些也是任何其他优化、分支预测相关或其他方面的考虑因素。
也许最常见的技术是对正常和错误使用不同的方法returns。 C没有选择，但C++有例外。编译器知道异常分支是异常的，因此是意外的。
这意味着异常分支确实很慢，因为它们是不可预测的，但非错误分支变得更快。平均而言，这是净赢。
请注意，我不是微优化向导。我不确切知道硬件分支预测器是如何工作的。对我来说，它是一种神奇的野兽，我可以和它玩剪刀布石头游戏，它似乎能够读懂我的想法并一直打败我。我是设计和建筑类型。
尽管如此，由于这个问题是关于高层次的心态，我也许可以提供一些提示。
分析
如前所述，我不是计算机体系结构向导，但我确实知道如何使用 VTune 分析代码并测量诸如分支预测错误和缓存未命中之类的事情，并且在性能关键领域一直这样做。如果您不知道如何执行此操作（分析），那么这是您应该研究的第一件事。这些微观热点中的大多数都是事后发现最好的方法，手头有探查器。
分支消除
很多人就如何提高分支机构的可预测性提供了一些极好的低级建议。在某些情况下，您甚至可以手动尝试帮助分支预测器并优化静态分支预测（编写 if 语句以首先检查常见情况，例如）。这里有一篇来自英特尔的关于细节的综合文章：https://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts。
然而，在基本的常见 case/rare 案例预测之外做到这一点非常困难，而且几乎总是最好保存以供以后 测量之后使用。人类很难准确预测分支预测器的性质。它比页面错误和缓存未命中之类的事情更难预测，甚至那些在复杂的代码库中几乎不可能完全由人工预测。
但是，有一种更简单的高级方法可以减少分支预测错误，那就是完全避免分支。
逃课Small/Rare工作
我在职业生涯早期经常犯的一个错误是，看到很多同行在刚起步时，在他们学会分析并且仍然凭直觉行事之前，试图做的是尝试跳过小的或稀有的工作。
这方面的一个例子是记忆大型查找 table 以避免重复执行一些相对便宜的计算，例如使用跨越兆字节的查找 table 以避免重复调用cos 和 sin。对人脑来说，这似乎节省了计算一次并存储它的工作量，除了经常从这个巨大的 LUT 加载内存，通过内存层次结构向下加载到寄存器中，结果往往比预期的计算成本更高保存。
另一种情况是添加一堆小分支以避免在整个代码中进行不必要的小计算（不会影响正确性）作为天真的优化尝试，结果发现分支成本不仅仅是做不必要的计算。
这种将分支作为优化的幼稚尝试也适用于成本稍高但很少见的工作。以这个 C++ 为例：
struct Foo
{
...
Foo& operator=(const Foo& other)
{
// Avoid unnecessary self-assignment.
if (this != &other)
{
...
}
return *this;
}
...
};
请注意，这有点像 simplistic/illustrative 示例，因为大多数人使用复制和交换对按值传递的参数执行复制分配，并且无论如何都避免分支不管怎样
在本例中，我们进行分支以避免自我赋值。然而，如果自赋值只是在做多余的工作并且不影响结果的正确性，那么简单地允许自复制通常可以提高实际性能：
struct Foo
{
...
Foo& operator=(const Foo& other)
{
// Don't check for self-assignment.
...
return *this;
}
...
};
...这会有所帮助，因为自我分配往往很少见。我们通过冗余自分配来减缓罕见情况，但我们通过避免检查所有其他情况来加快常见情况。当然，这不太可能显着减少分支预测错误，因为在分支方面存在 common/rare 案例偏差，但是嘿，一个不存在的分支不会被错误预测。
小向量的幼稚尝试
作为个人故事，我以前在一个大型 C 代码库中工作，其中经常有很多这样的代码：
char str[256];
// do stuff with 'str'
...自然而然，由于我们拥有相当广泛的用户群，一些稀有用户最终会在我们的软件中输入长度超过 255 个字符的 material 的名称并溢出缓冲区，导致段错误。我们的团队开始使用 C++ 并开始将大量这些源文件移植到 C++ 并用以下代码替换此类代码：
std::string str = ...;
// do stuff with 'str'
... 毫不费力地消除了那些缓冲区溢出。然而，至少在那时，像 std::string 和 std::vector 这样的容器是堆（自由存储）分配的结构，我们发现自己用 correctness/safety 来换取效率。其中一些替换区域对性能至关重要（在紧密循环中调用），虽然我们通过这些大规模替换消除了很多错误报告，但用户开始注意到速度变慢。
然后我们想要一种类似于这两种技术的混合体。我们希望能够在其中添加一些东西以实现 C 风格固定缓冲区变体的安全性（对于常见情况来说非常好并且非常有效），但仍然适用于缓冲区不存在的罕见情况足够大以供用户输入。我是团队中的性能极客之一，也是为数不多的使用分析器的人之一（不幸的是，我和很多认为他们太聪明而不能使用分析器的人一起工作），所以我被召集到这个任务中。
我第一次天真的尝试是这样的（大大简化了：实际使用的是 placement new 等等，并且是一个完全符合标准的序列）。它涉及为常见情况使用固定大小的缓冲区（在编译时指定大小），如果大小超过该容量则使用动态分配的缓冲区。
template <class T, int N>
class SmallVector
{
public:
...
T& operator[](int n)
{
return num < N ? buf[n]: ptr[n];
}
...
private:
T buf[N];
T* ptr;
};
这次尝试彻底失败了。虽然它没有为构建 heap/free 商店付出代价，但 operator[] 中的分支使其比 std::string 和 std::vector<char> 更糟糕，并且显示为分析hotspot 而不是 malloc（我们的 std::allocator 和 operator new 的供应商实现在幕后使用 malloc。所以我很快想到在构造函数中简单地将 ptr 分配给 buf 。现在 ptr 即使在常见情况下也指向 buf，现在 operator[] 可以这样实现：
T& operator[](int n)
{
return ptr[n];
}
...通过简单的分支消除，我们的热点消失了。我们现在有了一个通用的、符合标准的容器，我们可以使用它，它的速度与以前的 C 风格、固定缓冲区解决方案差不多（唯一的区别是构造函数中多了一个指针和几条指令），但是可以处理那些大小需要大于 N 的罕见情况。现在我们使用它的次数甚至超过 std::vector（但这只是因为我们的用例偏爱一堆极小的、临时的、连续的、随机访问的容器）。让它变快归结为只删除 operator[].
常见 Case/Rare 大小写倾斜
经过多年的分析和优化后学到的一件事是，没有 "absolutely-fast-everywhere" 代码这样的东西。很多优化行为是用那里的低效率换取这里的更高效率。用户可能会认为您的代码处处绝对快速，但这是来自智能权衡，其中优化与常见情况保持一致（常见情况既符合实际的用户端场景又符合实际情况）来自测量这些常见场景的分析器指出的热点）。
当您将性能偏向常见情况而远离罕见情况时，往往会发生好事。为了使常见情况变得更快，罕见情况通常必须变得更慢，但这是一件好事。
零成本异常处理
常见 case/rare 大小写倾斜的一个例子是许多现代编译器中使用的异常处理技术。他们应用零成本 EH，这并不是真正的 "zero-cost" 全面。在抛出异常的情况下，它们现在比以往任何时候都慢。然而，在没有抛出异常的情况下，它们现在比以往任何时候都更快，而且在成功的场景中通常比这样的代码更快：
if (!try_something())
return error;
if (!try_something_else())
return error;
...
当我们在这里使用零成本 EH 并避免手动检查和传播错误时，在非异常情况下，事情往往比上面这种代码风格更快。粗略地说，这是由于分支减少。然而，作为交换，抛出异常时必须发生更昂贵的事情。然而，常见案例和罕见案例之间的偏差往往有助于现实世界的场景。我们不太关心加载文件失败（罕见情况）的速度，而是成功加载文件（常见情况）的速度，这就是为什么许多现代 C++ 编译器实现 "zero-cost" EH 的原因。这又是为了歪曲常见情况和罕见情况，使它们在性能方面相距更远。
虚拟调度和同质化
面向对象代码中的大量分支，其中依赖项流向抽象（例如，stable 抽象原则），可以有大量的分支（当然除了循环，循环很好到分支预测器）以动态调度（虚函数调用或函数指针调用）的形式。
在这些情况下，一个常见的诱惑是将所有类型的子类型聚合到一个存储基指针的多态容器中，遍历它并在该容器中的每个元素上调用虚拟方法。这可能会导致很多分支预测错误，尤其是当这个容器一直在更新的时候。伪代码可能如下所示：
for each entity in world:
entity.do_something() // virtual call
避免这种情况的策略是开始根据其子类型对该多态容器进行排序。这是游戏行业中流行的一种相当老式的优化。我不知道它今天有多大帮助，但它是一种高级优化。
即使在最近的案例中，我发现另一种绝对有用的方法也能达到类似的效果，那就是将多态容器分解为每个子类型的多个容器，导致代码如下：
for each human in world.humans():
human.do_something()
for each orc in world.orcs():
orc.do_something()
for each creature in world.creatures():
creature.do_something()
...自然这就妨碍了代码的可维护性，降低了可扩展性。但是，您不必为这个世界上的每个子类型都这样做。我们只需要做最常见的。例如，这个想象中的视频游戏可能到目前为止由人类和兽人组成。它也可能有仙女、妖精、巨魔、精灵、侏儒等，但它们可能不像人类和兽人那么普遍。所以我们只需要将人类和兽人分开即可。如果您负担得起，您还可以拥有一个多态容器来存储所有这些子类型，我们可以将其用于对性能要求较低的循环。这有点类似于 hot/cold 用于优化参考位置的拆分。
面向数据的优化
优化分支预测和优化内存布局往往有点模糊。我很少尝试特别是 分支预测器的优化，那是在我用尽所有其他方法之后。然而，我发现非常关注内存和参考位置确实使我的测量导致更少的分支预测错误（通常不知道确切原因）。
这里可以帮助学习面向数据的设计。我发现一些与优化相关的最有用的知识来自于在面向数据的设计环境中研究内存优化。面向数据的设计倾向于强调更少的抽象（如果有的话），以及处理大块数据的更庞大的高级接口。从本质上讲，此类设计倾向于减少代码中不同分支和跳转的数量，并使用更多循环代码处理大块同类数据。
即使您的目标是减少分支预测错误，也可以更专注于更快地使用数据，这通常会有所帮助。例如，我之前从无分支 SIMD 中发现了一些巨大的收获，但是我的心态仍然是更快地消耗数据（它确实做到了，并且感谢像 Harold 这样的 SO 的一些帮助）。
TL;DR
所以无论如何，这些是一些策略，可以从高层的角度减少整个代码中的分支预测错误。他们在计算机体系结构方面缺乏最高水平的专业知识，但我希望鉴于所问问题的级别，这是一种适当的有用回答。很多这样的建议在一般情况下都与优化有些模糊，但我发现分支预测的优化通常需要与超越它的优化（内存、并行化、矢量化、算法）相混淆。无论如何，最安全的做法是在你深入探索之前确保你手上有一个剖面仪。
无分支并不总是更好，即使分支的两边都很微不足道。 When branch prediction works, it's faster than a loop-carried data dependency.
请参阅 gcc -O3 将 if() 转换为无分支代码的情况，因为它非常可预测，因此速度较慢。
有时您确信条件是不可预测的（例如在排序算法或二进制搜索中）。或者你更关心最坏情况不慢 10 倍，而不是快速情况快 1.5 倍。
一些习语更有可能编译成无分支形式（如 cmov x86 条件移动指令）。
x = x>limit ? limit : x; // likely to compile branchless
if (x>limit) x=limit; // less likely to compile branchless, but still can
第一种方式总是写入 x，而第二种方式不修改其中一个分支中的 x。这似乎是某些编译器倾向于为 if 版本发出分支而不是 cmov 的原因。即使 x 是一个已经存在于寄存器中的局部 int 变量，这也适用，因此 "writing" 它不涉及存储到内存，只是更改寄存器中的值。
编译器仍然可以为所欲为，但我发现这种习惯用法的差异会产生影响。根据您正在测试的内容，
TODO：关于 http://gcc.godbolt.org/
的示例为了回答您的问题，让我解释一下分支预测是如何工作的。
首先，当处理器正确预测采取的分支时，会有分支惩罚。如果处理器预测一个分支被采用，那么它必须知道预测分支的目标，因为执行流将从该地址继续。假设分支目标地址已经存储在分支目标缓冲区（BTB）中，它必须从 BTB 中找到的地址获取新指令。所以即使正确预测了分支，你仍然在浪费几个时钟周期。
由于 BTB 具有关联缓存结构，目标地址可能不存在，因此可能会浪费更多时钟周期。
另一方面，如果 CPU 预测一个分支没有被采纳，并且如果它是正确的，那么就没有惩罚，因为 CPU 已经知道连续的指令在哪里。
正如我上面所解释的，预测未采用的分支比预测采用的分支具有更高的吞吐量。
Is it possible to avoid branch misprediction using some high level programming technique (i.e. no assembly)?
是的，这是可能的。您可以通过组织代码的方式避免所有分支都具有重复的分支模式，例如总是采用或不采用。
但是如果你想获得更高的吞吐量，你应该按照我上面解释的最有可能不被采用的方式组织分支。
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++)?
如果可能的话尽量去掉分支。如果在编写 if-else 或 switch 语句时不是这种情况，请首先检查最常见的情况，以确保最有可能不采用的分支。尝试使用 __builtin_expect(condition, 1) 函数强制编译器生成条件，将其视为未采用。