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

liangbch

Intel PM 1.7G
L1 Data: 32K, L1 inst: 32K
L2 cache: 2048K
RAM DDR 1248M

case 1: 计算0-65535
1）liangbch的这两个C版本排到第1和第2，iSqt_gxq_c的C版本排到了第3,不过另一个整数版本iSqt_16却是最慢的，在这个CPU上整数的版本快于浮点版本，可能与PM的整数运算能力计较强有关。
2）只有一个版本慢于参考函数。
3）各个函数的实际速度为（按速度排序）

iSqt_c1_lbc#: 0.00071 s
iSqt_c2_lbc#: 0.00137 s
iSqt_gxq_c#: 0.00170 s
iSqt_FPU1_lbc#: 0.00220 s
iSqt_FPU2_lbc#: 0.00220 s
iSqt_FPU2_yaos#: 0.00220 s
iSqt_FPU1_yaos#: 0.00290 s
iSqt_FPU3_lbc#: 0.00448 s
iSqt_FPU_yaos#: 0.00455 s
iSqt_GxQ_asm#: 0.00518 s
iSqt_ref#: 0.00525 s
iSqt_16#: 0.00751 s


case 2: 计算0-2^28-1
1）liangbch的第一个版本仍是最快的，在被开方数较大的情况下，iSqt_gxq_c 将 iSqt_c2_lbc 超越成为第2快的版本，而iSqt_c2_lbc则慢于3个浮点版本。
2）iSqt_FPU2_lbc，iSqt_FPU2_yaos，iSqt_FPU1_lbc 性能区别不大，可视为速度基本相同。
2）仍然只有iSqrt_16 慢于参考函数
3）各个函数的实际速度为（按速度排序）

iSqt_c1_lbc#: 5.73374 s
iSqt_gxq_c#: 7.73133 s
iSqt_FPU2_lbc#: 9.20537 s
iSqt_FPU2_yaos#: 9.26246 s
iSqt_FPU1_lbc#: 9.66667 s
iSqt_c2_lbc#: 10.39615 s
iSqt_FPU1_yaos#: 12.13651 s
iSqt_FPU3_lbc#: 18.79839 s
iSqt_FPU_yaos#: 19.12746 s
iSqt_GxQ_asm#: 21.65353 s
iSqt_ref#: 21.96407 s
iSqt_16#: 33.18486 s

liangbch

看了一下iSqrt_gxq_c编译后的代码，每得到1bit的结果仅仅需要6条指令。而我的确是9条指令，当被开方数较大时，iSqrt_c2_lbc 慢于iSqrt_gxq_c 也就可以理解了，gxq这个版本确实很巧妙。

   iSqrt_c2_lbc  仍然有改进的余地，现在的iSqrt_c2_lbc可直接得到前4bit初值，如果将平方表增加到256（现在是16项），这样平方表所占用的空间达到2*256=512, 则可直接得到前8bi的初值。在被开方数很大时,速度有望超过iSqrt_gxq_c，不过，我以为这个算法差不多到头了，速度很难有本质性提高了。

无心人

TO 80#
增加两个语句不会增加执行时间的

TO 81#
PM处于PIII和PIV之间， 或者说，其浮点速度慢啊

我有三点感受
1、P4级别上，纯整数指令几乎不占优势
2、Core 2以上，浮点最好了，直接用fisttp好了
3、PM以下，纯整数指令最好了

liangbch

因本帖涉及到众多技术点，故予以加精。
1. 涉及到用整数指令开方，和浮点指令开方。
2. 涉及到跳转表，bsr指令技术。
3. 涉及到使用 swtich/case语句循环展开技术。
4. 涉及到牛顿迭代法和逐位求平方根两种算法。
5. 设计到用整数指令求浮点数转化为整数的技术。

无心人

呵呵

还有问题么解决
如果诸位有兴趣
可以把整数算法完全汇编优化了

gxqcn

无心人近来喜欢用“么”这个字，估计是网络语，开始还读不大习惯。

其实有一个字更准确——“冇”（读作mǎo，没有的意思，刚才用智能拼音居然没打出来），
我老家那一带就有此方言。

无心人

呵呵

么那个意思啊
么确实是么有的意思

么比冇要容易理解啊
主要是这么说很好玩么

liangbch

我曾又写了一版 逐位开方算法(汇编版)。此算法模拟手动开方算法,不查表。每求1bit需要8条指令，但速度却并不理想。
  我看了一下，gxq的c版经编译后只有6条指令，即使用汇编重写代码，采用逐位求平方根的算法也也很难突破6条指令。所以，我以为类似的算法，gxq的C版已经达到极限，是否用汇编重写的算法已经没有多大意义了。
gxq 的6条指令如下：

1. lea        edx, DWORD PTR [eax+67108864]
   
2.         shr        eax, 1
   
3.         cmp        ecx, edx
   
4.         jb        SHORT \$L275
   
5.         sub        ecx, edx
   
6.         add        eax, 67108864

复制代码

无心人

先告一段落吧

gxqcn

我自己曾写了好几套纯ALU指令的汇编代码，
但在我的机器上测试下来的结果均不如编译器直接编译的c代码，
估计与CPU特性相关。

下面这一版本是比较优化的纯ALU汇编代码，无跳转指令：

1. __declspec(naked)
   
2. UINT32 __fastcall iSqrt( UINT32 n )
   
3. {
   
4.     __asm   push    esi;
   
5.     __asm   push    edi;
   
6.     __asm   xor     eax, eax;
   
7. 
   
8. #define SQRT_CORE_ASM(x)                    \
   
9.     __asm   lea     edx, [eax+(1UL<<(x))]   \
   
10.     __asm   shr     eax, 1                  \
    
11.     __asm   mov     esi, ecx                \
    
12.     __asm   sub     ecx, edx                \
    
13.     __asm   lea     edi, [eax+(1UL<<(x))]   \
    
14.     __asm   cmovb   ecx, esi                \
    
15.     __asm   cmovae  eax, edi
    
16. 
    
17. 
    
18.     SQRT_CORE_ASM(30);
    
19.     SQRT_CORE_ASM(28);
    
20.     SQRT_CORE_ASM(26);
    
21.     SQRT_CORE_ASM(24);
    
22.     SQRT_CORE_ASM(22);
    
23.     SQRT_CORE_ASM(20);
    
24.     SQRT_CORE_ASM(18);
    
25.     SQRT_CORE_ASM(16);
    
26.     SQRT_CORE_ASM(14);
    
27.     SQRT_CORE_ASM(12);
    
28.     SQRT_CORE_ASM(10);
    
29.     SQRT_CORE_ASM(8);
    
30.     SQRT_CORE_ASM(6);
    
31.     SQRT_CORE_ASM(4);
    
32.     SQRT_CORE_ASM(2);
    
33.     SQRT_CORE_ASM(0);
    
34. 
    
35. #undef SQRT_CORE_ASM
    
36. 
    
37.     __asm   pop     edi;
    
38.     __asm   pop     esi;
    
39.     __asm   ret;
    
40. }

复制代码

该版本估计在比较好的CPU上运行（比如无心人的），在整型指令版本中可以胜出；
由于CPU对浮点指令的提速也比较快，所以可能仍落后于浮点指令版本。

补记：在 96# 我给出了3个ALU汇编版本，即便在比较高级的 CPU 上，仍可能胜出。