Linux汇编之分支优化

汇编 2015年03月13日 ,

Linux汇编分支优化
分支指令对程序的性能有较大的影响,大多数现代的处理器利用指令预取缓存提高性能。而在程序运行时,指令预取缓存被填充上顺序指令。乱序引擎试图尽可能快地执行指令,即使程序前面的指令还没有执行。但是,分支指令对乱序引擎有严重的影响。本文中枫竹梦介绍在Linux汇编语言(ASM)中如何改进汇编语言的性能。

分支预测

在遇到分支指令时,处理器的乱序引擎必须确定要处理的下一条指令。乱序引擎单元利用称为分支预测前端(branch prediction front end)的独立单元确定是否应该跳转该分支。

无条件分支

对于无条件分支,确定下一条指令是简单的。但是跳转的距离有多远,下一条指令是否在缓存中,是不一定的。

在确定下一条指令的位置时,乱序引擎必须确定指令在预取缓存中是否存在。如果不存在就要清空缓存,然后从新的位置重新加载指令。这对应用程序的性能而言代价很高。

条件分支

条件分支给处理器提出了更大的挑战。对于每一个条件分支,分支预测单元必须确定是否采用分支。通常在乱序引擎执行指令时,没有充分的充分的条件确定采用哪个分支。乱序引擎采用分支预测的方式确定执行的分支。使用规则和学习的历史来实现。主要有以下3个规则:

  • 假设会采用后向分支
  • 假设不会采用向前分支
  • 以前曾经采用过的分支会再次采用

使用一般的程序设计逻辑,最常用的向后分支(跳转到前面的指令码的分支)是在循环中使用的。如:

movl $100, %ecx
loop1:
addl %cx, %eax
decl %ecx
jns loop1

执行下一条指令中有一次,即退出循环。跳转回loop1执行100次。也就是说在总计101次的预测中只有1次是错误的。

对前向分支处理会困难一些。分支预测算法假设多数情况下分支不会采用向前的方向。在程序设计逻辑中,假设紧跟在跳转指令后面的代码最可能被执行,而不是跳转到代码的其他位置。从下面的代码中可以观察到这一点:

movl -12(%ebp), %eax
cmpl -8(%ebp), %eax
jle .L2
movl -12(%ebp), %eax
movl %eax, 4(%esp)
movl $.LC0, (%esp)
call printf
jmp .L4
.L2:
movl -8(%ebp), %eax
movl %eax, 4(%esp)
movl $.LC0, (%esp)
call printf

这是在模仿高级语言分支一文中对C程序if语句汇编的部分代码。JLE指令后面的代码处理if语句的then部分。从分支预测的角度来看,汇编预测if语句的then部分比else部分更可能被执行,从而试图优化代码。

第3条规则暗示,执行了多次的分支 在多数情况下可能采用相同的路径。分支目标缓冲区(Branch Target Buffer, BTB)跟踪处理器执行的每个分支指令,分支的结果存储在缓冲区区域中。BTB信息高于分支的前两个规则。如果第一次遇到分支时,没有采用向后的方向,分支预测单元就会假设任何后续分支都不会采用向后方向,而不是假设会应用向后分支的规则。BTB的问题在于它可能会充满,这会使分支结果花费更长时间。

优化技巧

处理器尽其最大的努力优化分支,也可以在汇编语言程序中使用几个技巧来帮助处理器。

消除分支

解决分支性能问题的最显而易见的方式是尽可能消除分支的使用。如条件传送指令的使用。

有时候重复几个额外指令能够消除跳转。这种小的指令开销将容易地适合指令预取缓存,并且补偿跳转本身造成的性能影响。如:

loop:
cmpl data(, %edi, 4), %eax
je part2
call function1
jmp looptest
part2:
call function2
looptest:
inc %edi
cmpl $10, $edi
jnz loop

根据从data数组读出的值,循环调用两个函数之一。调用函数后,跳转到循环的末尾,递增数组的下标值并且返回循环的开始。每次执行第个函数时,都要使用JMP指令进行向前跳转。因为前向分支预测不会采用它,这对性能有一定的影响。修改代码如下:

loop:
cmpl data(, %edi, 4), %eax
je part2
call function1
inc %edi
cmpl $10, $edi
jnz loop
jmp end
part2:
call function2
inc %edi
cmpl $10, $edi
jnz loop
end:

在循环内不使用向前分支,相比之前消除了向前分支。

可预测分支代码优先

充分利用分支预测单元的规则提高应用程序的性能。如将最可能执行的代码安排在向顺序执行的部分,这可以通过预取缓存提高性能。对于使用后向分支的代码,试图将可能采用的分支放置在后向分支中,有时需要改变程序的逻辑来实现。

展开循环

虽然循环一般采用后向的分支规则预测。但是即使正确预测了分支,相比没有循环还是有性能方面的损失。更好的经验是尽可能消除小型的循环。

即使是简单的循环也需要每次迭代时都必须检查计数器,还有必须计算的跳转指令。可以尝试将小型的循环展开编写。虽然代码的长度变长了,但是会被更快速的执行。

(完)

如无特别说明,本站文章皆为原创,若要转载,务必请注明以下原文信息:
日志标题:《Linux汇编之分支优化》
日志链接:http://furzoom.com/linux-asm-optimized-branch/
博客名称:枫竹梦

【上一篇】
【下一篇】

发表评论

插入图片

NOTICE1:请申请gravatar头像,没有头像的评论可能不会被回复!

回到顶部