分支感知编程

我正在阅读有关分支错误预测可能是应用程序性能的热门瓶颈的文章。正如我所看到的，人们经常展示汇编代码，这些代码揭示了问题，并声明程序员通常可以在大多数情况下预测分支的去向，并避免分支的错误预测。

我的问题是:

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

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

人们经常…并且声明程序员通常可以预测分支的位置

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

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

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

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

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

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

但是当一些分析器(valgrind, VTune，…)告诉我在foo.cpp的第n行上我得到了分支预测惩罚时，我该怎么办?

Lundin给出了非常明智的建议

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

2的顺序。和3。可能会被调换。手工优化代码需要大量的工作。另一方面，收集分析数据对于某些程序来说也很困难。

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

作为一个警告，我不是一个微优化向导。我不知道硬件分支预测器是如何工作的。对我来说，它是一个神奇的野兽，我和它玩剪刀-纸-石头游戏，它似乎能读懂我的心思，一直打败我。我是一个设计师。建筑类型。

然而，由于这个问题是关于高层次的心态，我也许可以提供一些建议。

分析

如我所说，我不是一个计算机架构向导，但我确实知道如何使用VTune分析代码，并测量诸如分支错误预测和缓存丢失之类的事情，并且一直在性能关键领域中这样做。如果你不知道如何做这个(分析)，这是你应该研究的第一件事。大多数这些微观级别的热点最好是在事后用手边的分析器发现。

分支消除

关于如何提高分支的可预测性，很多人给出了一些很好的低级建议。在某些情况下，您甚至可以手动尝试帮助分支预测器，也可以优化静态分支预测(例如，首先编写if语句来检查常见情况)。这里有一篇关于细节的全面文章，来自英特尔:https://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts。然而，在基本的常见情况/罕见情况预测之外执行此操作非常困难，并且几乎总是最好将其保存在您测量之后的后续。对人类来说，准确地预测分支预测器的性质太难了。这比页面错误和缓存丢失等事情更难预测，即使是这些，在复杂的代码库中也几乎不可能完美地人工预测。
然而，有一种更简单、更高级的方法来减轻分支错误预测，那就是完全避免分支。
跳过小/稀有作品
在我的职业生涯早期，我经常犯的一个错误是，看到很多同行在他们刚开始的时候，在他们还没有学会侧写和仍然凭直觉做事之前，试图跳过小的或罕见的工作。
这方面的一个例子是对一个大的查找表进行记忆，以避免重复做一些相对便宜的计算，比如使用一个跨越兆字节的查找表来避免重复调用cos和sin。对于人脑来说，这似乎节省了计算一次并存储它的工作量，除了经常从这个巨大的LUT中通过内存层次结构向下加载内存并将其加载到寄存器中，通常最终会比它们打算节省的计算量更昂贵。
另一种情况是添加一堆小分支，以避免在整个代码中进行不必要的小计算(不会影响正确性)，这是一种天真的优化尝试，结果发现分支的成本比进行不必要的计算要高。
这种对分支的天真尝试作为一种优化，甚至可以应用于稍微昂贵但很少的工作。以c++为例:

struct Foo { ... Foo& operator=(const Foo& other) { // Avoid unnecessary self-assignment. if (this != &other) { ... } return *this; } ... };
_{请注意，这是一个简单的/说明性的例子，因为大多数人实现复制赋值时使用的是对值传递的参数的复制-交换，无论如何都要避免分支}
在这种情况下，我们进行分支是为了避免自赋值。然而，如果自赋值只是做冗余的工作，并且不妨碍结果的正确性，那么允许自复制通常可以提高实际性能:

struct Foo { ... Foo& operator=(const Foo& other) { // Don't check for self-assignment. ... return *this; } ... };
…这是有帮助的，因为自我分配往往是相当罕见的。通过冗余的自分配，我们减慢了罕见情况的速度，但是通过避免检查所有其他情况，我们加快了常见情况的速度。当然，这不太可能显著减少分支的错误预测，因为在分支方面存在常见/罕见的情况偏差，但是，嘿，不存在的分支不可能被错误预测。
一个小向量的朴素尝试
就我个人而言，我曾经在一个大型的C代码库中工作过，那里经常有很多这样的代码:

char str[256]; // do stuff with 'str'
…当然，因为我们有一个相当广泛的用户基础，一些罕见的用户最终会在我们的软件中输入一个长度超过255个字符的材料的名称，并溢出缓冲区，导致分段故障。我们的团队开始使用c++，并开始将这些源文件移植到c++中，并将这些代码替换为:

std::string str = ...; // do stuff with 'str'
…这消除了那些缓冲区溢出，不费太多力气。然而，至少在当时，像std::string和std::vector这样的容器是堆(自由存储)分配的结构，我们发现自己为了效率而牺牲了正确性/安全性。其中一些被替换的区域是性能关键的(称为紧密循环)，当我们通过这些大规模替换消除了许多错误报告时，用户开始注意到速度变慢了。
所以我们想要一种介于这两种技术之间的东西。我们希望能够在那里添加一些东西，以实现比c风格的固定缓冲区变体更安全的功能(这在常见情况下非常好且非常有效)，但仍然适用于缓冲区不足以容纳用户输入的极少数情况。我是团队中性能极客之一，也是少数几个使用分析器的人之一(不幸的是，我和很多认为自己太聪明而不会使用分析器的人一起工作)，所以我被叫进了这个任务。
我的第一个天真的尝试是这样的(大大简化:实际的一个使用位置新等等，是一个完全符合标准的序列)。一般情况下使用固定大小的缓冲区(在编译时指定的大小)，如果大小超过该容量，则使用动态分配的缓冲区。

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; };
这次尝试彻底失败了。虽然它没有为构建堆/自由存储付出代价，但operator[]中的分支使其比std::string和std::vector<char>更糟糕，并且作为分析热点而不是malloc(我们的std::allocator和operator new的供应商实现在底层使用了malloc)。所以我很快就有了在构造函数中将ptr赋值给buf的想法。现在ptr即使在常见情况下也指向buf，现在operator[]可以这样实现:
T& operator[](int n) { return ptr[n]; }
…通过这个简单的分支消除，我们的热点消失了。我们现在有了一个通用的、符合标准的容器，它的速度和以前的c风格的固定缓冲区解决方案一样快(唯一的区别是在构造函数中多了一个指针和几个指令)，但可以处理那些需要大于N大小的罕见情况。现在我们甚至比std::vector更频繁地使用它(但这只是因为我们的用例更喜欢一堆小的、临时的、连续的、随机访问的容器)。而让它变得更快，归根结底就是在operator[]中消除一个分支。
常见/罕见歪斜
经过多年的分析和优化，我学到的一件事是，没有什么"在任何地方都绝对快速"的代码。很多优化行为都是用那里的低效率换取这里的更高效率。用户可能会认为您的代码在任何地方都是绝对快速的，但这来自于智能权衡，其中优化与常见情况保持一致(常见情况既与现实的用户端场景保持一致，又来自于测量这些常见场景的分析器指出的热点)。
当您将性能偏向于常见情况而远离罕见情况时，往往会发生好事情。为了让常见情况变得更快，通常罕见情况必须变得更慢，但这是一件好事。
零成本异常处理
常见/罕见情况倾斜的一个例子是在许多现代编译器中使用的异常处理技术。他们采用零成本EH，这并不是真正的"零成本"。在抛出异常的情况下，它们现在比以往任何时候都慢。然而，在没有抛出异常的情况下，它们现在比以往任何时候都快，并且在成功的场景中通常比以下代码更快:

if (!try_something()) return error; if (!try_something_else()) return error; ...
当我们在这里使用零成本EH并避免手动检查和传播错误时，在非异常情况下，事情往往比上面这种风格的代码更快。粗略地说，这是由于分支减少。然而，作为交换，当抛出异常时，必须发生代价高得多的事情。然而，常见情况和罕见情况之间的这种偏差往往有助于现实世界的情况。我们不太关心加载文件失败的速度(罕见情况)，因为加载成功(常见情况)，这就是为什么许多现代c++编译器实现了"零成本"EH。这也是为了区分常见情况和罕见情况，使它们在性能方面相差更远。
虚拟调度和同质性
许多面向对象代码中的分支，其中依赖关系流向抽象(例如稳定抽象原则)，可以以动态分派(虚拟函数调用或函数指针调用)的形式拥有大量分支(当然除了循环，它很好地发挥了分支预测器的作用)。
在这些情况下，一个常见的诱惑是将所有类型的子类型聚合到一个存储基指针的多态容器中，循环遍历该容器并对该容器中的每个元素调用虚方法。这可能导致很多分支预测错误，特别是如果这个容器一直在更新的话。伪代码可能像这样:
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()
…这自然会阻碍代码的可维护性并降低可扩展性。但是，您不必对这个世界中的每个子类型都这样做。我们只需要处理最常见的情况。例如，这个假想的电子游戏可能由人类和半兽人组成。它也可能有仙女、地精、巨魔、精灵、侏儒等，但它们可能不像人类和半兽人那样常见。所以我们只需要把人类和半兽人分开。如果你能负担得起，你还可以拥有一个多态容器来存储所有这些子类型，我们可以将其用于性能不那么关键的循环。这有点类似于优化引用位置的热/冷分割。
面向数据优化
优化分支预测和优化内存布局往往会混淆在一起。我很少尝试优化，特别是针对分支预测器的，而且只有在我用尽了所有其他方法之后。然而，我发现大量关注内存和引用的局部性确实使我的测量结果减少了分支错误预测(通常不知道确切原因)。
在这里，它可以帮助学习面向数据的设计。我发现与优化相关的一些最有用的知识来自于研究面向数据设计背景下的内存优化。面向数据的设计倾向于强调更少的抽象(如果有的话)，以及处理大块数据的更大的高级接口。从本质上讲，这样的设计倾向于减少代码中不同分支和跳跃的数量，用更多的循环代码处理大块同构数据。
即使你的目标是减少分支错误预测，把更多的精力放在更快地消费数据上也会有所帮助。例如，我以前从无分支SIMD中发现了一些巨大的收益，但心态仍然是更快地消费数据(它确实做到了，并且感谢来自这里的一些帮助，如Harold)。
TL;博士
无论如何，从高层次的角度来看，这些都是潜在地减少代码中分支错误预测的一些策略。他们在计算机体系结构方面缺乏最高水平的专业知识，但我希望这是一个适当的有益的回答，考虑到被问到的问题的水平。一般来说，这些建议都是模糊的优化，但我发现，对于分支预测的优化通常需要与超出它的优化(内存、并行化、向量化、算法)相模糊。在任何情况下，最安全的做法是确保在深入研究之前手头有一个剖析器。

Linux内核基于__builtin_expectgcc内置定义likely和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)) {
/* ... */
}

一般来说，保持热内循环与最常见的缓存大小成比例是一个好主意。也就是说，如果您的程序每次处理的数据块小于32kb，并且对其进行了相当多的处理，那么您可以很好地利用L1缓存。

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

这很重要，因为cpu首先具有分支预测的部分原因是能够预取下一条指令的操作数。通过安排代码，无论采取什么分支，下一个数据都很有可能来自L1缓存，可以减少分支错误预测的性能后果。虽然不是一个完美的策略，但L1缓存大小似乎普遍停留在32或64K;这几乎是整个行业的常态。不可否认，以这种方式编码通常不是直截了当地的，而依赖于其他人推荐的配置文件驱动优化等可能是最直接的方法。

无论如何，是否会发生分支错误预测的问题取决于CPU的缓存大小，机器上运行的其他内容，主内存带宽/延迟等。

也许最常见的技术是对正常和错误返回使用单独的方法。C没有选择，但c++有例外。编译器知道异常分支是异常的，因此是不可预期的。

这意味着异常分支确实很慢，因为它们是不可预测的，但是非错误分支更快。平均来说，这是一个净赢。

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

避免?也许不是。减少?当然…

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

值得注意的是，对一台机器的优化不一定是对另一台机器的优化。考虑到这一点，基于您提供的任何测试输入，配置文件引导的优化在重新安排分支方面相当出色。这意味着您不需要进行任何编程来执行此优化，并且它应该相对地针对您正在分析的机器进行定制。显然，当您的测试输入和您所配置的机器大致符合通常的期望时，将获得最佳结果……但这些也是任何其他优化，分支预测相关或其他方面的考虑因素。

为了回答你的问题，让我解释一下分支预测是如何工作的。

首先，当处理器正确地预测所采取的分支时，存在分支惩罚。．如果处理器预测一个分支已被占用，那么它必须知道预测分支的目标，因为执行流将从该地址继续。假设分支目标地址已经存储在分支目标缓冲区(BTB)中，它必须从BTB中找到的地址获取新指令。因此，即使正确预测了分支，您仍然会浪费几个时钟周期。
由于BTB具有关联缓存结构，因此目标地址可能不存在，因此可能会浪费更多的时钟周期。

另一方面，如果CPU预测一个分支没有被占用，如果它是正确的，那么就没有惩罚，因为CPU已经知道连续指令的位置。

如上所述，预测未被占用的分支比预测被占用的分支具有更高的吞吐量.

是否有可能使用一些高级编程技术(即没有汇编)来避免分支错误预测?

是的，有可能。您可以通过组织代码的方式，使所有分支都具有重复的分支模式，例如总是采取或不采取。
但是如果你想获得更高的吞吐量，你应该按照我上面解释的那样，以一种最可能不被占用的方式组织分支。

我应该记住什么才能在高编程环境中生成分支友好的代码高级编程语言(我最感兴趣的是C和c++)?

如果可能，尽可能消除分支。如果在编写If -else或switch语句时不是这种情况，则首先检查最常见的情况，以确保最有可能不占用分支。尝试使用__builtin_expect(condition, 1)函数强制编译器产生未被采用的条件

无分支并不总是更好，即使分支的两边都是微不足道的。当分支预测工作时，它比循环携带的数据依赖要快。

参见gcc优化标志-O3使代码比-O2慢，在gcc -O3将if()转换为无分支代码的情况下，在非常可预测的情况下，使其变慢。

有时你确信一个条件是不可预测的(例如在排序算法或二分搜索中)。或者你更关心最坏情况不是慢10倍，而不是快1.5倍。

一些习惯用法更有可能编译成无分支的形式(如cmovx86的条件移动指令)。

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变量，这也适用，所以"写"它不涉及存储到内存，只是改变寄存器中的值。

编译器仍然可以做他们想做的任何事情，但是我发现这种习惯用法的不同可以产生不同。根据您测试的内容，有时帮助编译器掩码和and比使用普通的旧cmov更好。我之所以这么做，是因为我知道编译器可以用一条指令生成掩码(并且可以看到clang是如何完成的)。

TODO:示例:http://gcc.godbolt.org/

相关内容

最新更新

热门标签：