B计划之长加法最佳算法讨论

无心人

哦 知道了

liangbch

增加了2个版本，先给出在PIV 2.6上的测试结果 说明： binAdd_base30_ALU_4way_unroll2 为 binAdd_base30_ALU_4way_unroll的改进版，指令数更少，速度更快些。 binAdd_base30_ALU_8way_unroll2 为 binAdd_base30_ALU_8way_unroll的改进版，指令数更少，速度更快些，但基本与binAdd_base30_ALU_4way_unroll2 持平。 Test function: binAdd_ALU(..) 100000 times... Elapsed time: 1904.675 ms Test function: binAdd_GMP_ALU_8way_unroll(..) 100000 times... Elapsed time: 1357.660 ms Test function: binAdd_Yaos_MMX_4way_unroll(..) 100000 times... Elapsed time: 772.390 ms Test function: binAdd_base30_ALU(..) 100000 times... Elapsed time: 1203.820 ms Test function: binAdd_base30_ALU_4way_unroll(..) 100000 times... Elapsed time: 1225.580 ms Test function: binAdd_base30_ALU_4way_unroll2(..) 100000 times... Elapsed time: 1190.035 ms Test function: binAdd_base30_ALU_8way_unroll(..) 100000 times... Elapsed time: 1213.810 ms Test function: binAdd_base30_ALU_8way_unroll2(..) 100000 times... Elapsed time: 1189.320 ms Test function: binAdd_Base30_MMX_4way_unroll(..) 100000 times... Elapsed time: 903.745 ms 再给出测试代码： //基为2^30的版本另一个版本，采用4路循环展开

1. _declspec(naked)
2. DWORD binAdd_base30_ALU_4way_unroll2(DWORD *dst,
3. const DWORD *src1,
4. const DWORD *src2,
5. int size)
6. {
7. #undef BASE30_MASK
8. #define BASE30_MASK 0x3fffffff
9. _asm
10. {
11. push edi
12. push esi
13. push ebx
14. sub esp,4
16. mov ebx,[esp+16+PARAM_DST]
17. mov esi,[esp+16+PARAM_SRC1]
18. mov edi,[esp+16+PARAM_SRC2]
19. mov edx,[esp+16+PARAM_SIZE]
21. lea eax,[esi+edx*4]
22. mov [esp],eax
24. xor ecx,ecx //clear carry
25. and edx,3
26. jz a10
28. loop00:
29. add ecx,[esi]
30. add ecx,[edi]
31. mov ecx,eax
32. and eax,BASE30_MASK
33. shr ecx,30
34. mov [ebx],eax
35. lea esi,[esi+4]
36. lea edi,[edi+4]
37. lea ebx,[ebx+4]
38. dec edx
39. jnz loop00
40. a10:
41. jmp cmp00
43. ALIGN 8
44. loop01:
45. add ecx, [esi]
46. add ecx, [edi]
47. mov eax, ecx
48. and eax,BASE30_MASK
49. shr ecx,30
50. mov [ebx],eax
52. add ecx, [esi+4]
53. add ecx, [edi+4]
54. mov edx, ecx
55. and edx,BASE30_MASK
56. shr ecx,30
57. mov [ebx+4],edx
60. add ecx, [esi+8]
61. add ecx, [edi+8]
62. mov eax, ecx
63. and eax,BASE30_MASK
64. shr ecx,30
65. mov [ebx+8],eax
68. add ecx, [esi+12]
69. add ecx, [edi+12]
70. mov edx, ecx
71. and edx,BASE30_MASK
72. shr ecx,30
73. mov [ebx+12],edx
76. lea esi,[esi+16]
77. lea edi,[edi+16]
78. lea ebx,[ebx+16]
79. cmp00:
80. cmp esi,[esp]
81. jb loop01
83. thisExit:
84. add esp,4
86. pop ebx
87. pop esi
88. pop edi
89. mov eax,0
90. adc eax,0
91. ret
92. }
93. }

复制代码

//基为2^30的版本另一个版本，指令数更少，采用8路循环展开

1. _declspec(naked)
2. DWORD binAdd_base30_ALU_8way_unroll2(DWORD *dst,
3. const DWORD *src1,
4. const DWORD *src2,
5. int size)
6. {
7. #undef BASE30_MASK
8. #define BASE30_MASK 0x3fffffff
9. _asm
10. {
11. push edi
12. push esi
13. push ebx
14. sub esp,4
16. mov ebx,[esp+16+PARAM_DST]
17. mov esi,[esp+16+PARAM_SRC1]
18. mov edi,[esp+16+PARAM_SRC2]
19. mov edx,[esp+16+PARAM_SIZE]
21. lea eax,[esi+edx*4]
22. mov [esp],eax
24. xor ecx,ecx
25. and edx,7
26. jz a10
28. loop00:
29. add ecx,[esi]
30. add ecx,[edi]
31. mov eax,ecx
32. and eax,BASE30_MASK
33. shr ecx,30
34. mov [ebx],eax
35. lea esi,[esi+4]
36. lea edi,[edi+4]
37. lea ebx,[ebx+4]
38. dec edx
39. jnz loop00
40. a10:
41. jmp cmp00
43. ALIGN 8
44. loop01:
45. add ecx,[esi]
46. add ecx,[edi]
47. mov eax,ecx
48. and eax,BASE30_MASK
49. shr ecx,30
50. mov [ebx],eax
53. add ecx,[esi+4]
54. add ecx,[edi+4]
55. mov edx,ecx
56. and edx,BASE30_MASK
57. shr ecx,30
58. mov [ebx+4],edx
61. add ecx,[esi+8]
62. add ecx,[edi+8]
63. mov eax,ecx
64. and eax,BASE30_MASK
65. shr ecx,30
66. mov [ebx+8],eax
69. add ecx,[esi+12]
70. add ecx,[edi+12]
71. mov edx,ecx
72. and edx,BASE30_MASK
73. shr ecx,30
74. mov [ebx+12],edx
77. add ecx,[esi+16]
78. add ecx,[edi+16]
79. mov eax,ecx
80. and eax,BASE30_MASK
81. shr ecx,30
82. mov [ebx+16],eax
85. add ecx,[esi+20]
86. add ecx,[edi+20]
87. mov edx,ecx
88. and edx,BASE30_MASK
89. shr ecx,30
90. mov [ebx+20],edx
93. add ecx,[esi+24]
94. add ecx,[edi+24]
95. mov eax,ecx
96. and eax,BASE30_MASK
97. shr ecx,30
98. mov [ebx+24],eax
101. add ecx,[esi+28]
102. add ecx,[edi+28]
103. mov edx,ecx
104. and edx,BASE30_MASK
105. shr ecx,30
106. mov [ebx+28],edx
109. lea esi,[esi+32]
110. lea edi,[edi+32]
111. lea ebx,[ebx+32]
112. cmp00:
113. cmp esi,[esp]
114. jb loop01
116. thisExit:
117. add esp,4
118. pop ebx
119. pop esi
120. pop edi
121. mov eax,0
122. adc eax,0
123. ret
124. }
125. }

复制代码

无心人

刚把加法的SSE2加4路展开给通用化了 并顺便实现了8路展开 1024双字加，重复100万次 4路SSE2加: 2547.029 8路SSE2加: 2456.956 8路的仅提高3.5%时间 所以4路的为最佳形式了 附四路八路通用加法代码 DWORD longAdd4p(DWORD result[], DWORD left[], DWORD right[], DWORD len) { __asm { mov esi, [left] mov edi, [right] mov ebx, [result] mov ecx, [len] mov edx, ecx pxor mm0, mm0 shr ecx, 2 je loop20 loop1: movd mm1, [esi] movd mm2, [edi] paddq mm1, mm2 movd mm3, [esi+4] movd mm4, [edi+4] paddq mm3, mm4 movd mm5, [esi+8] movd mm6, [edi+8] paddq mm5, mm6 movd mm7, [esi+12] movd mm3, [edi+12] paddq mm7, mm3 paddq mm0, mm1 movd [ebx], mm0 psrlq mm0, 32 paddq mm0, mm3 movd [ebx+4], mm0 psrlq mm0, 32 paddq mm0, mm5 movd [ebx+8], mm0 psrlq mm0, 32 paddq mm0, mm7 movd [ebx+12], mm0 psrlq mm0, 32 add esi, 16 add edi, 16 add ebx, 16 sub ecx, 1 jne loop1 loop20: mov ecx, edx and ecx, 3 jz exit1 loop2: movd mm1, [esi] movd mm2, [edi] paddq mm0, mm1 paddq mm0, mm2 movd [ebx], mm0 psrlq mm0, 32 add esi, 4 add edi, 4 add ebx, 4 sub ecx, 1 jne loop2 exit1: movd eax, mm0 emms } } DWORD longAdd8p(DWORD result[], DWORD left[], DWORD right[], DWORD len) { __asm { mov esi, [left] mov edi, [right] mov ebx, [result] mov ecx, [len] mov edx, ecx pxor mm0, mm0 shr ecx, 3 je loop20 loop1: movd mm1, [esi] movd mm2, [edi] paddq mm1, mm2 movd mm3, [esi+4] movd mm4, [edi+4] paddq mm3, mm4 movd mm5, [esi+8] movd mm6, [edi+8] paddq mm5, mm6 movd mm7, [esi+12] movd mm3, [edi+12] paddq mm7, mm3 movd mm2, [esi+16] movd mm4, [edi+16] paddq mm2, mm4 paddq mm0, mm1 movd [ebx], mm0 psrlq mm0, 32 movd mm6, [esi+20] movd mm1, [edi+20] paddq mm6, mm1 paddq mm0, mm3 movd [ebx+4], mm0 psrlq mm0, 32 paddq mm0, mm5 movd [ebx+8], mm0 psrlq mm0, 32 movd mm4, [esi+24] movd mm5, [edi+24] paddq mm4, mm5 paddq mm0, mm7 movd [ebx+12], mm0 psrlq mm0, 32 movd mm1, [esi+28] movd mm3, [edi+28] paddq mm1, mm3 paddq mm0, mm2 movd [ebx+16], mm0 psrlq mm0, 32 paddq mm0, mm6 movd [ebx+20], mm0 psrlq mm0, 32 paddq mm0, mm4 movd [ebx+24], mm0 psrlq mm0, 32 paddq mm0, mm1 movd [ebx+28], mm0 psrlq mm0, 32 add esi, 32 add edi, 32 add ebx, 32 sub ecx, 1 jne loop1 loop20: mov ecx, edx and ecx, 7 jz exit1 loop2: movd mm1, [esi] movd mm2, [edi] paddq mm0, mm1 paddq mm0, mm2 movd [ebx], mm0 psrlq mm0, 32 add esi, 4 add edi, 4 add ebx, 4 sub ecx, 1 jne loop2 exit1: movd eax, mm0 emms } }

liangbch

原帖由 liangbch 于 2008-4-8 18:05 发表 对于编写高性能的程序，常常需要权衡程序效率和复杂度之间的平衡。1路->4路，性能提高明显， 4路 -〉8路 则性能提高的就很有限了。从GMP的源代码可以看出，他使用的循环展开一般为4-6路。个人觉得4路循环展开应该是一 ...

看来我在16#的断言没有错。

无心人

如果实现求圆周率程序 8路展开也许还有用处的

liangbch

8路循环展开也不是没有用武之地，对于循环体内代码很少的情况下，8路循环展开还是有优势的，如内存清0，内存复制。memcpy 源代码就使用了8路循环展开。

无心人

那可以考虑和16路展开比较

liangbch

可以预计16路循环展开对性能的提升极为有限。 哈哈，我还是想说一句，我的原则是有所为，有所不为，为了1%的性能提高，而花费%20的时间和精力，我一般不会去做。

无心人

我做4路加法消耗20-30分钟 4路改8路仅修改了10分钟 所以如果你改16路不划算 证明你代码存在难修改的问题 结构化不好

liangbch

哈哈，上面只是一个比方，我也不知道改一个函数需要耗费多少成本。 不过8路改16路应该很简单，逻辑上应该没有多大变化，但相应的也需要写一堆测试代码。 8路改为16路，提速效果应该不大，我不想尝试了。我下一步想要做的是，实现$2^30$的basecase乘法。