大数运算基选择测试

liangbch

在38楼给出几个 以$2^32$为基，使用 MMX寄存器，可计算480bit ×480bit　的函数。其中
UInt480x480_MMX是一个使用完全循环展开，仅能计算480bit的数的版本；而UIntMul_basecase_MMX2是一个不使用循环展开，可计算任意长度的数的版本。
现在，楼主又给出一个使用4路循环展开的版本，理论上这个版本在　计算480bit × 480 bit，应该比 UIntMul_basecase_MMX2 快一些，但慢于UInt480x480_MMX

38#给出的这两个函数的原型是：
void UInt480x480_MMX( unsigned long * result, const unsigned long *  left, const unsigned long *  right );
void UIntMul_basecase_MMX2( unsigned long * result, const unsigned long *  left, const unsigned long *  right,
           unsigned long leftLen,  unsigned long rightLen );

无心人

对， 你的分析很对
看并行4路的效率了
在加法是1/6的增幅
乘法估计要更多

liangbch

乘法肯定是比1/6少。

循环展开能够提高速度的原因在于：
  1.减少了数组指针的递增指令的执行次数，如下面代码中的“lea edi, [edi+4]”，“lea ebx, [ebx+4]”，
  2.减少了比较和条件跳转指令的执行次数。如下面代码中的“sub ecx, 1“，"jnz mbinmul3".
  而其他用来工作的指令则无法减少，另一个好处是，循环展开便于合适的安排指令，使指令间的依赖很小，但这种影响一般很小。

  如果循环体很小，其中几条指令不是很耗时，则减少的这些指令占用的时间比例较大，提速明显。反之则提速不明显。对于加法，真正干活的指令占用时间少，故提升比例较高。而对于乘法，真正用来干活的指令（如pmuludq）占用的时间比例很大。故提升的比例应该很有限。

1. movd mm2, dword ptr [edi]
   
2. lea edi, [edi+4]
   
3. movd mm3, dword ptr [ebx]                        
   
4. pmuludq mm2, mm1
   
5. paddq mm0, mm3
   
6. paddq mm0, mm2
   
7. movd dword ptr [ebx], mm0
   
8. psrlq mm0, 32
   
9. lea ebx, [ebx+4]
   
10. sub ecx, 1
    
11. jnz mbinmul3

复制代码

无心人

可是乘法存在延迟长的问题啊
如果单循环，可能造成整个循环都在等乘法结果
而4个一起，只要一个好了
就能做部分工作，
处理完一个
也许剩下的乘法都不会再产生多余的延迟了

所以到底是你说的情况
还是我说的情况
要测试了才说的清

无心人

所以我分析下面的彩色指令都应该不占CPU额外时间
movd mm2, dword ptr [edi]
lea edi, [edi+4]  
movd mm3, dword ptr [ebx]                        
pmuludq mm2, mm1
paddq mm0, mm3
paddq mm0, mm2
movd dword ptr [ebx], mm0
psrlq mm0, 32
lea ebx, [ebx+4]
sub ecx, 1
jnz mbinmul3

无心人

执行顺序可能是
1、movd mm2, dword ptr [edi]
1、lea edi, [edi+4]  
1、movd mm3, dword ptr [ebx]                        
2、pmuludq mm2, mm1
2、paddq mm0, mm3
3、paddq mm0, mm2
4、movd dword ptr [ebx], mm0
4、psrlq mm0, 32
4、lea ebx, [ebx+4]
2、sub ecx, 1
5、jnz mbinmul3

liangbch

理论上，CPU存在多个执行单元，调整指令顺序，减少指令依赖可以提升速度。然而我之前的种种实验表明，这种调整指令顺序，提高并行度的做法并无多大效果，不知何故。

  另一种行之有效的优化循环的办法是减少控制指令，这种做法在某些CPU效果相当明显，我们以本贴子中出现过的程序为例给予说明。

UInt480x480_yaos,UInt480x480_MMX2,UInt480x480_MMX3 这三个函数均为以普通方式计算大数乘法的函数，
程序的逻辑也相同，不过 UInt480x480_yaos多做了一些额外的工作，即需要先将目标buffer清零。


  先看看他们在2种CPU的速度表现,计算2个长为15个DWORD的乘积，运行100万次

                     PIV 2.6           PM1.7
UInt480x480_yaos  698.655 ms        1053.610 ms
UInt480x480_MMX2  671.515 ms       863.055 ms
UInt480x480_MMX3  585.015 ms       798.775 ms

  再分析一下这几个程序的差异，这几个程序均为2重循环，在循环体中，包括真正干活的指令和循环控制的指令，循环控制的指令又分调整数组指针或计数器的指令 和 比较/跳转指令.这3个程序中内循环指令条数分别为11，10，9，其中循环控制指令分别为4，3，2条。

  第一个程序，循环控制指令是 “lea edi, [edi+4]”，“lea ebx, [ebx+4]”，“sub ecx, 1”，“jnz mbinmul3”，共4条。第一个程序，循环控制指令是“inc eax”，“cmp eax,dword ptr [esp + 16+STACK_BASE]”，“jb  innerLoop”。第三个程序循环控制指令是“inc eax”，“jnz innerLoop”。
  第三个程序的速度已经非常逼近完全循环展开的版本，尤其是在PM CPU。在PIV/PM,速度分别达到完全循环展开程序的82%/%95.

  下面给出这三个程序调用到的子程序的完整的代码。

1. 程序UInt480x480_yaos 调用到的子程序的代码
   
2. void  lMul_yaos(uint32  *result,
   
3. const uint32  *left,
   
4. const uint32  *right,
   
5. uint32 sLeft,
   
6. uint32 sRight)
   
7. {
   
8. __asm          {
   
9.              mov edx, sLeft
   
10.              mov  esi, dword ptr [left]
    
11.              mov  edi, dword ptr [right]
    
12.              mov  ebx, dword ptr [result]
    
13. mbinmul2:
    
14.              mov eax, ebx
    
15.              pxor mm0, mm0
    
16.              mov ecx, sRight                        
    
17.              movd mm1, dword ptr [esi]
    
18.              movd mm4, edi
    
19. mbinmul3:
    
20.              movd mm2, dword ptr [edi]
    
21.              lea edi, [edi+4]
    
22.              movd mm3, dword ptr [ebx]                        
    
23.              pmuludq mm2, mm1
    
24.              paddq mm0, mm3
    
25.              paddq mm0, mm2
    
26.              movd dword ptr [ebx], mm0
    
27.              psrlq mm0, 32
    
28.              lea ebx, [ebx+4]
    
29.              sub ecx, 1
    
30.              jnz mbinmul3
    
31. 
    
32.              movd edi, mm4
    
33.              movd dword ptr [ebx], mm0
    
34.              mov ebx, eax
    
35.              lea esi, [esi+4]
    
36.              lea ebx, [ebx+4]
    
37.              sub edx, 1
    
38.              jnz mbinmul2
    
39.              emms
    
40.              }
    
41. }

复制代码

1. 程序UInt480x480_MMX2 调用到的子程序的代码
   
2. 
   
3. _declspec(naked)
   
4. void UIntMul_basecase_MMX2( unsigned long * result,
   
5.                            const unsigned long *  left,
   
6.                            const unsigned long *  right,
   
7.     unsigned long leftLen,
   
8.     unsigned long rightLen )
   
9. {
   
10. #define STACK_BASE 12
    
11. __asm
    
12.     {
    
13.          push esi
    
14.          push edi
    
15.          push ebp
    
16. 
    
17.          mov ebp,  dword ptr [esp + 4+STACK_BASE]    ; result
    
18.          mov  esi,  dword ptr [esp + 8+STACK_BASE]    ; left
    
19.          mov  edi,  dword ptr [esp + 12+STACK_BASE]   ; right
    
20.          mov ecx,  dword ptr [esp + 20+STACK_BASE] ; rightLen
    
21. 
    
22. //next10:
    
23.          cmp ecx,0
    
24.          jz thisExit
    
25. 
    
26. //loop1_Init:
    
27.          xor eax,eax // j=0;i<leftLen
    
28.          pxor mm0,mm0
    
29.          movd mm2,[edi]
    
30.          jmp loop1_Cmp
    
31. 
    
32. loop1:
    
33.          movd mm1,[esi+eax*4]
    
34.          pmuludq mm1,mm2
    
35.          paddq mm0, mm1
    
36.          movd [ebp+eax*4],mm0
    
37.          inc eax
    
38.          psrlq mm0, 32 //carry
    
39. 
    
40. loop1_Cmp:
    
41.          cmp eax,dword ptr [esp + 16+STACK_BASE] //leftLen
    
42.          jb loop1
    
43.          movd [ebp+eax*4],mm0
    
44. 
    
45. //outLoopInit:
    
46.          mov ecx,1 // i=1;i<rightLen
    
47.          jmp outLoopCmp
    
48. 
    
49. outLoop:
    
50.          add ebp,4
    
51.          pxor mm0,mm0
    
52.          movd mm2,[edi+ecx*4]
    
53.          xor eax,eax
    
54.          jmp innerLoopCmp
    
55. 
    
56. innerLoop:
    
57.          movd mm1,[esi+eax*4]
    
58.          movd mm3,[ebp+eax*4]
    
59.          pmuludq mm1,mm2
    
60.          paddq mm0, mm1
    
61.          paddq mm0, mm3
    
62.          movd [ebp+eax*4],mm0
    
63.          inc eax
    
64.          psrlq mm0, 32 //carry
    
65. 
    
66. innerLoopCmp:
    
67.          cmp eax,dword ptr [esp + 16+STACK_BASE] //leftLen
    
68.          jb innerLoop
    
69.          movd [ebp+eax*4],mm0
    
70.          inc ecx
    
71. outLoopCmp:
    
72.          cmp ecx,dword ptr [esp + 20+STACK_BASE] //rightLen
    
73.          jb outLoop
    
74. 
    
75. thisExit:
    
76. 
    
77.          pop ebp
    
78.          pop edi
    
79.          pop esi
    
80. 
    
81.          emms
    
82.          ret
    
83. }
    
84. }

复制代码

1. 程序UInt480x480_MMX3 调用到的子程序的代码:
   
2. 
   
3. _declspec(naked)
   
4. void UIntMul_basecase_MMX3( unsigned long * result,
   
5.                            const unsigned long *  left,
   
6.                            const unsigned long *  right,
   
7.     unsigned long leftLen,
   
8.     unsigned long rightLen )
   
9. {
   
10. #define STACK_BASE 12
    
11. __asm
    
12.     {
    
13.          push esi
    
14.          push edi
    
15.          push ebp
    
16. 
    
17.          mov ebp,  dword ptr [esp + 4+STACK_BASE]    ; result
    
18.          mov  esi,  dword ptr [esp + 8+STACK_BASE]    ; left
    
19.          mov  edi,  dword ptr [esp + 12+STACK_BASE]   ; right
    
20.          mov ecx,  dword ptr [esp + 20+STACK_BASE] ; rightLen
    
21. 
    
22. //next10:
    
23.          cmp ecx,0
    
24.          jz thisExit
    
25. 
    
26. //loop1_Init:
    
27.          xor eax,eax // j=0;i<leftLen
    
28.          pxor mm0,mm0
    
29.          movd mm2,[edi]
    
30.          jmp loop1_Cmp
    
31. 
    
32. loop1:
    
33.          movd mm1,[esi+eax*4]
    
34.          pmuludq mm1,mm2
    
35.          paddq mm0, mm1
    
36.          movd [ebp+eax*4],mm0
    
37.          inc eax
    
38.          psrlq mm0, 32 //carry
    
39. 
    
40. loop1_Cmp:
    
41.          cmp eax,dword ptr [esp + 16+STACK_BASE] //leftLen
    
42.          jb loop1
    
43.          movd [ebp+eax*4],mm0
    
44. 
    
45. //outLoopInit:
    
46.          mov ecx,1 // i=1;i<rightLen
    
47.          mov eax,dword ptr [esp + 16+STACK_BASE] //leftLen
    
48.          lea esi,[esi+eax*4]
    
49.          lea ebp,[ebp+eax*4]
    
50.          jmp outLoopCmp
    
51. 
    
52. outLoop:
    
53.          add ebp,4
    
54.          pxor mm0,mm0
    
55.          movd mm2,[edi+ecx*4]
    
56.          mov eax,dword ptr [esp + 16+STACK_BASE] //leftLen
    
57.          neg eax
    
58.          jmp innerLoopCmp
    
59. 
    
60. innerLoop:
    
61.          movd mm1,[esi+eax*4]
    
62.          movd mm3,[ebp+eax*4]
    
63.          pmuludq mm1,mm2
    
64.          paddq mm0, mm1
    
65.          paddq mm0, mm3
    
66.          movd [ebp+eax*4],mm0
    
67.          psrlq mm0, 32 //carry
    
68.          inc eax
    
69. innerLoopCmp:
    
70.          jnz innerLoop
    
71.          movd [ebp+eax*4],mm0
    
72.          inc ecx
    
73. outLoopCmp:
    
74.          cmp ecx,dword ptr [esp + 20+STACK_BASE] //rightLen
    
75.          jb outLoop
    
76. 
    
77. thisExit:
    
78. 
    
79.          pop ebp
    
80.          pop edi
    
81.          pop esi
    
82. 
    
83.          emms
    
84.          ret
    
85. }
    
86. }

复制代码

无心人

不起作用的原因是现代CPU乃乱序执行的

liangbch

我有2台电脑，PIV 和 PM，我在优化程序的时候总是要在2台电脑上测试。某些优化手段在一台电脑上效果很明显，但在另外型号的电脑上可能不明显。现在总结一下这2台电脑的差异。
  PM ADC指令相对较慢，减少ADC指令，提速效果明显，而PIV 则不明显。
  PM 内存子系统相对较慢，减少内存写提速效果明显，而PIV 则不明显。
  PM 指令并行执行的较差，减少指令条数提速效果明显，而PIV 则不明显。
  PIV SSE2 指令中访问 128bit寄存器的指令速度很快，而PM则非常慢，用128bit寄存器优化大数乘法，速度不升反降。

无心人

PM类似现在Core核心
但属于Core一代
PM的SSE2执行单元少
且其他执行单元少
但解码单元多