二进制32位整数快速平方根

无心人

我测试下吧

liangbch

测试环境：
CPU:
  Intel Pentium4 2.6G
  L1 data 8KB, L1 trace 12KB
  L2 cache 512KB
RAM:
   DDR 768MB
OS: windows XP
compiler: VC++6.0 release


Test case1: n=0 to 65535

iSqt_c1_lbc#: 0.00082 s
iSqt_FPU1_lbc#: 0.00095 s
iSqt_FPU3_lbc#: 0.00127 s
iSqt_FPU2_lbc#: 0.00146 s
iSqt_c2_lbc#: 0.00151 s
iSqt_gxq_c#: 0.00173 s
iSqt_FPU1_yaos#: 0.00220 s
iSqt_FPU_yaos#: 0.00235 s
iSqt_FPU2_yaos#: 0.00246 s
iSqt_ref#: 0.00306 s
iSqt_16#: 0.00398 s
iSqt_gxq_90#: 0.00434 s  (新增，90楼那个版本）
iSqt_GxQ_asm#: 0.00449 s


Test case2: n=0- 2^28-1

iSqt_FPU1_lbc#: 3.97569 s
iSqt_FPU3_lbc#: 5.32763 s
iSqt_FPU2_lbc#: 7.59953 s
iSqt_gxq_c#: 7.64778 s
iSqt_c1_lbc#: 8.14219 s
iSqt_FPU1_yaos#: 9.24091 s
iSqt_FPU_yaos#: 9.51267 s
iSqt_c2_lbc#: 10.19276 s
iSqt_FPU2_yaos#: 10.54652 s
iSqt_ref#: 12.78721 s
iSqt_16#: 14.57529 s
iSqt_gxq_90#: 18.04432 s (新增，90楼那个版本）
iSqt_GxQ_asm#: 18.64220 s

无心人

宝宝：

    今天看你42# FPU3代码除了你么处理esp外， 你也么恢复ecx啊

     另外，似乎是连续的两个fntstcw， fldcw造成的你的代码速度比俺的快

    依据的什么原理？？

liangbch

为什么我的版本比你的快，我没有仔细分析过，连续使用两个fntstcw没有什么特别的道理，我的原则是指令数尽可能少，另外要做到浮点寄存器栈的平衡。
  
我确实没有回回复ecx寄存器，我记得按照函数调用规则，如果你在子程序中修改了esi,edi,ebx,esp,ebp 等寄存器，你必须恢复它，但是你可以在子程序中仍以修改eax,edx,ecx 的值，调用者不能假定这些寄存器没有变化。
  但是如果指定了__fastcall关键字，是否必须保证调用子程序后不修改ecx的值，我刚刚查阅了一些资料，但依然没有找到确切的答案。我是假定在__fastcall子程序中可以修改ecx 的值的。

无心人

几乎同样的功能
几乎同样的指令

一个9.24
一个5.32

到底差距在哪里啊？

gxqcn

1. __declspec(naked)
   
2. UINT32 __fastcall iSqrt_ALU( UINT32 n )
   
3. {
   
4.     __asm   push    esi;
   
5.     __asm   push    edi;
   
6.     __asm   xor     eax, eax;
   
7. 
   
8. #if 1   /* Ver1: 指令数最少，但含跳转 */
   
9. 
   
10. #define SQRT_CORE_ASM(x)                    \
    
11.     __asm   lea     edx, [eax+(1UL<<(x))]   \
    
12.     __asm   shr     eax, 1                  \
    
13.     __asm   cmp     ecx, edx                \
    
14.     __asm   jb      L_##x                   \
    
15.     __asm   sub     ecx, edx                \
    
16.     __asm   add     eax, (1UL<<(x))         \
    
17.     __asm   L_##x:
    
18. 
    
19. #elif 0 /* Ver2: 常规指令，无跳转 */
    
20. 
    
21. #define SQRT_CORE_ASM(x)                    \
    
22.     __asm   mov     edi, 1UL<<(x)           \
    
23.     __asm   lea     edx, [eax+edi]          \
    
24.     __asm   shr     eax, 1                  \
    
25.     __asm   cmp     ecx, edx                \
    
26.     __asm   sbb     esi, esi                \
    
27.     __asm   not     esi                     \
    
28.     __asm   and     edx, esi                \
    
29.     __asm   and     edi, esi                \
    
30.     __asm   sub     ecx, edx                \
    
31.     __asm   add     eax, edi
    
32. 
    
33. #else   /* Ver3: 含CMOVcc指令，无跳转 */
    
34. 
    
35. #define SQRT_CORE_ASM(x)                    \
    
36.     __asm   lea     edx, [eax+(1UL<<(x))]   \
    
37.     __asm   shr     eax, 1                  \
    
38.     __asm   mov     esi, ecx                \
    
39.     __asm   sub     ecx, edx                \
    
40.     __asm   lea     edi, [eax+(1UL<<(x))]   \
    
41.     __asm   cmovb   ecx, esi                \
    
42.     __asm   cmovae  eax, edi
    
43. 
    
44. #endif
    
45. 
    
46.     SQRT_CORE_ASM(30);
    
47.     SQRT_CORE_ASM(28);
    
48.     SQRT_CORE_ASM(26);
    
49.     SQRT_CORE_ASM(24);
    
50.     SQRT_CORE_ASM(22);
    
51.     SQRT_CORE_ASM(20);
    
52.     SQRT_CORE_ASM(18);
    
53.     SQRT_CORE_ASM(16);
    
54.     SQRT_CORE_ASM(14);
    
55.     SQRT_CORE_ASM(12);
    
56.     SQRT_CORE_ASM(10);
    
57.     SQRT_CORE_ASM(8);
    
58.     SQRT_CORE_ASM(6);
    
59.     SQRT_CORE_ASM(4);
    
60.     SQRT_CORE_ASM(2);
    
61.     SQRT_CORE_ASM(0);
    
62. 
    
63. #undef SQRT_CORE_ASM
    
64. 
    
65.     __asm   pop     edi;
    
66.     __asm   pop     esi;
    
67.     __asm   ret;
    
68. }

复制代码

其对应的C代码是一样的，只是采用了不同的汇编手法。

测试结果如下：

n: 0-0x10000
iSqt_ref#: 0.00098 s
iSqt_c1_lbc#: 0.00071 s
iSqt_c2_lbc#: 0.00133 s
iSqt_FPU1_lbc#: 0.00092 s
iSqt_FPU2_lbc#: 0.00134 s
iSqt_FPU3_lbc#: 0.00118 s
iSqt_FPU_yaos#: 0.00217 s
iSqt_FPU1_yaos#: 0.00217 s
iSqt_FPU2_yaos#: 0.00208 s
iSqt_gxq_c#: 0.00140 s
iSqt_GxQ_asm#: 0.00471 s
iSqt_ALU_v1#: 0.00115 s
iSqt_ALU_v2#: 0.00580 s
iSqt_ALU_v3#: 0.00426 s
iSqt_16#: 0.00298 s


n: 0-0x4000000
iSqt_ref#: 1.03851 s
iSqt_c1_lbc#: 2.05060 s
iSqt_c2_lbc#: 1.94235 s
iSqt_FPU1_lbc#: 0.99109 s
iSqt_FPU2_lbc#: 1.41954 s
iSqt_FPU3_lbc#: 1.24257 s
iSqt_FPU_yaos#: 2.31683 s
iSqt_FPU1_yaos#: 2.38967 s
iSqt_FPU2_yaos#: 2.22774 s
iSqt_gxq_c#: 1.11229 s
iSqt_GxQ_asm#: 5.01363 s
iSqt_ALU_v1#: 1.17843 s
iSqt_ALU_v2#: 6.18305 s
iSqt_ALU_v3#: 4.54953 s
iSqt_16#: 2.95849 s

测试平台为：Windows XP SP3, P4 2.93GHz

无心人

46#代码存在冗余
需要修改

无心人

如果我的Core2Xeon测试
应该是你的V3版本最好了

无心人

1. 
   
2. __declspec(naked)
   
3. DWORD __fastcall iSqrt_FPU1_yaos(DWORD n)
   
4. {
   
5. __asm
   
6. {
   
7.    sub esp, 8
   
8.    mov [esp + 4], ecx
   
9.    fnstcw word ptr  [esp]
   
10.    fnstcw word ptr [esp + 2]
    
11.    or word ptr [esp], 0x0E60
    
12.    mov eax, ecx  
    
13.    shr eax, 31
    
14.    fld qword ptr [b32 + eax * 8]
    
15.    fild dword ptr [esp + 4]
    
16.    faddp st(1), st
    
17.    fsqrt
    
18.    fldcw word ptr [esp]
    
19.    fistp dword ptr [esp + 4]
    
20.    fldcw word ptr [esp + 2]
    
21.    mov eax, [esp + 4]
    
22.    add esp, 8
    
23.    ret
    
24.    }
    
25. }
    

复制代码

宝宝的代码里我的函数FPU1应该是这样的
稍微优化了点
执行时间减少了至少40%
我明天去学校看我机器里的代码

可能存在版本差异

无心人

今天早上
翻MMX的书

看到说，内存的内部和全部
即128位内部的64位，64位内部的32位等等。。。
如果同时发生写和读
将发生阻塞

可能是我程序代码速度慢的原因