分支感知编程

Question

我正在阅读那个分支错误预测可能是应用程序性能的热门瓶颈.正如我所看到的,人们经常会显示汇编代码来揭示问题,并指出程序员通常可以预测分支在大多数时间内的位置并避免分支错误预测.

我的问题是:

1-是否可以使用某种高级编程技术(即无汇编)来避免分支错误预测？

2-我应该记住用高级编程语言生成分支友好的代码(我最感兴趣的是C和C++)？

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

Answer 1

人们经常......并说明程序员通常可以预测分支的去向

(*)经验丰富的程序员经常提醒人类程序员在预测时非常糟糕.

1-是否可以使用某种高级编程技术(即无汇编)来避免分支错误预测？

不是标准的c ++或c.至少不是一个分支.您可以做的是最小化依赖关系链的深度,以便分支错误预测不会产生任何影响.现代cpu将执行分支的两个代码路径并删除未选择的代码路径.然而,这是一个限制,这就是分支预测仅在深度依赖链中起作用的原因.

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

2-我应该记住用高级编程语言生成分支友好的代码(我最感兴趣的是C和C++)？

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

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

伦丁提出了非常明智的建议

1. 测量是否重要.
2. 如果重要的话,那么
   • 最小化计算的依赖链的深度.如何做到这一点可能非常复杂,而且超出了我的专业知识,如果没有潜入装配,你就无法做到.您可以用高级语言做的是最小化条件检查的数量(**).否则,你将受编译器优化的支配.避免深度依赖链也可以更有效地使用无序超标量处理器.
   • 使您的分支始终可预测.这个效果可以在这个stackoverflow问题中看到.在这个问题中,数组上有一个循环.循环包含一个分支.分支取决于当前元素的大小.对数据进行排序时,使用特定编译器编译并在特定cpu上运行时,可以证明循环更快.当然,保持所有数据排序也会花费cpu时间,可能比分支错误预测更多,因此,测量.
3. 如果仍然存在问题,请使用配置文件引导优化(如果可用).

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

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

Answer 2

Linux内核定义likely和unlikely基于__builtin_expect gcc内置的宏:

    #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)) {
    /* ... */
}

Answer 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;
    }
    ...
};

_{请注意,这有点简单/说明性示例,因为大多数人使用copy-and-swap对值传递的参数实现复制赋值,无论如何都要避免分支.}

在这种情况下,我们分支以避免自我分配.然而,如果自我分配只是做多余的工作并且不妨碍结果的正确性,那么它通常可以让你提升现实世界的表现,只需简单地允许自我复制:

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的原因.它再次有利于扭曲常见情况和罕见情况,在性能方面将它们推向更远的地方.

虚拟调度和同质性

在面向对象的代码中,依赖关系流向抽象(稳定抽象原理,例如)的大量分支,可以以动态的形式拥有大量的分支(除了循环,当然,它们很好地适用于分支预测器) dispatch(虚函数调用或函数指针调用).

在这些情况下,常见的诱惑是将所有类型的子类型聚合到存储基指针的多态容器中,循环遍历它并在该容器中的每个元素上调用虚方法.这可能导致很多分支错误预测,特别是如果此容器一直在更新.伪代码可能如下所示:

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中找到了一些很大的收获,但是思维方式仍然在更快地消耗数据(它确实如此,并且感谢来自这里的一些帮助,比如哈罗德).

TL; DR

因此,无论如何,从高级别角度来看,这些策略可能会降低整个代码中的分支错误预测.他们缺乏计算机体系结构方面的最高水平的专业知识,但我希望这是一个适当的有用的响应,因为问题的级别.很多这样的建议在一般情况下都是模糊的,但我发现优化分支预测通常需要通过超越优化(内存,并行化,矢量化,算法)来模糊.在任何情况下,最安全的选择是确保在冒险之前掌握一个分析器.

Answer 4

也许最常见的技术是使用单独的方法进行正常和错误返回.C别无选择,但C++有例外.编译器知道异常分支是特殊的,因此是意外的.

这意味着异常分支确实很慢,因为它们是不可预测的,但非错误分支更快.平均而言,这是净胜利.

Answer 5

一般来说,保持热内循环与最常遇到的高速缓存大小成比例是个好主意.也就是说,如果你的程序一次处理数据,例如,少于32k字节,并且在它上面做了大量的工作,那么你就是在充分利用L1缓存.

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

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

无论如何,根据CPU的高速缓存大小,计算机上运行的是什么,主内存带宽/延迟等等,是否会出现分支误预测的问题会有所不同.