一个卓有成效的汇编优化范例–使用SSE2指令优化进制转化

我的一个感兴趣的编程方向是大数计算,因此用汇编语言写了很多大数计算方面的小程序,上周突然想出一个使用SSE2指令将整数转为16进制字符串的好主意,遂付诸实现。原以为至多可提速500%,那知测试后发现,相对于最初的C语言版本,速度竟提高20倍以上,兴奋之余,遂有了这篇博客文章。

这个程序主要示范将64bit一个整数转化为16进制字符串的功能,功能和算法都比较简单。我相信许多人都写过类似的程序,但不知有没有人尝试去你优化它。这个示范程序包括3个C语言版和1个使用SSE2指令的汇编语言版。下面我们给出代码和说明。

先看这个函数最初的版本,UINT64_2_hexString_c1,为了性能起见,我们使用 __fastcall 函数约定,__fastcall 接口的函数使用寄存器来传递参数,免除了调用时压栈的开销,而且被调函数可以省去保存/恢复寄存器等指令。

上面这个函数虽然简单,然而速度却仍不理想。我们知道,在32位运行环境,对64位整数计算的C语言语句要翻译成多条指令,故速度较慢,下面这个版本使用完全的32位整数处理,故速度快于上面的版本。

上面这个函数首先将64位整数地址转化32位整数的地址,然后使用32位整数运算。代码是复杂了,但速度更快了。尽管如此,程序仍有优化的空间。

我们注意到,上面的函数包括2个循环,在每个循环中又有一个if语句,站在汇编语言视角,循环和if语句都是分支语句,可编译成比较跳转指令对。分支对CPU是个麻烦事儿,由于现代CPU普遍采用管线技术,在执行当前指令时,后面的指令已经被取到甚至译码完成。CPU遇到分支时,就需要预测那个分支最可能被执行到,从而将最可能被执行到的那个分支的代码加载到管线。当分支预测成功时,所有的指令可流畅地无停顿的执行。一旦分支预测失败,则不得不将管线中已加载测的指令全部丢弃,重新从正确的分支点取指和译码。分支预测的技术很复杂,完整的讲述需要一本书的内容。我们这里仅作简单介绍。分支预测的的实现通常是这样的,在首次遇到分支时,执行非跳转分支。在每次执行分支指令时,将实际执行情况(执行那个分支)存入历史记录。以后再遇到这个分支时,则可以根据历史记录来判断那个分支最可能被执行到。最简单的一种判断算法是,总是预测执行概率比较高的那个分支,这种分支预测方案对循环引起的分支最有效。比如一个循环次数为n的for循环,前n次总是从循环体底部跳转到头,只有最后一次循环不跳转,换言之,跳转分支执行的概率远高于非跳转分支,故CPU总是预测跳转分支。就上面的例子而言,两个循环都是固定次数的循环且循环次数很少。在这种情况下,编译器可使用循环展开的方法来消除分支,但是对于语句”if ( c>’9′ ) c+=7″ 这样的分支,分支预测技术很难奏效,0-15之间的随机数,大于9的概率37.5%,即使CPU总是预测<=’9’的那个分支,也有37.5%的预测失败的概率,分支预测失败,CPU需要付出相当的代价,需要几个甚至10个额外的周期。

我的下一个版本用到的技术就是分支消除技术,通过消除分支来提高函数执行速度,为了消除分支,不得不使用额外的语句,虽然代码变多了,但函数执行速度大大加快。

下面是终极版本,使用SSE2指令的汇编版,直接使用ALU指令编程的优化作用有限,甚至不如编译器。我们这里直接使用SSE2指令,SSE2指令主要使用XMM寄存器来工作,1个XMM寄存器可看成是4个DWORD,8个WORD,16个BYTE,1个UINT64位数转化为字符串后有16个字符,可全部装在一个XMM寄存器中,所以这个工作正好适合用SSE2指令来做。下面的汇编版的代码,用到几个16字节数组,要求16直接对齐,尽管在汇编中也可以定义16字节对齐,但我们这里把数组的定义放在C文件中,放在C文件中的好处是易于扩展,比如可在C文件中定义32字节对齐,我曾尝试在汇编文件中定义32字节对齐时,但汇编器总是报错。这里给出C语言中的常数数组的定义。

下面是微软汇编器ml.exe格式的汇编语言源代码。

上面我没有将英文注释翻译成中文。这是因为,对于汇编代码,高手不用讲,初学者不会看,故这里就不再给出更多的说明了。

下面给出主程序中的全部代码。

关于编译:本程序使用C语言和汇编语言混合编程。C语言源文件直接加到VC工程中即可。汇编语言使用VC中自带的汇编器ml.exe来编译。

方法

1. 将汇编文件加入到VC工程中。

2.选中文件,右键属性菜单,Item type选Custom Build Tool. 在Command Line一栏: 输入“ml /coff /c %(FullPath)”, 在Outputs 一栏输入”%(Filename).obj;%(Outputs)”

测试结果

函数
C1
C2
C3
SSE4
时间(纳秒)
67.95
52.71
20.16
3.18
相对速度
100%
129%
335%
2138%