分支感知编程
我正在阅读这个分支，错误预测可能是应用程序性能的一个热点瓶颈。 正如我所看到的，人们通常会显示汇编代码，揭示了这个问题，并指出程序员通常可以预测分支可以走多远的时间，避免分支错误预测。
我的问题是：
1-是否可以避免使用一些高级编程技术（即没有汇编 ）的分支预测错误？
2-我应该记住用高级编程语言（我主要对C和C ++感兴趣）生成支持分支的代码？
代码示例和基准值得欢迎！
人们经常……并指出程序员通常可以预测分支可以去的地方
（*）有经验的程序员经常提醒说，人类程序员在预测这个方面非常糟糕。
1-是否可以避免使用一些高级编程技术（即没有汇编）的分支预测错误？
不是标准的c ++或c。 至less不是一个分支。 你可以做的是最大限度地减less你的依赖链的深度，这样分支预测就不会有任何影响。 现代cpus将执行分支的两个代码path，并删除未被select的代码path。 然而，这是有限的，这就是为什么分支预测只在深度依赖链中起作用的原因。
一些编译器提供了用于手动build议预测的扩展，例如gcc中的__builtin_expect 。 这是关于它的一个stackoverflow问题 。 更好的是，一些编译器（如gcc）支持分析代码并自动检测最佳预测。 由于（*），使用分析而不是手动工作是聪明的。
2-我应该记住用高级编程语言（我主要对C和C ++感兴趣）生成支持分支的代码？
首先，你应该记住，分支的错误预测只会影响你的程序中最关键的部分，而不是担心它，直到你测量和发现问题。
但是当一些剖析器（valgrind，VTune，…）告诉我在foo.cpp的第n行我得到了一个分支预测惩罚时，我该怎么办？
伦丁给了非常明智的build议
- 测量一下是否重要。
- 如果它很重要的话
- 最大限度地减less计算依赖链的深度。 如何做到这一点可能相当复杂，超出了我的专业知识，没有深入集会就没有太多的事情可做。 你可以用高级语言做的事情是尽量减less条件检查（**）的数量。 否则，你是在编译器优化的摆布。 避免深度依赖链也允许更有效地使用乱序超标量处理器。
- 让您的分支始终可预测。 这个效果可以在这个stackoverflow问题中看到。 在这个问题中，有一个数组上的循环。 循环包含一个分支。 分支取决于当前元素的大小。 当对数据进行sorting时，用特定的编译器编译并在特定的cpu上运行时，循环会显示得更快。 当然，保持所有数据的sorting也会花费CPU时间，可能比分支错误的预测还要多，所以测量 。
- 如果问题仍然存在，请使用简介指导优化 （如果可用）。
2.和3.的顺序可以切换。 手动优化你的代码是很多工作。 另一方面，收集分析数据对于某些程序也是困难的。
（**）一种方法是通过例如展开它们来转换你的循环。 您也可以让优化器自动执行。 尽pipe如此，你必须进行测量，因为展开会影响你与caching进行交互的方式，最终会变成一个悲观的东西。
Linux内核基于__builtin_expect gcc builtins定义了likely和unlikelymacros：
#define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0)
（ 在这里查看include/linux/compiler.h的macros定义）
你可以像这样使用它们：
if (likely(a > 42)) { /* ... */ }
要么
if (unlikely(ret_value < 0)) { /* ... */ }
也许最常用的技术是使用单独的方法来返回正常和错误。 C没有select，但是C ++有例外。 编译器意识到exception分支是例外的，因此是意想不到的。
这意味着exception分支确实很慢，因为它们是不可预测的，但是非错误分支速度更快。 平均而言，这是一场净胜。
作为一个警告，我不是一个微型优化向导。 我不知道硬件分支预测器是如何工作的。 对我来说，这是一个魔术般的野兽，我用剪刀纸石头，似乎能够读懂我的思想，并一直打我。 我是一个devise和build筑types。
不过，由于这个问题是关于高层次的思维方式，所以我可能会提出一些build议。
剖析
如上所述，我不是计算机体系结构向导，但我知道如何使用VTune分析代码，并测量分支预测失误和caching未命中等情况，并始终在性能关键字段中执行此操作。 如果你不知道如何做（分析），这是你应该首先考虑的事情。 大多数这些微观层次的热点最好是事后分析。
消除分支
很多人在提高分支机构的可预测性方面给出了一些很好的低级build议。 您甚至可以手动尝试在某些情况下帮助分支预测器，并优化静态分支预测（例如，编写if语句以检查常见情况，例如）。 有关英特尔的详细信息，请访问： https : //software.intel.com/zh-cn/articles/branch-and-loop-reorganization-to-prevent-mispredicts 。
但是，这样做超出了基本的常见情况/罕见情况下的预测，这是非常困难的事情，它几乎总是最好的保存以备后用 。 对于人类来说，要准确预测分支预测器的性质实在太难了。 要比页面错误和caching未命中等事情更难预测，甚至在复杂的代码库中，这些几乎不可能完全人为地预测。
但是，缓解分支预测失误有一个更简单，更高层次的方法，那就是避免完全分支。
跳过小/稀有的工作
我在职业生涯早些时候经常犯的一个错误，就是看到很多同龄人在他们刚开始学习之前试图去做的事情，而他们已经学会了简介，并且还在继续前行，那就是尝试跳过小的或者稀有的工作。
一个例子是记忆到一个大的查找表，以避免重复执行一些相对便宜的计算，例如使用跨越兆字节的查找表来避免重复调用cos和sin 。 对于人类的大脑来说，这似乎是节省了一次计算并存储它的工作，除了经常将这个巨大的LUT中的内存加载到内存层次结构中，并进入寄存器，通常会比计划的计算花费更多保存。
另一种情况是增加一些小分支来避免小计算，这些计算在整个代码中是无害的（不会影响正确性），作为一种天真的优化尝试，仅仅是为了发现分支成本，而不仅仅是做不必要的计算。
这种天真的分支作为一种优化的尝试也可以适用于即使是稍微昂贵但罕见的工作。 以这个C ++为例：
struct Foo { ... Foo& operator=(const Foo& other) { // Avoid unnecessary self-assignment. if (this != &other) { ... } return *this; } ... };
请注意，这是一个简单/说明性的例子，因为大多数人使用copy-and-swap对值传递的参数进行复制分配，无论如何都避免分支。
在这种情况下，我们正在分支以避免自我分配。 然而，如果自我分配只是做了多余的工作，并不妨碍结果的正确性，那么它往往会促使你在现实世界的performance中简单地进行自我复制：
struct Foo { ... Foo& operator=(const Foo& other) { // Don't check for self-assignment. ... return *this; } ... };
…这可以帮助，因为自我分配往往是相当罕见的。 我们正在通过冗余自我分配来减缓这种罕见的情况，但我们正在加快常见的情况，避免需要检查所有其他情况。 当然这不太可能减less分支预测误差，因为在分支方面存在一个常见/罕见的情况偏差，但是嘿，一个不存在的分支不能被误预测。
天真的尝试在一个小vector
作为一个个人的故事，我曾经在一个大规模的C代码库中工作，这个C代码库经常有很多这样的代码：
char str[256]; // do stuff with 'str'
…自然，由于我们有相当广泛的用户群，一些罕见的用户最终会在我们的软件中input长度超过255个字符的材料的名称，并溢出缓冲区，导致段错误。 我们的团队正在进入C ++，并开始将许多这些源文件移植到C ++中，并用以下代码replace这些代码：
std::string str = ...; // do stuff with 'str'
…消除了那些缓冲区溢出没有太多的努力。 然而，至less在那个时候，像std::string和std::vector这样的容器是堆（免费存储）分配的结构，我们发现自己正在交换正确性/安全性来提高效率。 其中一些被replace的区域对性能至关重要（称为紧缩循环），虽然我们通过这些大规模replace消除了大量的错误报告，但用户开始注意到速度减慢。
所以我们想要的东西就像是这两种技术的混合。 我们希望能够通过C语言的固定缓冲区变体来实现安全性（这对于常见情况来说是非常好的和非常高效的），但是仍然适用于缓冲区不太常见的情况对于用户input来说足够大。 我是团队中performance的极客之一，也是为数不多的使用探查器的人之一（我不幸与很多认为自己太聪明的人一起工作），所以我被召集到了这个任务中。
我第一次天真的尝试是这样的（大大简化：实际使用放置新等等，是一个完全符合标准的顺序）。 它涉及在常见情况下使用固定大小的缓冲区（在编译时指定大小），如果大小超过该容量，则使用dynamic分配的缓冲区。
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; };
这个尝试完全失败了。 虽然它没有支付构build堆/免费存储的价格，但operator[]的分支使得它比std::string和std::vector<char>更糟糕，并且显示为分析热点，而不是malloc （我们的供应商实现了std::allocator和operator new使用了malloc下的malloc ）。 所以我很快就明白了，只要在构造函数中将ptr指定给buf 。 现在，即使在常见情况下， ptr指向buf ，现在operator[]可以这样实现：
T& operator[](int n) { return ptr[n]; }
…而那个简单的分支消除，我们的热点就消失了。 我们现在有一个通用的，兼容标准的容器，我们可以使用这个容器，它的速度与以前的C型固定缓冲区解决scheme差不多，只是在构造函数中有一个额外的指针和一些指令。可以处理那些尺寸需要大于N罕见情况。 现在我们使用这个比std::vector更多（但仅仅是因为我们的用例支持一堆小的，临时的，连续的，随机访问的容器）。 快速的解决方法就是去掉operator[]一个分支。
常见案例/罕见案例倾斜
在多年的分析和优化之后学到的东西之一就是没有“绝对快速到处”的代码。 许多优化行为在这里效率低下，效率更高。 用户可能认为自己的代码是绝对快速的 ，但是这来自智能的权衡，优化与常见的情况保持一致（常见的情况是与实际的用户端场景相一致，并且来自于一个分析器指出的热点，常见场景）。
好的事情往往会发生，当你偏向普通情况下的performance，并远离罕见的情况。 对于一般情况下要加快速度的情况，往往这种less有的情况一定会变慢，但这是件好事。
零成本例外处理
常见情况/罕见情况下倾斜的一个例子是在许多现代编译器中使用的exception处理技术。 他们应用零成本的EH，这并不是真正的“零成本”。 在抛出exception的情况下，它们现在比以前更慢了。 然而，在不抛出exception的情况下，它们现在比以前更快了，而且在成功的情况下比这样的代码更快：
if (!try_something()) return error; if (!try_something_else()) return error; ...
当我们在这里使用零成本的EH而不是手动检查和传播错误时，在非例外的情况下，事情往往会比上面这种types的代码更快。 粗略地说，这是由于分支减less。 然而，作为交换，当抛出exception时，必须发生更为昂贵的事情。 然而，普通情况和罕见情况之间的偏差往往有助于现实情景。 我们不太关心加载文件失败的速度（罕见的情况），因为加载成功（常见的情况），这就是为什么很多现代C ++编译器实现“零成本”的EH。 这又是为了歪曲普通的情况和罕见的情况，把它们推向更远的地方。
虚拟调度和同质性
在依赖关系stream向抽象（比如稳定的抽象原则）的面向对象的代码中，大量的分支可以有大量的分支（当然，除了循环之外，这对分支预测器来说也很好）调度（虚函数调用或函数指针调用）。
在这些情况下，一种常见的诱惑是将所有types的子types聚合成一个存储基指针的多态容器，循环它并在该容器中的每个元素上调用虚拟方法。 这可能导致很多分支预测失误，特别是如果这个容器一直在更新。 伪代码可能看起来像这样：
for each entity in world: entity.do_something() // virtual call
避免这种情况的策略是开始基于子types对这个多态容器进行sorting。 这是一个相当古老的游戏行业stream行的优化。 我不知道今天有多大的帮助，但它是一种高级别的优化。
另一种方式，即使在最近发生的类似效果的情况下，我发现它仍然是有用的，就是将多态容器拆分成多个容器，每个容器的子types如下所示：
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()
自然这阻碍了代码的可维护性并降低了可扩展性。 但是，这个世界上的每个子types都不需要这样做。 我们只需要为最常见的做。 例如，这个虚构的video游戏可能由人类和兽人组成。 它也可能有精灵，地精，巨魔，精灵，侏儒等，但它们可能不像人类和兽人那么普遍。 所以我们只需要把人类和兽人分开。 如果你能负担得起，你也可以有一个多态的容器来存储所有这些子types，我们可以使用这些子types来减less性能关键的循环。 这有点类似于热/冷分裂，以优化参考的位置。
面向数据的优化
优化分支预测和优化内存布局趋于模糊在一起。 我只是很less尝试专门针对分支预测器的优化，只有在我耗尽其他所有东西之后。 然而，我发现把注意力集中在记忆和参考的地点上，这使得我的测量结果导致了更less的分支预测失误（通常不知道原因）。
在这里可以帮助学习面向数据的devise。 我发现一些与优化有关的最有用的知识来自于研究面向数据devise的内存优化。 面向数据的devise倾向于强调较less的抽象（如果有的话）以及处理大块数据的较大的高级接口。 就本质而言，这样的devise倾向于减less不同分支的数量，并且使用更多的代码处理大量的同类数据。
即使您的目标是减less分支机构的错误预测，但更多地关注更快地消费数据，这通常也是有帮助的。 例如，我从无分支SIMD中发现了一些很大的收获，但是这种思维方式仍然更加快速地消耗数据（这一点，并且要感谢像哈罗德这样的一些人的帮助）。
TL; DR
所以无论如何，这些都是一些策略，可以从高层次的angular度来减less整个代码中的分支预测失误。 他们缺乏计算机体系结构的最高水平的专业知识，但是我希望这是一个适当的有用的反应types，考虑到问题的水平。 很多这样的build议都是通过优化来模糊的，但是我发现对于分支预测的优化往往需要通过优化来模糊（内存，并行化，vector化，algorithm）。 无论如何，最安全的方法就是在深入探索之前，确保你手上有一个分析器。
一般来说，保持热内环与最常遇到的caching大小成正比是个好主意。 也就是说，如果您的程序一次处理的数据量小于32kbytes，并且在其上做了相当多的工作，那么您就可以很好地利用L1caching。
相比之下，如果热内部循环咀嚼100MByte的数据，并且每个数据项只执行一个操作，那么CPU将花费大部分时间从DRAM中获取数据。
这很重要，因为CPU首先具有分支预测的部分原因是能够为下一条指令预取操作数。 分支错误预测的性能结果可以通过安排代码来减less，这样无论采取什么分支，下一个数据都有可能来自L1caching。 虽然不是一个完美的策略，L1caching大小似乎普遍卡在32或64K; 这在整个行业中几乎是一个不变的事情。 以这种方式承认编码往往不是直截了当的，依靠其他人所推荐的简档驱动优化等可能是最直接的方法。
不pipe别的，分支错误预测的问题是否会根据CPU的高速caching大小，机器上还在运行什么，主内存带宽/等待时间等等而有所不同。
1-是否可以避免使用一些高级编程技术（即没有汇编）的分支预测错误？
避免？ 也许不是。 减less？ 当然…
2-我应该记住用高级编程语言（我主要对C和C ++感兴趣）生成支持分支的代码？
值得注意的是，一台机器的优化不一定是另一台机器的优化。 考虑到这一点， configuration文件引导优化在重新安排分支方面相当出色，基于您提供的任何testinginput。 这意味着您不需要执行任何编程来执行此优化，并且应该根据您所分析的任何一台机器进行相应的调整。 显然，当您的testinginput和您所用的机器大致符合常见的期望值时，最佳的结果将会实现…但是这些也是任何其他优化，分支预测相关或其他方面的考虑因素。
为了回答你的问题，让我解释一下分支预测是如何工作的。
首先，当处理器正确预测采取的分支时会有分支惩罚。 如果处理器预测分支被采用，则它必须知道预测分支的目标，因为执行stream将从该地址继续。 假设分支目标地址已存储在分支目标缓冲区（BTB）中，则必须从BTB中find的地址获取新的指令。 所以即使分支被正确预测，你仍然在浪费几个时钟周期。
由于BTB具有关联的caching结构，所以目标地址可能不存在，因此可能浪费更多的时钟周期。
另一方面，如果CPU预测分支未被采用，并且如果它是正确的，则不存在惩罚，因为CPU已经知道连续指令在哪里。
正如我上面所解释的那样， 预测不采取分支的吞吐量比预测采取的分支更高 。
是否有可能避免使用一些高级编程技术（即没有汇编）的分支预测失误？
对的，这是可能的。 你可以通过组织你的代码来避免所有分支都有重复的分支模式，使得总是被采用或不被采用。
但是如果你想获得更高的吞吐量，你应该按照上面解释的方式组织分支机构。
我应该记住用高级编程语言来生成支持分支的代码（我主要对C和C ++感兴趣）？
如果可能的话，消除分支。 如果在编写if-else或switch语句时不是这种情况，请首先检查最常见的情况，以确保最有可能不被占用的分支。 尝试使用_builtin_expect(condition, 1)函数强制编译器产生条件，视为未被采用。
即使分支的两边都是微不足道的，分支并不总是更好。 当分支预测工作时，它比循环执行的数据依赖性更快 。
有时候你确信一个条件是不可预知的（例如在一个sortingalgorithm或二进制search中）。 或者你更关心最坏的情况，而不是速度的10倍，快于1.5倍的速度。
一些成语更可能编译成无cmovforms（如cmov x86条件移动指令）。
x = x>limit : limit : x; // likely to compile branchless if (x>limit) x=limit; // less likely to compile branchless
第一种方式总是写入x ，而第二种方式不会修改其中一个分支中的x 。 这似乎是一些编译器倾向于为if版本发出分支而不是cmov的原因。 即使当x是已经存在于寄存器中的本地intvariables时，这也适用，所以“写入”它不涉及存储器到存储器，只是改变寄存器中的值。
编译器仍然可以做任何他们想做的事情，但是我发现这个习语的不同可以有所作为。 根据你testing的结果， 偶尔会更好地帮助编译器掩码和AND，而不是做一个普通的旧的cmov 。 我是这么回答的，因为我知道编译器只需要用一条指令来生成掩码就可以了（看看clang是怎么做的）。
TODO： http ://gcc.godbolt.org/上的例子
