小代码的优化

G-Spider

用汇编写代码不一定高效，呵呵，是的，汇编爱好者可能爱上了它的灵活性。 写代码嘛，首先是解决实现问题，如果都不能实现，不谈优化，接着再优化优化你的代码，当然，如果你说你牛，就一步到位^_^。

有时候，我们可能没有很好的设计逻辑流程，举个例子， 有人在某群里发了个问题，要帮忙解决，问题如下： 求一个 int64 有效数据至少有多少 byte 长？如果是255 则有效字节长为1；若是256，则有效字节长为2 ... 最大有效字节为8，最小为0。 (假定是32位平台)面对这个问题，我想到的是bsr指令(或许有更好的思路^_^) BSR—Bit Scan Reverse BSR r32,r/m32 该指令的操作描述如下(可查阅Intel指令手册)：

1. IF SRC = 0
2. THEN
3. ZF ← 1;
4. DEST is undefined;
5. ELSE
6. ZF ← 0;
7. temp ← OperandSize – 1;
8. WHILE Bit(SRC, temp) = 0
9. DO
10. temp ← temp - 1;
11. DEST ← temp;
12. OD;
13. FI;

复制代码

对于BSR DEST,SRC，如果SRC为0，则将flag标志的ZF置1,DEST的值不确定。 否则，将ZF置0，再从SRC的高位开始扫描Bit位，当找到Bit 1则退出，将 此Bit 1的位置赋给DEST (范围:0~31)。 例如：

1. mov eax,4 ;00000000 00000000 00000000 00000100
2. bsr edx,eax ;edx=29 ZF=0
4. xor eax,eax
5. bsr edx,eax ;edx=? ZF=0

复制代码

;=================================================================== 嗯，讲了这么多没用的，呵呵。开始上面的那个解决问题^_^ 代码一：

1. bsr eax,dword ptr [buf+4] ;0~31
2. jz A00
3. add eax,32+8
4. jmp A02
5. A00:
6. bsr eax,dword ptr [buf] ;0~31
7. jz A01
8. add eax,8
9. jmp A02
10. A01:
11. xor eax,eax
12. A02:
13. shr eax,3

复制代码

以上代码，先找高32位，如果不为0，则说明有效字节数>=4，可直接跳到A02. 否则，高位均为0，开始考虑低32位，如果也均为0，则跳转到A01，清0结束。 呵呵，上面的代码跳的有点晕，改进一下： 代码二：

1. bsr eax,dword ptr [buf+4] ;0~31
2. jz A00
3. add eax,32
4. jmp A01
5. A00:
6. bsr eax,dword ptr [buf] ;0~31
7. jnz A01
8. mov eax,-8
9. A01:
10. add eax,8
11. shr eax,3

复制代码

呵呵，同样的功能，却省下了一个jmp A02 ，当均为0时，将执行mov eax,-8， 这样与下面的add eax,8相消，达到清0效果。 再改进一下： 代码三：

1. bsr eax, dword ptr [buf+4] ;0~31
2. jnz A00
3. bsr eax, dword ptr [buf] ;0~31
4. jnz A01
5. mov eax,-40
6. A00:
7. add eax,32
8. A01:
9. add eax,8
10. shr eax,3

复制代码

经过一系列的逻辑流程调整，是不是清爽了许多咧。

G-Spider

2. FNV hash 有名的hash函数。最近需要对以0结尾的字符串进行hash，找了下，觉得FNV合适。 参考：http://isthe.com/chongo/tech/comp/fnv/ FNV-1a片段如下：

1. typedef unsigned int Fnv32_t;
2. Fnv32_t __stdcall fnv_32a_str(char *str)
3. {
4. unsigned char *s = (unsigned char *)str;
5. Fnv32_t hval= 2166136261;
6. while (*s) {
7. hval ^= (Fnv32_t)*s++;
8. hval *= 0x01000193;
9. }
10. return hval;
11. }

复制代码

考虑到while循环没有do while循环的良好流程形式，所以修改如下(这样将结尾的0也hash，没什么不当^_^ ，从上面提供的网址可以查看 到，他们提供的asm代码如fast_fnv32a，均如此)

1. typedef unsigned int Fnv32_t;
2. Fnv32_t __stdcall fnv_32a_str_c(char *str)
3. {
4. unsigned char *s = (unsigned char *)str;
5. Fnv32_t hval= 2166136261;
6. do {
7. hval ^= (Fnv32_t)*s;
8. hval *= 16777619;
9. }while(*s++);
10. return hval;
11. }

复制代码

首先我参考fast_fnv32a写了一个： 代码一：

1. push esi
2. push edi
3. mov esi,[esp + 12] ;str
4. mov eax,2166136261 ;FNV1_32A_INIT
5. mov edi,16777619 ;fnv_32_prime
6. ;---------------------------
7. A00:
8. movzx ecx,byte ptr [esi]
9. xor eax,ecx
10. mul edi
11. inc esi
12. test ecx,ecx
13. jnz A00
14. ;---------------------------
15. pop edi
16. pop esi
17. retn 4

复制代码

以上代码实现了上面的c功能，然后vc下测试，启用/O2，发现不如fnv_32a_str_c的c代码高效。 查看c的反汇编如下： 代码二：

1. mov edx,[esp + 4] ;str
2. push esi
4. mov eax,2166136261 ;FNV1_32A_INIT
5. ;---------------------------
6. A00:
7. mov cl,byte ptr [edx]
8. mov esi,ecx
9. and esi,255
10. xor esi,eax
12. imul esi,16777619 ;fnv_32_prime
13. inc edx
14. mov eax,esi
15. test cl,cl
16. jnz A00
17. ;---------------------------
18. pop esi
19. retn 4

复制代码

发现其巧用imul而省下了寄存器edx，少了一对push pop,你可能想到了用movzx，又可省下不少。 mov cl ,byte ptr [edx] mov esi,ecx and esi,255 ;占6字节 替换为: movzx ecx,byte ptr [edx] mov esi,ecx 一下省了5字节，效率上mov与movzx相当。 细心一点又会发现esi不需要。 代码三：

1. mov edx,[esp + 4] ;str
2. mov eax,2166136261 ;FNV1_32A_INIT
3. ;---------------------------
4. A00:
5. movzx ecx,byte ptr [edx]
6. xor eax,ecx
7. imul eax,16777619 ;fnv_32_prime
8. inc edx
9. test ecx,ecx
10. jnz A00
11. ;---------------------------
12. retn 4

复制代码

呵呵，减小到28字节，效率也有提升。 接着，我将inc edx调整一下顺序，在我的赛扬处理器上获得了更佳的性能^_^。 代码四:

1. mov edx,[esp + 4] ;str
2. mov eax,2166136261 ;FNV1_32A_INIT
3. ;---------------------------
4. A00:
5. movzx ecx,byte ptr [edx]
6. inc edx
7. xor eax,ecx
8. imul eax,16777619 ;fnv_32_prime
9. test ecx,ecx
10. jnz A00
11. ;---------------------------
12. retn 4

复制代码

G-Spider

对于上面的代码四，由于包含imul 乘法运算，难免有点。于是想到用逻辑运算代替乘法。 fnv_32_prime这个数有点特点：16777619=0x01000193 hval =hval * (0x01000000 +256+128+16+2+1) hval + = (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24); 首先我用Intel c++优化编译，得到如下结果，性能优于代码四： 代码五：

1. mov eax,2166136261 ;FNV1_32A_INIT
2. mov edx,[esp + 4] ;str
3. push ebx
4. push esi
5. push edi
6. ;---------------------------
7. A00:
8. movzx ecx, BYTE ptr [edx]
9. xor eax, ecx
10. mov edi, eax
11. mov esi, eax
12. shl edi, 4
13. inc edx
14. shl esi, 7
15. add edi, esi
16. mov esi, eax
17. shl esi, 8
18. lea ebx, DWORD ptr [eax+eax*2]
19. shl eax, 24
20. add ebx, edi
21. add esi, eax
22. test ecx, ecx
23. lea eax, DWORD ptr [ebx+esi]
24. jne A00
25. ;---------------------------
26. pop edi
27. pop esi
28. pop ebx
29. ;---------------------------
30. retn 4

复制代码

个人自己写了个版本，性能优于代码五，且比代码五的总字节数更小： 代码六:

1. mov eax,2166136261 //;FNV1_32A_INIT
2. mov edx,[esp + 4] //;str
3. push esi
4. push edi
5. //;---------------------------
6. //;hval ^= (Fnv32_t)*s;
7. //;hval *= 0x01000193;
8. //;hval =hval * (0x01000000 +256+128+16+2+1)
9. //;hval + = (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
10. A00:
11. movzx ecx,byte ptr [edx]
12. xor eax,ecx //;hval ^= (Fnv32_t)*s;
13. lea esi,[eax+eax*2] //;(hval)+(hval<<1)
14. shl eax,4 //;(hval<<4)
15. inc edx
16. lea edi,[eax+eax*8] //;(hval<<4) + (hval<<7)
17. shl eax,4
18. add esi,eax //;(hval)+(hval<<1) +(hval<<8)
19. shl eax,16 //;(hval<<24)
20. add edi,eax //;(hval<<24) +(hval<<4) + (hval<<7)
21. test ecx,ecx
22. lea eax,[esi+edi]
23. jnz A00
24. ;---------------------------
25. pop edi
26. pop esi
27. ;---------------------------
28. retn 4

复制代码

在我的赛扬机上的测试比较：

G-Spider

基于楼上的思路，也可以对另一款不错的串hash进行优化： BKDR_C

1. unsigned int __stdcall BKDRHash0(unsigned char *str)
2. {
3. unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
4. unsigned int hash = 0;
5. do{
6. hash = hash * seed + (*str);
7. }while(*str++);
8. return hash;
9. }

复制代码

启用优化后，vc会对131分解为128+4+1 BKDR_asm0 使用乘法指令:

1. __declspec(naked)
2. unsigned int __stdcall BKDRHash1(unsigned char *str)
3. {
4. __asm{
5. xor eax, eax
6. mov edx, [4+esp]
7. A00:
8. imul eax,131
9. movzx ecx, BYTE ptr [edx]
10. inc edx
11. add eax, ecx
12. test ecx, ecx
13. jne A00
15. retn 4
16. }
17. }

复制代码

BKDR_asm1 对分解的优化:

1. __declspec(naked)
2. unsigned int __stdcall BKDRHash2(unsigned char *str)
3. {
4. __asm{
5. xor eax,eax
6. mov edx,[esp+4]
7. A00:
8. mov ecx,eax
9. shl ecx,6
10. add ecx,eax
11. inc edx
12. lea eax,[eax+ecx*2]
13. movzx ecx,byte ptr [edx]
14. add eax,ecx
15. test ecx,ecx
16. jnz A00
17. ;---------------------------
18. retn 4
19. }
20. }

复制代码

在我的赛扬机下的测试结果：

liangbch

mark, 有时间好好学习一下

wayne

膜拜一下

G-Spider

接四楼，有点小问题修正一下，131=128+2+1 , BKDR_asm1中的inc edx 应该放在 movzx之后，这样三款hash值一致，当然不影响执行效率。 是不是很不错了呢？ 对imul 与乘进行逻辑分解有个权衡，这与cpu有关。之前在赛扬上测试，imul 不如分解之后的快，今个在Intel Core i5上测试，BKDR_asm0 胜过BKDR_asm1. 可见imul 的执行效率已经大大改善。 可以设想，如果通过分解后与imul的执行效率相当，那么在稍差的机器上，分解版将完胜imul版，^_^。 出于这个想法，有必要再对BKDR_asm1做进一步优化，因为BKDR_asm1在i5上输给了BKDR_asm0. 还有可能优化吗？能否再减少A00循环体的指令数呢？ BKDRHash3：

1. __declspec(naked)
2. unsigned int __stdcall BKDRHash3(unsigned char *str)
4. { //131=128+2+1
5. //hash = hash * (128+2+1) + (*str);
6. __asm{
7. xor eax,eax
8. mov edx,[esp+4]
9. A00:
10. lea ecx,[eax+eax*2]
11. shl eax,7
12. add eax,ecx
13. movzx ecx,byte ptr [edx]
14. inc edx
15. add eax,ecx
16. test ecx,ecx
17. jnz A00
18. ;---------------------------
19. retn 4
20. }
21. }

复制代码

小结： 整个BKDR hash函数的优化过程，为了减少push pop 将movzx 置后，使得ecx 可以在movzx之前使用^_^，通过分解将乘转化为简单的逻辑运算，使用强大的指令lea 完成加乘赋值一体化。 好的组合分解又能减少不必要的操作^_^。 这次在Intel Core i5 CPU上测试，发现imul 与分解后的执行效率相当，这说明在赛扬必完胜imul ，见下图的BKDRHash1(imul版)和BDKRHash4(分解优化版)： 测试代码：

1. #include <stdio.h>
2. #include <time.h>
3. #define N0 10000000
5. //string test
6. unsigned char buf[]="InitializeCriticalSectionAndSpinCount";
8. //=====================================================
9. unsigned int __stdcall BKDRHash0(unsigned char *str)
10. {
11. unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
12. unsigned int hash = 0;
13. do{
14. hash = hash * seed + (*str);
15. }while(*str++);
16. return hash;
17. }
18. //=====================================================
19. __declspec(naked)
20. unsigned int __stdcall BKDRHash1(unsigned char *str)
22. {
23. __asm{
24. xor eax, eax
25. mov edx, [4+esp]
26. A00:
27. imul eax, 131
28. movzx ecx, BYTE ptr [edx]
29. inc edx
30. add eax, ecx
31. test ecx, ecx
32. jne A00
33. retn 4
34. }
35. }
36. //=====================================================
37. __declspec(naked)
38. unsigned int __stdcall BKDRHash2(unsigned char *str)
39. {//131=128+2+1
40. //hash =(hash * 64+hash)*2+hash + (*str);
41. __asm{
42. xor eax,eax
43. mov edx,[esp+4]
44. A00:
45. mov ecx,eax
46. shl ecx,6
47. add ecx,eax
48. lea eax,[eax+ecx*2]
49. movzx ecx,byte ptr [edx]
50. add eax,ecx
51. inc edx
52. test ecx,ecx
54. jnz A00
55. ;---------------------------
56. retn 4
57. }
58. }
60. //=====================================================
61. __declspec(naked)
62. unsigned int __stdcall BKDRHash3(unsigned char *str)
64. { //131=128+2+1
65. //hash = hash * (128+2+1) + (*str);
66. __asm{
67. xor eax,eax
68. mov edx,[esp+4]
69. A00:
70. lea ecx,[eax+eax*2]
71. shl eax,7
72. add eax,ecx
73. movzx ecx,byte ptr [edx]
74. inc edx
75. add eax,ecx
76. test ecx,ecx
77. jnz A00
78. ;---------------------------
79. retn 4
80. }
81. }
83. //=====================================================
84. int main()
85. {
86. double t0,t1,t2,t3;
87. int i,j;
88. printf("Hash Value:\n");
89. printf("%x " ,BKDRHash0(buf));
90. printf("%x " ,BKDRHash1(buf));
91. printf("%x " ,BKDRHash2(buf));
92. printf("%x " ,BKDRHash3(buf));
95. printf("\nElapsed time: \nBKDRHash0 BKDRHash1 BKDRHash2\
96. BKDRHash4(seconds)\n");
98. for(j=0;j<20;j++)
99. {
100. //=======================================================
101. t0=clock();
103. for(i=0;i<=N0;i++)
104. {
105. BKDRHash0(buf);
107. }
108. printf("%.8f ",(clock()-t0)/CLOCKS_PER_SEC);
109. //=======================================================
111. t1=clock();
113. for(i=0;i<=N0;i++)
114. {
115. BKDRHash1(buf);
117. }
118. printf("%.8f ",(clock()-t1)/CLOCKS_PER_SEC);
119. //=======================================================
120. t2=clock();
122. for(i=0;i<=N0;i++)
123. {
124. BKDRHash2(buf);
125. }
127. printf("%.8f ",(clock()-t2)/CLOCKS_PER_SEC);
128. //=======================================================
129. t3=clock();
131. for(i=0;i<=N0;i++)
132. {
133. BKDRHash3(buf);
134. }
135. printf("%.8f\n",(clock()-t3)/CLOCKS_PER_SEC);
136. //=======================================================
137. }
138. system("PAUSE");
139. return 0;
141. }

复制代码

G-Spider

5# liangbch 相互交流，共同进步^_^。 6# wayne 不敢当，我等荣幸。