我的一个感兴趣的编程方向是大数计算，因此用汇编语言写了很多大数计算方面的小程序，上周突然想出一个使用SSE2指令将整数转为16进制字符串的好主意，遂付诸实现。原以为至多可提速500%，那知测试后发现，相对于最初的C语言版本，速度竟提高20倍以上，兴奋之余，遂有了这篇博客文章。
这个程序主要示范将64bit一个整数转化为16进制字符串的功能，功能和算法都比较简单。我相信许多人都写过类似的程序，但不知有没有人尝试去你优化它。这个示范程序包括3个C语言版和1个使用SSE2指令的汇编语言版。下面我们给出代码和说明。
先看这个函数最初的版本，UINT64_2_hexString_c1，为了性能起见，我们使用 __fastcall 函数约定，__fastcall 接口的函数使用寄存器来传递参数，免除了调用时压栈的开销，而且被调函数可以省去保存/恢复寄存器等指令。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//这是C语言普通版,直接使用64位整数逻辑指令和算术指令 void __fastcall UINT64_2_hexString_c1(UINT64 *p, char *buff) { UINT64 x=*p; int i; for (i=15;i>=0;i--) { char c= (x & 0xf)+'0'; if ( c>'9') c+=7; buff[i]=c; x>>=4; } buff[16]=0; } |
上面这个函数虽然简单，然而速度却仍不理想。我们知道，在32位运行环境，对64位整数计算的C语言语句要翻译成多条指令，故速度较慢，下面这个版本使用完全的32位整数处理，故速度快于上面的版本。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
void __fastcall UINT64_2_hexString_c2(UINT64 *p, char *buff) { DWORD *pDW=(DWORD *)p; DWORD x; int i; for (x=pDW[1],i=7;i>=0;i--) { char c= (x & 0xf)+'0'; if ( c>'9') c+=7; buff[i]=c; x>>=4; } for (x=pDW[0],i=7;i>=0;i--) { char c= (x & 0xf)+'0'; if ( c>'9') c+=7; buff[8+i]=c; x>>=4; } buff[16]=0; } |
上面这个函数首先将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个额外的周期。
我的下一个版本用到的技术就是分支消除技术，通过消除分支来提高函数执行速度，为了消除分支，不得不使用额外的语句，虽然代码变多了，但函数执行速度大大加快。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//这是使用消除分支技术的C语言版，在i7-4700HQ，速度是上一个版本的2.6倍 void __fastcall UINT64_2_hexString_c3(UINT64 *p, char *buff) { DWORD *pDW=(DWORD *)p; DWORD x; int i; for (x=pDW[1],i=7;i>=0;i--) { char c= (x & 0xf)+'0'; char mask= 0 -( c>'9'); //the flag is 0xff when c>'9' buff[i]= c + ( mask & 7); x>>=4; } for (x=pDW[0],i=7;i>=0;i--) { char c= (x & 0xf)+'0'; char mask= 0 -( c>'9'); //the flag is 0xff when c>'9' buff[i+8]= c + ( mask & 7); x>>=4; } buff[16]=0; } |
下面是终极版本，使用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语言中的常数数组的定义。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <stdio.h> #include <stdlib.h> typedef unsigned char BYTE; #if defined(__GNUC__) // GCC #define INTRIN_ALIGN(n) __attribute__((aligned(n))) #else #define INTRIN_ALIGN(n) __declspec(align(n)) #endif // #if defined(__GNUC__) // GCC INTRIN_ALIGN(16) BYTE i256_num_0s[16]= { '0','0','0','0','0','0','0','0', '0','0','0','0','0','0','0','0', }; INTRIN_ALIGN(16) BYTE i256_num_9s[16]= { '9','9','9','9','9','9','9','9', '9','9','9','9','9','9','9','9', }; INTRIN_ALIGN(16) BYTE i256_num_full7[16]= { 7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7, }; |
下面是微软汇编器ml.exe格式的汇编语言源代码。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
.686P .XMM .model flat _DATA SEGMENT EXTRN _i256_num_0s:BYTE EXTRN _i256_num_9s:BYTE EXTRN _i256_num_full7:BYTE _DATA ENDS PUBLIC @UINT64_2_hexString_sse2@8 _TEXT SEGMENT ; The XMM register definition for function _UINT64_2_hexString_sse2 XMM_R_DB_STR_0 TEXTEQU <XMM2> XMM_R_DB_STR_9 TEXTEQU <XMM3> XMM_R_DB_7 TEXTEQU <XMM4> XMM_R_TMP TEXTEQU <XMM1> @UINT64_2_hexString_sse2@8 PROC movq XMM0, mmword ptr [ecx] PSHUFD XMM0, XMM0, 11001101b ;now XMM0 contain 2 QWORD and low 32bits in every QWORD is valid ; We denote the value of xmm register with a string, "N" means a byte, "0" means a byte whose value is 0, ; We use low-bytes first order, ; Now, the value of XMM0 is (NNNN0000,NNNN0000),contain 2 QWORD and contain 32 bits in every qword ; the first round transform, 2 QWORD => 4 DWORD MOVDQA XMM_R_TMP, XMM0 PSLLQ XMM0, 48 ;toward high shift 48 bits ; now value of XMM0 is (000000NN, 000000NN), now bit0-bit15 of every original QWORD is in XMM0 PSRLQ XMM_R_TMP, 16 ;toward low shift 16 bits ; now value of XMM1 is (NN000000,NN000000), bit16-bit31 of every original QWORD is in XMM1 PSRLQ XMM0, 16 ;toward low shift 16 bits ; now value of XMM0 is (0000NN00,0000NN00), now bit0-bit15 of every original QWORD is in XMM0 POR XMM0, XMM_R_TMP ;merge bit0-bit15 and bit16-bit31 ; now value of XMM0 is (NN00,NN00,NN00,NN00), contain 4 DWORD, and 16 bits in every DWORD is valid ; the second round transform, 4 DWORD => 8 WORD MOVDQA XMM_R_TMP, XMM0 PSLLD XMM0, 24 ;toworad high shift 24 bits ; now value of XMM0 is (000N,000N,000N,000N), the bit0-bit7 of every original DWORD is in XMM0 PSRLD XMM_R_TMP, 8 ;toworad low shift 8 bits ; now value of XMM0 is (N000,N000,N000,N000), the bit8-bit15 of every original DWORD is in XMM1 PSRLD XMM0, 8 ;toworad low shift 8 bits ; now value of XMM0 is (00N0,00N0,00N0,00N0), the bit0-bit7 of every original DWORD is in XMM0 POR XMM0, XMM_R_TMP ;merge bit0-bit7 and bit8-bit16 ; now value of XMM0 is (N0,N0,N0,N0,N0,N0,N0,N0), contain 8 WORD, and 8 bits in every WORD is valid ; the third round transform, 8 WORD => 16 BYTE MOVDQA XMM_R_TMP, XMM0 PSLLW XMM0, 12 ;toworad high shift 12 bits ; the bit0-bit3 of every original WORD is in XMM0 PSRLW XMM_R_TMP, 4 ;toworad low shift 4 bits ; now the bit4-bit7 or every original WORD is in XMM1 PSRLW XMM0, 4 ; toworad low shift 4 bits ; the bit0-bit3 of every original WORD is in XMM0 POR XMM0, XMM_R_TMP ;merge bit0-bit3 and bit4-7 ; now value of XMM0 is (N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,N,) contain 16 BYTE, the value range of every byte is 0-15 ; pre-load array to XMM register MOVDQA XMM_R_DB_STR_0, xmmword ptr _i256_num_0s MOVDQA XMM_R_DB_STR_9, xmmword ptr _i256_num_9s POR XMM0, XMM_R_DB_STR_0 ;now the BYTE[i] of XMM0 is '0' to '0'+15 MOVDQA XMM_R_TMP, XMM0 ;now the BYTE[i] of XMM_R_TMP is '0' to '0'+15 MOVDQA XMM_R_DB_7, xmmword ptr _i256_num_full7 ;now XMM_R_DB_7 is full 7 PCMPGTB XMM_R_TMP, XMM_R_DB_STR_9 ; BYTE[i] of XMM_R_TMP (0<=i<15) is -1 if BYTE[i]>'9' PAND XMM_R_TMP, XMM_R_DB_7 ; BYTE[i] of XMM_R_TMP (0<=i<15) is 7, if BYTE[i]>'9' PADDB XMM0, XMM_R_TMP ;final result,now the BYTE[i] of XMM0 is '0'-'9' or 'A' to 'F' MOVDQU xmmword ptr [edx], XMM0 mov byte ptr [edx+16], 0 ret 0 @UINT64_2_hexString_sse2@8 ENDP _TEXT ENDS END |
上面我没有将英文注释翻译成中文。这是因为，对于汇编代码，高手不用讲，初学者不会看，故这里就不再给出更多的说明了。
下面给出主程序中的全部代码。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 |
#include <stdio.h> #include <stdlib.h> #include <string.h> /* 这个程序示范使用优化技术来实现将64位整数转化为16进制字符串。 包括3个C语言的版本和一个使用SSE2指令的汇编版本。 经测试，在我的电脑上（I7-4700HQ），汇编版本的速度是C语言普通版20倍，是分支消除技术版本的7.5倍。 作者：Baocheng Liang 完成日期：2015-7-30, 版权所有。 */ #define ARRAY_LEN 4096 #define LOOP_COUNT 2048 typedef unsigned long long UINT64; typedef unsigned long DWORD; typedef unsigned short WORD; typedef unsigned char BYTE; UINT64 g_nums[ARRAY_LEN]; char g_buff[ARRAY_LEN*16+16]; extern double currTime(); //使用高精度计时器 extern void __fastcall UINT64_2_hexString_sse2(UINT64 *p, char *buff); //使用SSE2指令的汇编版本 extern void __fastcall UINT64_2_hexString_c1(UINT64 *p, char *buff); //最普通的C语言版本 extern void __fastcall UINT64_2_hexString_c2(UINT64 *p, char *buff); //最普通32位整数的的C语言版本 extern void __fastcall UINT64_2_hexString_c3(UINT64 *p, char *buff); //使用分支消除技术的C语言版本 typedef void ( __fastcall *lpfn_UInt64_2_hexString)(UINT64 *p, char *buff); //这是C语言普通版,直接使用64位整数逻辑指令和算术指令 void __fastcall UINT64_2_hexString_c1(UINT64 *p, char *buff) { UINT64 x=*p; int i; for (i=15;i>=0;i--) { char c= (x & 0xf)+'0'; if ( c>'9') c+=7; buff[i]=c; x>>=4; } buff[16]=0; } //这是C语言改进版，使用32位整数逻辑指令和算术指令 void __fastcall UINT64_2_hexString_c2(UINT64 *p, char *buff) { DWORD *pDW=(DWORD *)p; DWORD x; int i; for (x=pDW[1],i=7;i>=0;i--) { char c= (x & 0xf)+'0'; if ( c>'9') c+=7; buff[i]=c; x>>=4; } for (x=pDW[0],i=7;i>=0;i--) { char c= (x & 0xf)+'0'; if ( c>'9') c+=7; buff[8+i]=c; x>>=4; } buff[16]=0; } //这是使用消除分支技术的C语言版，在i7-4700HQ，速度是上一个版本的2.6倍 void __fastcall UINT64_2_hexString_c3(UINT64 *p, char *buff) { DWORD *pDW=(DWORD *)p; DWORD x; int i; for (x=pDW[1],i=7;i>=0;i--) { char c= (x & 0xf)+'0'; char mask= 0 -( c>'9'); //the flag is 0xff when c>'9' buff[i]= c + ( mask & 7); x>>=4; } for (x=pDW[0],i=7;i>=0;i--) { char c= (x & 0xf)+'0'; char mask= 0 -( c>'9'); //the flag is 0xff when c>'9' buff[i+8]= c + ( mask & 7); x>>=4; } buff[16]=0; } void test_UINT64_2_hexString(lpfn_UInt64_2_hexString fp, const char *funcName) { UINT64 arr[]={ 0x0123456789abcdef, 0x02468ACE13579BDF, 0xaaaaaaaaaaaaaaaa, 0xffffffffffffffff, }; int i; char buff[17*4]; memset(buff,0,sizeof(buff)); printf("Test function %s\n",funcName); for (i=0;i<4;i++) { fp(arr+i,buff+i*17); printf("%s\n", buff+i*17); } } void perf_UINT64_2_hexString(lpfn_UInt64_2_hexString fp,const char *funcName) { int i,j; UINT64 x; char *p; double t; //初始化全局数组g_nums for (i=0;i<ARRAY_LEN;i++) { p=(char *)(&x); for (j=0;j<8;j++) p[j]= (rand() & 0xff);//get a 64bit random number g_nums[i]=x; } t=currTime(); //计时开始 g_buff[0]=0; for ( i=0;i<LOOP_COUNT;i++) { p=g_buff; for (j=0;j<ARRAY_LEN;j++) { fp( g_nums+j,p); p+=16; } } t=(currTime()-t)*1000000000; //转化时间到纳秒 printf("It take %.2f ns to run function %s\n",t/(LOOP_COUNT*ARRAY_LEN),funcName); printf("strlen(buff) is %d\n",strlen(g_buff)); } //功能测试 void test_function() { test_UINT64_2_hexString(UINT64_2_hexString_c1, "UINT64_2_hexString_c1"); test_UINT64_2_hexString(UINT64_2_hexString_c2, "UINT64_2_hexString_c2"); test_UINT64_2_hexString(UINT64_2_hexString_c3, "UINT64_2_hexString_c3"); test_UINT64_2_hexString(UINT64_2_hexString_sse2,"UINT64_2_hexString_sse2"); } //性能测试 void perf_function() { perf_UINT64_2_hexString(UINT64_2_hexString_c1, "UINT64_2_hexString_c1"); perf_UINT64_2_hexString(UINT64_2_hexString_c2, "UINT64_2_hexString_c2"); perf_UINT64_2_hexString(UINT64_2_hexString_c3, "UINT64_2_hexString_c3"); perf_UINT64_2_hexString(UINT64_2_hexString_sse2,"UINT64_2_hexString_sse2"); } int main(int argc, char* argv[]) { test_function(); perf_function(); return 0; } 补充： 这里给出跨平台的计时函数currTime的代码。 #if defined(_WIN32) #include <windows.h> static LARGE_INTEGER freq; static BOOL initFreq() { BOOL ret; if ( !QueryPerformanceFrequency( &freq) ) { ret=FALSE; } else { ret=TRUE; } return ret; } double currTime() //使用高精度计时器 { LARGE_INTEGER performanceCount; BOOL result; double time=0.0; BOOL bRet=TRUE; if (freq.QuadPart==0) { bRet=initFreq(); } if (bRet) { result=QueryPerformanceCounter( &performanceCount ); time= performanceCount.HighPart * 4294967296.0 + performanceCount.LowPart; time=time / ( freq.HighPart * 4294967296.0 + freq.LowPart); } return time; } #elif defined(__linux__) #include <sys/time.h> #include <stdio.h> #include <stdlib.h> double currTime() { struct timeval tv; gettimeofday(&tv, NULL); return (double)(tv.tv_sec) + (double)(tv.tv_usec)/1000000.00; } #else #error do not support this complier #endif |
关于编译：本程序使用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%
|