Jib*_*art 7 language-agnostic performance cpu-architecture compiler-optimization branch-prediction
在谈论ifs的表现时,我们通常会谈论错误预测如何阻止管道.我看到的推荐解决方案是:
我找不到的是我们是否能尽早计算出病情,以便在可能的情况下提供帮助.所以,而不是:
... work
if (a > b) {
... more work
}
做这样的事情:
bool aGreaterThanB = a > b;
... work
if (aGreaterThanB) {
... more work
}
这样的事情可能会完全避免这个条件的停顿(取决于管道的长度和我们可以放在bool和if之间的工作量)？这并不一定是因为我写的,但有什么办法,以评估条件语句早,所以CPU不必尝试和预测的分支？
此外,如果这有帮助,编译器可能会做什么呢？
乱序执行绝对是一回事（不仅是编译器，甚至处理器芯片本身都可以对指令重新排序），但它对由数据依赖性引起的流水线停顿比由错误预测引起的停顿更有帮助。
在控制流场景中的好处在某种程度上受到以下事实的限制：在大多数体系结构中，条件分支指令仅根据标志寄存器而不是通用寄存器做出决定。除非中间的“工作”非常不寻常，否则很难提前设置标志寄存器，因为大多数指令都会更改标志寄存器（在大多数体系结构上）。
也许确定组合
TST (reg)
J(condition)
可以设计为(reg)在提前足够远的情况下最小化失速。这当然需要处理器的很大程度的帮助，而不仅仅是编译器。并且处理器设计者可能会针对设置分支标志的指令的提前（乱序）执行的更一般情况进行优化，结果标志通过流水线转发，提前结束停顿。
是的,允许尽可能早地计算分支条件是有益的,这样可以提前解决任何错误预测,并且管道的前端部分可以提前开始重新填充.在最好的情况下,如果有足够的工作已经在飞行中以完全隐藏前端气泡,那么错误预测可以是免费的.
不幸的是,在无序CPU上,早期有一个有点微妙的定义,因此让分支尽早解决并不像在源代码中移动线路那么简单 - 你可能不得不改变方式条件是计算的.
不幸的是,早先没有引用源文件中条件/分支的位置,也没有引用与比较或分支对应的汇编指令的位置.因此,在最基本的层面,它主要是7不会在你的榜样工作.
即使源级别定位很重要,它也可能在您的示例中不起作用,因为:
你已经将条件的评估向上移动并将其分配给a bool,但它不是<可以错误预测的测试(操作符),它是后续的条件分支:毕竟,它是一个分支错误预测.在您的示例中,分支在两个位置都在同一位置:其形式只是从更改if (a > b)为if (aGreaterThanB).
除此之外,你改变代码的方式不太可能欺骗大多数编译器.优化编译器不会按照您编写的顺序逐行发出代码,而是根据源级依赖关系安排他们认为合适的内容.之前提取条件可能会被忽略,因为编译器会希望将检查放在自然的位置:大约在具有标志寄存器的体系结构的分支之前.
例如,考虑以下两个简单函数的实现,它遵循您建议的模式.第二个函数将条件移动到函数的顶部.
int test1(int a, int b) {
int result = a * b;
result *= result;
if (a > b) {
return result + a;
}
return result + b * 3;
}
int test2(int a, int b) {
bool aGreaterThanB = a > b;
int result = a * b;
result *= result;
if (aGreaterThanB) {
return result + a;
}
return result + b * 3;
}
我检查了gcc,clang 2和MSVC,并且所有编译的函数都相同(编译器之间的输出不同,但对于每个编译器,两个函数的输出相同).例如,编译test2与gcc导致:
test2(int, int):
mov eax, edi
imul eax, esi
imul eax, eax
cmp edi, esi
jg .L4
lea edi, [rsi+rsi*2]
.L4:
add eax, edi
ret
该cmp指令对应于a > b条件,并且gcc已将其向下移动经过所有"工作"并将其放在jg与条件分支相邻的旁边.
因此,如果我们知道,操作源中的顺序的简单操作不工作,什么不工作？事实证明,您可以做的任何事情都可以在数据流图中"向上"移动分支条件,这可以通过允许更早地解决错误预测来提高性能.我不打算深入了解现代CPU如何依赖数据流,但您可以在这里找到一个简短的概述,并指出最后的进一步阅读.
这是一个涉及链表遍历的真实示例.
考虑将所有值相加为空终止链表的任务,该链表还将其长度1存储为列表头结构的成员.链表实现为一个list_head对象和零个或多个列表节点(具有单个int value有效负载),定义如下:
struct list_node {
int value;
list_node* next;
};
struct list_head {
int size;
list_node *first;
};
该规范的搜索循环将采用node->next == nullptr定点的最后一个节点,以确定是已经达到列表的末尾,就像这样:
long sum_sentinel(list_head list) {
int sum = 0;
for (list_node* cur = list.first; cur; cur = cur->next) {
sum += cur->value;
}
return sum;
}
这就像你得到的一样简单.
然而,这使得在cur == null节点到节点指针追逐结束时结束求和(第一个)的分支,这是数据流图中最长的依赖性.如果此分支错误预测,则错误预测的解决方案将"迟到",并且前端气泡将直接添加到运行时.
另一方面,您可以通过显式计算节点来进行求和,如下所示:
long sum_counter(list_head list) {
int sum = 0;
list_node* cur = list.first;
for (int i = 0; i < list.size; cur = cur->next, i++) {
sum += cur->value;
}
return sum;
}
将此与哨兵解决方案相比较,似乎我们增加了额外的工作:我们现在需要初始化,跟踪和减少计数4.然而,关键是这个递减依赖链非常短,因此它将"指向追踪"工作"向前运行",并且错误预测将在早期发生,同时仍然存在有效的剩余指针追踪工作,可能是运行时的大幅改进.
让我们真的尝试一下吧.首先,我们检查两个解决方案的程序集,以便我们可以验证没有任何意外情况发生:
<sum_sentinel(list_head)>:
test rsi,rsi
je 1fe <sum_sentinel(list_head)+0x1e>
xor eax,eax
loop:
add eax,DWORD PTR [rsi]
mov rsi,QWORD PTR [rsi+0x8]
test rsi,rsi
jne loop
cdqe
ret
<sum_counter(list_head)>:
test edi,edi
jle 1d0 <sum_counter(list_head)+0x20>
xor edx,edx
xor eax,eax
loop:
add edx,0x1
add eax,DWORD PTR [rsi]
mov rsi,QWORD PTR [rsi+0x8]
cmp edi,edx
jne loop:
cdqe
ret
正如预期的那样,哨兵方法稍微简单一点:在设置过程中少一条指令,在循环5中少一条指令,但总体来说,键指针追逐和加法步骤是相同的,我们期望这个循环由连续节点的延迟控制指针.
实际上,当预测影响可忽略不计时,当对短或长列表求和时,循环执行几乎相同.对于长列表,分支预测影响自动很小,因为当达到列表末尾时的单个误预测在许多节点上摊销,并且对于L1中包含的列表,运行时渐近地逐渐达到每个节点4个周期,这是什么我们期望英特尔最好的4周期负载使用延迟.
对于简短列表,如果列表模式是可预测的,则分支错误预测是可以忽略的:要么始终相同,要么循环一些适度的时间段(可以是1000或更多,具有良好的预测!).在这种情况下,当对多个短列表求和时,每个节点的时间可以少于4个周期,因为多个列表可以一次在飞行中(例如,如果汇总列表阵列).在任何情况下,两种实现方式几乎完全相同.例如,当列表总是有5个节点时,对一个列表求和的时间大约为12个周期,其中任何一个实现:
** Running benchmark group Tests written in C++ **
Benchmark Cycles BR_MIS
Linked-list w/ Sentinel 12.19 0.00
Linked-list w/ count 12.40 0.00
让我们将分支预测添加到混合中,方法是更改列表生成代码以创建平均长度为5的列表,但实际长度均匀分布[0, 10].求和代码不变:只有输入不同.随机列表长度的结果:
** Running benchmark group Tests written in C++ **
Benchmark Cycles BR_MIS
Linked-list w/ Sentinel 43.87 0.88
Linked-list w/ count 27.48 0.89
该BR_MIS列表明,由于循环退出是不可预测的,因此我们得到每个列表6几乎一个分支错误预测6.
然而,哨兵算法现在需要约44个周期而不是计数算法的~27.5个周期.计数算法快约16.5个周期.您可以使用列表长度和其他因素,并更改绝对时间,但增量几乎总是大约16-17个周期,这与最近英特尔的分支误预测惩罚大概相同!通过尽早解决分支条件,我们避免了前端泡沫,根本不会发生任何事情.
另一个例子是类似于计算浮点值的循环,比如泰勒级数近似,其中终止条件取决于计算值的某个函数.这具有与上面相同的效果:终止条件取决于慢循环携带的依赖性,因此它与计算值本身一样慢.如果退出是不可预测的,退出时你会遇到停顿.
如果您可以更改它以预先计算迭代计数,则可以使用解耦整数计数器作为终止条件,从而避免出现气泡.即使前期计算增加了一些时间,它仍然可以提供整体加速(并且计算可以与循环的第一次迭代并行运行,无论如何,因此它可能比您期望的成本低得多在它的延迟).
1 MIPS是一个有趣的例外,它没有标志寄存器 - 测试结果直接存储在通用寄存器中.
2 Clang以无分支的方式编译了这个和许多其他变体,但它仍然很有趣,因为你仍然具有相同的测试指令结构和条件移动(取代分支).
3像C++ 11一样std::list.
4事实证明,在x86上,每个节点的工作实际上在两种方法之间非常相似,因为dec隐式设置零标志的方式,所以我们不需要额外的test指令,而mov指针追逐中使用的不是因此,对抗方法有一个额外的,dec而哨兵方法有一个额外的测试,使它成为一个洗涤.
5虽然这部分只是因为gcc没有设法将递增的for循环转换为递减的循环,以利用dec设置零标志,避免使用cmp.也许更新的gcc版本做得更好.另见脚注4.
6我猜这可能接近于0.9而不是1.0,因为分支预测器仍然可以得到长度= 10的情况正确,因为一旦你循环9次,下一次迭代总是会退出.较少的合成/精确分布不会表现出来.
7我说的主要是因为在某些情况下你可以通过这样的源或汇编级重新排序来保存一两个循环,因为这样的事情会对无序处理器中的执行顺序产生轻微影响,执行顺序也是受汇编顺序影响,但仅限于数据流图的约束.另见此评论.