二进制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;
8. #if 1 /* Ver1: 指令数最少，但含跳转 */
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:
19. #elif 0 /* Ver2: 常规指令，无跳转 */
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
33. #else /* Ver3: 含CMOVcc指令，无跳转 */
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
44. #endif
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);
63. #undef SQRT_CORE_ASM
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版本最好了

无心人

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位等等。。。 如果同时发生写和读 将发生阻塞 可能是我程序代码速度慢的原因