无心人 发表于 2009-2-3 22:21:48

如果怕兼容性问题，用mm0也可以的
不会有不支持mmx的U了吧

无心人 发表于 2009-2-3 23:12:27

刚去查MMX的书（中文实体书）
movd是有的
也可以考虑下MMX的部分指令
所以59#应该还能优化
不知道GxQ能否给出代码的完整程序

另外，如果程序不用浮点，用不到emms
甚至，只要在浮点前用可以了

gxqcn 发表于 2009-2-4 09:54:10

测试模版

#include < stdio.h >
#include < time.h >

typedef unsigned int UINT32;

typedef UINT32 func_t( UINT32 );

#define FN(ID)      GreaterEqualBit2_##ID##F /* ex.: GreaterEqualBit2_24F */
#define TEST_VAL    314159265UL

/*

UINT32 GreaterEqualBit2_24F( UINT32 n /* 1 <= n <= 2^31+2^30 */ )
{
    ...
}

...
*/

void testFun( void )
{
    time_t t;
    UINT32 i, j;
    UINT32 fID[] = { 24, 36, 57, 58, 59 };
    func_t * funcTable[] = { FN(24), FN(36), FN(57), FN(58), FN(59) };
    func_t * pfn;

    // check result
    for ( i=0; i<sizeof(fID)/sizeof(fID); ++i )
    {
      printf( "GreaterEqualBit2_%uF(%u)=0x%X\n",
            fID, TEST_VAL, (funcTable)(TEST_VAL) );
    }

    // test speed
    printf( "\n\nn: 1-2^31\n\n" );
    for ( i=0; i<sizeof(fID)/sizeof(fID); ++i )
    {
      pfn = funcTable;

      t = time(NULL);
      for ( j=0x80000000UL; 0!=j; --j )
      {
            pfn( j );
      }
      t = time(NULL)-t;

      printf( "%u#: %u s\n", fID, t );
    }

}

int main(int argc, char* argv[])
{
    testFun();

    return 0;
}

liangbch 发表于 2009-2-4 12:50:40

我也曾想到查表法，这样，就可以省掉移位指令。这样指令是少了，但增加了访问L1/L2 cache的开销。
我曾试图在不使用查表法的基础上，精简指令条数，但没有取得突破。
在 Intel 和 AMD cpu上的测试结果表明，AMD 对cache 读写不敏感, 而Intel的cpu则对读写cache比较敏感。
在PIV cpu 运行gxq的那个版本，减少的指令条数的正效应 和 cache读写的负效 正好抵消，故和我的版本速度相当。而在AMD cpu运行 这几个版本，gxq和 无心人的版本因指令较少而胜出。

另外，我认为，测试代码和真实环境应该很难做到一致。测试代码多次读写同一处地址空间。故对RAM的存取实际上是对L1 cache的存取。而在真实环境则存在cache命中失败的情况。故在真实环境下，使用查表法的的实际运行速度应该慢于测试代码。

无心人 发表于 2009-2-4 14:05:52

__declspec(naked)
UINT32 GreaterEqualBit2_75F( UINT32 n /* 1 <= n <= 2^31+2^30 */ )
{
    __asm
    {
      movd mm0, ebx
      mov   ebx,
      bsr   ecx, ebx
      mov   eax, 1
      shl   eax, cl

      xor   ebx, eax
      xor   edx, edx
      bsr   ecx, ebx
      setne   dl
      shl   edx, cl
      add   eax, edx

      xor   ecx, ecx
      sub   ebx, edx
      cmovneecx, edx

      add   eax, ecx

      movd    ebx, mm0

      ret;
    }
}

无心人 发表于 2009-2-4 14:06:50

增加一个测试例子

无心人 发表于 2009-2-4 14:44:09

Core 2 XEON 1.6G

...\GreaterEqualBit2\Debug>GreaterEqualBit2.exe
GreaterEqualBit2_24F(314159265)=0x14000000
GreaterEqualBit2_25F(314159265)=0x14000000
GreaterEqualBit2_36F(314159265)=0x14000000
GreaterEqualBit2_57F(314159265)=0x14000000
GreaterEqualBit2_58F(314159265)=0x14000000
GreaterEqualBit2_59F(314159265)=0x14000000
GreaterEqualBit2_75F(314159265)=0x14000000
24# 24321.769 ms
25# 23220.229 ms
36# 26370.029 ms
57# 22912.707 ms
58# 25381.062 ms
59# 24208.571 ms
75# 23457.994 ms

...\GreaterEqualBit2\Debug>GreaterEqualBit2.exe
GreaterEqualBit2_24F(314159265)=0x14000000
GreaterEqualBit2_25F(314159265)=0x14000000
GreaterEqualBit2_36F(314159265)=0x14000000
GreaterEqualBit2_57F(314159265)=0x14000000
GreaterEqualBit2_58F(314159265)=0x14000000
GreaterEqualBit2_59F(314159265)=0x14000000
GreaterEqualBit2_75F(314159265)=0x14000000
24# 24329.577 ms
25# 23221.619 ms
36# 26376.303 ms
57# 22911.231 ms
58# 25355.553 ms
59# 24209.400 ms
75# 23447.267 ms

无心人 发表于 2009-2-4 15:04:06

可以认为， 查表法没有多少优势

无心人 发表于 2009-2-4 16:35:56

程序代码和编译后程序
仅要求支持MMX即可

代码


程序

无心人 发表于 2009-2-4 16:36:12

P4 Xeon 2.0G结果

GreaterEqualBit2_24F(314159265)=0x14000000
GreaterEqualBit2_25F(314159265)=0x14000000
GreaterEqualBit2_36F(314159265)=0x14000000
GreaterEqualBit2_57F(314159265)=0x14000000
GreaterEqualBit2_58F(314159265)=0x14000000
GreaterEqualBit2_59F(314159265)=0x14000000
GreaterEqualBit2_75F(314159265)=0x14000000
24# 43275.580 ms
25# 38754.110 ms
36# 68405.044 ms
57# 41526.848 ms
58# 44159.591 ms
59# 43885.799 ms
75# 43158.709 ms

GreaterEqualBit2_24F(314159265)=0x14000000
GreaterEqualBit2_25F(314159265)=0x14000000
GreaterEqualBit2_36F(314159265)=0x14000000
GreaterEqualBit2_57F(314159265)=0x14000000
GreaterEqualBit2_58F(314159265)=0x14000000
GreaterEqualBit2_59F(314159265)=0x14000000
GreaterEqualBit2_75F(314159265)=0x14000000
24# 43023.756 ms
25# 38908.013 ms
36# 68550.773 ms
57# 41309.780 ms
58# 43682.767 ms
59# 43913.680 ms
75# 43546.108 ms
=======================================
25#优势明显
页: 1 2 3 4 5 6 7 [8] 9 10 11
查看完整版本: 求bit位为1数目不超出2的正整数