分支感知编程

Question

分支感知编程

c++cperformanceoptimizationbranch-prediction

43

我发现分支预测错误可能会成为应用程序性能的热点瓶颈。人们通常展示揭示问题的汇编代码，并指出程序员通常可以预测分支走向大部分时间，从而避免分支预测错误。

我的问题是：

是否有一些高级编程技术（即无需汇编）可以避免分支预测错误？
在高级编程语言中编写友好于分支的代码时应注意什么（我主要关注C和C++）？

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

- Paolo M

2

相关：为什么处理排序数组比未排序数组更快？。请查看目前得票最高的答案。 - iammilind

2

由于分支预测只发生在机器级别，因此在高级编程语言级别要求它并没有太多意义。编译器通常包含特定于供应商的机制来注释条件与预期结果，但仍然由编译器生成其认为最佳的机器代码（这可能会被配置文件引导的优化或空间限制修改）。最终，如果您关心机器的细节，您需要了解机器，同时需要了解您的分析工具。 - Kerrek SB

11

你应该相信你的优化编译器。GCC 提供了 __builtin_expect。 - Basile Starynkevitch

1

保持列表排序可以帮助，因为这将允许像“if（x <10）”这样的代码更长时间地保持在一条路径上。 - rhughes

4

保持“大局观”非常重要。首先，对代码进行分析并找出哪些部分值得优化 。我曾经处理过的一个极端真实世界的例子是一个25万行的程序，其中超过90%的计算是在一个只有3行代码的循环中完成的。无法消除该循环中执行的工作量。在程序的其余部分进行任何优化都将完全浪费精力。 - alephzero

显示剩余12条评论

8个回答

22

作为警示，我并不是微优化领域的专家。我并不知道硬件分支预测器的工作原理。对我而言，它是一个神秘的存在，我与之下了剪刀石头布游戏，它似乎能读懂我的心思并一直战胜我。我更多的是关注设计和架构方面。

尽管如此，既然这个问题涉及到高层次的思考方式，我或许能提供一些建议。 性能分析 正如上面所说，我不是计算机架构领域的专家，但我知道如何使用VTune分析代码，并测量像分支误判和缓存失效等指标。在这样的性能关键领域，这应该是你需要掌握的第一步，如果你还不知道如何进行性能分析（profiling）的话。大部分这些微观热点都是最好通过分析工具事后才能发现的。 减少分支预测错误 很多人都提出了一些关于如何改进分支预测准确性的低级别建议。有时候，你甚至可以手动帮助分支预测器来优化静态分支预测（例如写if语句来首先检查常见情况）。Intel在这里提供了一篇详细的文章，介绍了所有微观细节：https://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts。

然而，除了基本的常见情况和罕见情况的预判之外，更深层次的优化是很难做到的。通常最好等到你对代码进行分析后再进行优化。对于人类来说，准确地预测分支预测器的行为是非常困难的。这比像缺页和缓存失效等事情还要困难得多，即使在复杂的代码库中，这些事情也几乎无法完美地通过人工预测。

不过，还有一种更简单高效的方式来减少分支误判的问题，那就是避免分支。 跳过小型或罕见的任务 我在职业生涯早期经常犯的一个错误，也看到很多同行在刚开始时会尝试跳过小型或罕见的任务，这是在他们还没有学会性能分析并仍然依赖直觉的时候。例如，使用一个跨越几兆字节的大型查找表来避免多次调用cos和sin等相对较小的计算。人类的思维认为，这样做可以避免重复计算，但实际上从这个庞大的查找表中加载内存，经过内存层次结构，再到寄存器中，往往比原本要执行的计算更加昂贵。

另一种情况是添加许多小分支，以避免在代码中进行无害但不必要的小型计算（不会影响正确性）作为天真的优化尝试，但最终发现分支的成本比仅执行不必要的计算更高。这种“分支作为优化”的天真尝试甚至也适用于稍微昂贵但不常见的工作。以此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 风格固定缓冲区变量的安全性（这对于常见情况非常好且非常高效），但仍然适用于罕见情况，即缓冲区不足以容纳用户输入。我是团队中的性能极客之一，也是少数使用分析器的人之一（不幸的是，我与很多认为自己太聪明而不需要使用分析器的人一起工作），所以我被召唤来完成这项任务。

我的第一个天真尝试是这样的（大大简化了：实际使用了放置 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;
};

这次尝试彻底失败了。虽然构造过程中没有付出堆/自由存储器的代价，但在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[]中的一个分支。

常见情况/罕见情况偏离

经过多年的性能分析和优化，我们发现没有所谓的“无处不快”的代码。优化的过程就是在不同地方进行效率的权衡。用户可能认为你的代码在任何情况下都很快，但这来自于明智的权衡，其中优化与常见情况相匹配（常见情况既与真实的用户场景相匹配，又来自于性能分析工具测量的热点场景）。

当你将性能偏向常见情况并远离罕见情况时，好的事情就会发生。为了让常见情况变得更快，通常罕见情况必须变得更慢，但这是一件好事。

零成本异常处理

现代编译器中使用的异常处理技术就是一个常见情况/罕见情况偏离的例子。它们应用了零成本异常处理，但在抛出异常的情况下，它们比以往任何时候都要慢。然而，在没有抛出异常的情况下，它们比以前更快，并且通常比像这样的代码在成功的情况下更快：

if (!try_something())
    return error;
if (!try_something_else())
    return error;
...

当我们使用零成本异常处理并避免手动检查和传播错误时，非异常情况下的执行速度往往比上述代码更快。粗略地说，这是由于分支减少所致。然而，作为交换，当抛出异常时需要发生更昂贵的操作。尽管如此，普通情况和罕见情况之间的偏差往往有助于实际场景。我们不太关心加载文件失败（罕见情况）的速度，而是关心成功加载它（常见情况）的速度，这就是为什么许多现代C++编译器实现“零成本”异常处理的原因。这再次符合将常见情况和罕见情况推向性能方面的偏差。

虚拟分派和同质性

在面向对象的代码中，如果依赖关系流向抽象（如稳定的抽象原则），则分支很多，除了循环（当然，循环对分支预测器有很好的效果）外，其大部分分支形式为动态分派（虚函数调用或函数指针调用）。

在这些情况下，一种常见的诱惑是将各种子类型聚合到一个存储基础指针的多态容器中，循环遍历它并在该容器中的每个元素上调用虚方法。这可能会导致许多分支预测失败，特别是如果该容器一直在更新。伪代码可能如下所示：

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等在SO上的帮助而成功）。

总之，这些都是从高层次的角度可能减少您代码中分支错误预测的策略。虽然缺乏计算机体系结构的最高级别的专业知识，但我希望这是一种适当的有用的答复，考虑到所提出问题的水平。许多这些建议与优化有些混淆，但我发现为分支预测进行优化通常需要与其它优化（内存、并行化、向量化、算法）混淆。在任何情况下，在深入探索之前，请确保手中有性能分析器。

- user4842163

听到人们仍然实现自己的小向量而不使用Boost中的向量，这真是令人沮丧。但也许这是在Boost实现该功能之前的事情。 - olq_plo

18

Linux内核基于gcc内置的__builtin_expect宏定义了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)) {
    /* ... */
}

- ouah

不知道内核也定义宏 :) - BitTickler

7

通常来说，将热门内部循环与最常遇到的缓存大小保持良好比例是一个不错的想法。也就是说，如果你的程序一次处理少于32k字节的数据块并且对其进行了相当数量的处理，那么你正在充分利用L1缓存。

相反的，如果你的热门内部循环要处理100MB的数据，并且每个数据项只执行一项操作，那么CPU将花费大部分时间从DRAM中获取数据。

这很重要，因为CPU之所以首先具有分支预测能力，是为了能够预取下一条指令的操作数。分支误判的性能后果可以通过排列代码，使无论采取哪种分支，下一个数据都有很大概率来自L1缓存而减少。虽然这不是一个完美的策略，但L1缓存大小似乎普遍固定在32或64K；这在整个行业中几乎都是一个常数。尽管这种编码方式通常不那么直观，但依靠推荐的基于剖面的优化等等可能是最直接的方法。

除此之外，分支误判的问题是否会发生取决于CPU的缓存大小、机器上运行的其他内容、主存带宽/延迟等，这是无可避免的。

- bazza

7

也许最常见的技术是使用不同的方法来处理正常返回和错误返回。C语言没有选择，但C++有异常处理。编译器知道异常分支是异常的，因此是意外的。这意味着异常分支的确很慢，因为它们是不可预测的，但是非错误分支会更快。平均而言，这是一个净胜利。

- MSalters

如果错误有任何非可忽略的发生几率，那么这个建议是完全错误的：发生异常的性能代价是巨大的。如果您关心性能，请不要在程序流程中引入异常。 - cmaster - reinstate monica

@cmaster：即使异常发生的可能性不可忽视，并且你关心非异常情况下的性能，但在异常情况下你通常并不关心性能。例如：编译代码。编译错误肯定会发生，大型项目的构建时间确实是一个问题。但异常的开销与人类查看错误所花费的时间相比微不足道。 - MSalters

@cmaster：这里的重点是（因为它涉及分支感知编程），异常可以节省大约(1-exceptionChance)*overheadOfErrorHandlingInNormalCase的时间。如果你每秒钟调用一个函数一千次，并且有一个错误返回值，那么必须每秒钟检查一千次。如果该错误是异常，编译器可以优化无错误的情况。如果错误被编码为负整数，则编译器没有这种指导。 - MSalters

@cmaster：苹果和橙子。最终，它关乎流程控制，在你捕获异常的那一点上，你已经过了流程的分支点（并且你在慢分支上）。仅仅检查错误代码还不是一个流程控制操作，而分支才是昂贵的。（特别是这种类型的分支会污染分支预测缓存——异常通常不依赖于预测分支，因为编译器可以使用假定不采取分支的分支。例如，x86指令0x2E）。 - MSalters

刚刚进行了一个简单的基准测试：在我的系统上，将异常抛出到单个函数级别比从函数中返回错误代码昂贵了483倍... - cmaster - reinstate monica

显示剩余3条评论

2

1- 有没有可能使用一些高级编程技术（即不使用汇编）来避免分支预测错误？

避免？也许不行。减少？当然可以...

2- 我应该注意什么才能在高级编程语言中编写出友好于分支的代码（我主要关注C和C++）？

值得注意的是，为一台机器进行优化并不一定适用于另一台机器。考虑到这一点，基于您提供的任何测试输入，基于剖面的优化可以很好地重新排列分支。这意味着您不需要进行任何编程即可执行此优化，并且它应该相对适合您正在剖析的任何机器。显然，当您的测试输入和您剖析的机器大致符合常见期望时，将实现最佳结果...但这些也是任何其他优化（包括与分支预测相关的优化）的考虑因素。

- autistic

2

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

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

另一方面，如果CPU将一个分支预测为不采取，而且这是正确的话，那么就没有惩罚，因为CPU已经知道连续指令的位置。

正如我上面所解释的，预测不采取分支比预测采取分支具有更高的吞吐量。

“是否可以使用某些高级编程技术（即无汇编语言）避免分支错误预测？”

是的，是有可能的。你可以通过以所有分支都具有重复的分支模式的方式组织你的代码来避免。如果你想获得更高的吞吐量，你应该按照我上面所解释的方式组织分支，使它们最有可能不被采取。

“我在高级编程语言中（我主要关心C和C++）如何编写分支友好的代码？”

如果可能，尽可能消除分支。如果这不是情况，在编写if-else或switch语句时，首先检查最常见的情况，以确保最有可能不采取分支。尝试使用内置函数 __builtin_expect(condition, 1) 来强制编译器将条件视为未采取。

- Görkem Mülayim

1

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

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

有时，您有信心某个条件是不可预测的（例如，在排序算法或二分搜索中）。或者，您更关心最坏情况不会比快速情况慢10倍，而不是快速情况比最坏情况快1.5倍。

一些习语更可能编译成无分支形式（例如x86条件移动指令cmov）。

x = x>limit ? limit : x;   // likely to compile branchless

if (x>limit) x=limit;      // less likely to compile branchless, but still can

第一种方法总是写入x，而第二种方法不在其中一个分支中修改x。这似乎是一些编译器倾向于发出分支而不是cmov的原因。即使x是一个本地的int变量，在寄存器中已经存在，所以“写入”它不涉及对内存的存储，只需更改寄存器中的值。

编译器仍然可以随意操作，但我发现这种习惯上的差异可能会产生影响。根据你正在测试的内容，有时使用掩码和AND帮助编译器可能比执行普通的cmov好。我在那个答案中这样做是因为我知道编译器将使用单个指令生成所需的掩码（并从clang如何执行此操作中看到）。

待办事项：http://gcc.godbolt.org/上的示例。

- Peter Cordes

在代码示例中，第一行的第一个“:”应该是一个“?”。 - hexcoder

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- eerorika · Accepted Answer

人们经常认为程序员通常可以预测一个分支会走向何方。

(*) 经验丰富的程序员经常提醒人们，人类程序员非常擅长这个。

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

在标准的 C++ 或 C 中不行。至少对于单个分支而言是不行的。你可以尽量减小依赖链的深度，使分支错误预测不会产生任何影响。现代 CPU 会执行分支的两条路径并丢弃未被选择的那个。然而，这也有其限制，这就是为什么分支预测只在深层次的依赖链中起作用。

一些编译器提供了扩展功能，可以手动建议预测，例如 gcc 中的 __builtin_expect。这里有一个关于此的 stackoverflow question。更好的是，一些编译器（如 gcc）支持对代码进行分析，并自动检测最优预测。由于 (*) 的原因，使用分析比手动工作更为智能。

2- 我如何在使用高级编程语言（主要是 C 和 C++）编写分支友好的代码时需要注意什么？

首先，你应该记住，分支预测只会影响程序中最性能关键的部分，并且不要担心它，直到你已经测量并发现了问题。

但是当一些分析工具（如 valgrind、VTune 等）告诉我在 foo.cpp 的第 n 行存在分支预测惩罚时，我该怎么办呢？

Lundin 给出了非常明智的建议。

衡量是否重要。
如果它很重要，那么：
- 最小化计算的依赖链深度。如何做到这一点可能非常复杂，超出了我的专业知识，除非深入研究汇编语言，否则你无法做太多事情。在高级语言中，你可以做的是尽量减少条件检查的数量（**）。否则，你就要看编译器优化的眼色了。避免深层次的依赖链也可以更有效地使用乱序超标量处理器。
- 使你的分支始终可预测。这种影响可以在stackoverflow问题中看到。在这个问题中，有一个数组的循环。循环包含一个分支。该分支取决于当前元素的大小。当数据排序时，可以证明使用特定编译器编译并在特定CPU上运行时，循环更快。当然，保持所有数据排序也会耗费CPU时间，可能比分支错误预测的代价还要大，因此需要衡量。
如果仍然存在问题，请使用profile guided optimization（如果可用）。

Order of 2. and 3. may be switched. Optimizing your code by hand is a lot of work. On the other hand, gathering the profiling data can be difficult for some programs as well.

(**) 其中一种方法是通过例如展开循环来转换它们。您也可以让优化器自动完成。但必须进行测量，因为展开会影响与缓存的交互方式，可能会导致性能下降。