是否有可能告诉分支预测器跟随分支的可能性有多大？

Question

为了说清楚,我不打算在这里使用任何类型的便携性,所以任何将我绑定到某个盒子的解决方案都可以.

基本上,我有一个if语句将99%的时间评估为true,并且我试图剔除每个性能的最后一个时钟,我可以发出某种编译器命令(使用GCC 4.1.2和x86 ISA,如果告诉分支预测器它应该缓存该分支吗？

Answer 1

是的,但它没有任何效果.例外是Netburst之前的旧(过时)架构,即便如此,它也没有做任何可测量的事情.

英特尔在Netburst体系结构中引入了一个"分支提示"操作码,以及一些旧架构上的冷跳(默认采取后向预测,前向预测未采用)的默认静态分支预测.GCC使用__builtin_expect (x, prediction),其中预测通常为0或1. 在所有较新的处理器架构(> = Core 2)上忽略编译器发出的操作码.实际上做的事情的小角落案例就是旧Netburst架构上的冷跳.英特尔建议现在不要使用静态分支提示,可能是因为他们认为代码大小的增加比可能的边际加速更有害.

除了用于预测器的无用分支提示之外__builtin_expect,编译器还可以重新排序代码以提高缓存使用率或节省内存.

它有多种原因无法按预期工作.

• 处理器可以完美地预测小循环(n <64).
• 处理器可以完美地预测小的重复模式(n~7).
• 处理器本身可以在编译期间比编译器/程序员更好地估计分支的概率.
• 分支的可预测性(=分支将被正确预测的概率)远比分支被采用的概率重要得多.不幸的是,这是高度依赖于架构的,并且预测分支的可预测性是非常困难的.

阅读Agner Fogs 手册中有关分支预测内部工作的更多信息.另请参阅gcc 邮件列表.

Answer 2

是.http://kerneltrap.org/node/4705

这__builtin_expect是一种gcc(版本> = 2.96)为程序员提供指示编译器的分支预测信息的方法.返回值 __builtin_expect是传递给它的第一个参数(只能是一个整数).

if (__builtin_expect (x, 0))
                foo ();

     [This] would indicate that we do not expect to call `foo', since we
     expect `x' to be zero. 

Answer 3

Pentium 4(又名Netburst微体系结构)将分支预测器提示作为jcc指令的前缀,但只有P4对它们做了任何事情.见http://ref.x86asm.net/geek32.html.和 Agner Fog的优秀asm选择指南的第3.5节,来自 http://www.agner.org/optimize/.他也有一个优化C++的指南.

早期和以后的x86 CPU默默地忽略这些前缀字节. 使用可能/不太可能的提示是否有任何性能测试结果？提到PowerPC有一些跳转指令,它们具有分支预测提示作为编码的一部分.这是一个非常罕见的建筑特色.在编译时静态预测分支是很难准确的,因此通常最好将其留给硬件来解决.

关于最近的Intel和AMD CPU中的分支预测器和分支目标缓冲区的确切行为,正式发布的内容并不多.优化手册(在AMD和英特尔的网站上很容易找到)提供了一些建议,但没有记录特定的行为.有些人已经运行测试来试图实现实现,例如Core2有多少BTB条目......无论如何,明确地暗示预测器的想法已被放弃(目前).

记录的是,例如Core2有一个分支历史缓冲区,如果循环总是运行一个恒定的短迭代次数<8或16 IIRC,它可以避免错误预测循环退出.但是不要太快展开,因为一个适合64字节(或Penryn上19uops)的循环不会有指令获取瓶颈,因为它从缓冲区重放...去阅读Agner Fog的pdf,它们非常好.

另请参阅为什么英特尔在这些年中更改了静态分支预测机制？:英特尔自从Sandybridge根本不使用静态预测时,据我们从性能实验中可以看出,这些实验尝试对CPU进行逆向工程.(当动态预测未命中时,许多较旧的CPU将静态预测作为后备.正常的静态预测是不采用前向分支并且采用后向分支(因为向后分支通常是循环分支).)

效果likely()/ unlikely()使用GNU C的宏__builtin_expect(如Drakosha的回答中提到)并不能直接插入BP提示到ASM.(它可能会这样做gcc -march=pentium4,但不能在编译其他任何东西时).

实际效果是布置代码,以便快速路径具有较少的分支,并且可能更少的指令总数.这将有助于在静态预测发挥作用的情况下进行分支预测(例如,动态预测变量很冷,在CPU上可以回退到静态预测而不是仅仅让预测变量高速缓存中的分支别名.)

看看GCC的__builtin_expect在if else语句中有什么优势？代码的一个特定例子.

即使预测完美,分支机构的成本也略高于未被分支机构.当CPU以16字节的块的形式提取代码以并行解码时,采用的分支意味着该获取块中的后续指令不是要执行的指令流的一部分.它在前端产生气泡,这可能成为高吞吐量代码的瓶颈(在高速缓存未命中的后端不会停顿,并且具有高指令级并行性).

在不同的块之间跳转也可能触及更多的缓存行代码,增加了L1i缓存占用空间,并且如果它很冷,可能会导致更多的指令缓存未命中.(以及潜在的uop-cache足迹).因此,快速路径的短路和线性是另一个优势.

GCC的配置文件引导优化通常会使可能/不可能的宏变得不必要.编译器收集运行时数据,以便每个分支以何种方式进行代码布局决策,并识别热块与冷块/功能.(例如,它会展开热循环功能,但不耐寒的功能.)请参阅-fprofile-generate并-fprofile-use 在GCC手册. 如何在g ++中使用配置文件引导的优化？

否则GCC必须使用各种启发式猜测,如果你没有使用可能/不太可能的宏并且没有使用PGO. -fguess-branch-probability默认情况下启用-O1和更高版本.

https://www.phoronix.com/scan.php?page=article&item=gcc-82-pgo&num=1在Xeon可扩展服务器CPU上具有PGO与常规gcc8.2的基准测试结果.(SKYLAKE微架构-AVX512).每个基准都至少获得了一个小的加速,一些基准获益了~10%.(其中大部分可能来自于在热循环中循环展开,但其中一些可能来自更好的分支布局和其他效果.)

Answer 4

我建议而不是担心分支预测,分析代码并优化代码以减少分支数量.一个例子是循环展开,另一个例子是使用布尔编程技术而不是使用if语句.

大多数处理器都喜欢预取语句.通常,分支语句将在处理器内生成错误,导致其刷新预取队列.这是最大的惩罚.为了减少这个惩罚时间,重写(和设计)代码,以便减少可用的分支.此外,某些处理器可以有条件地执行指令而无需分支.

我通过使用循环展开和大I/O缓冲区将程序从1小时的执行时间优化到2分钟.在这种情况下,分支预测不会节省太多时间.