小代码的优化

G-Spider 发表于 2011-11-12 19:12:40

用汇编写代码不一定高效，呵呵，是的，汇编爱好者可能爱上了它的灵活性。
写代码嘛，首先是解决实现问题，如果都不能实现，不谈优化，接着再优化优化你的代码，当然，如果你说你牛，就一步到位^_^。

经验分享，相互促进！有时候，我们可能没有很好的设计逻辑流程，举个例子，

有人在某群里发了个问题，要帮忙解决，问题如下：
求一个 int64 有效数据至少有多少 byte 长？如果是255 则有效字节长为1；若是256，则有效字节长为2 ...
最大有效字节为8，最小为0。

(假定是32位平台)面对这个问题，我想到的是bsr指令(或许有更好的思路^_^)
BSR—Bit Scan Reverse

BSR r32,r/m32
该指令的操作描述如下(可查阅Intel指令手册)：IF SRC = 0
THEN
   ZF ← 1;
   DEST is undefined;
ELSE
   ZF ← 0;
   temp ← OperandSize – 1;
WHILE Bit(SRC, temp) = 0
DO
   temp ← temp - 1;
   DEST ← temp;
OD;
FI;对于BSR DEST,SRC，如果SRC为0，则将flag标志的ZF置1,DEST的值不确定。
否则，将ZF置0，再从SRC的高位开始扫描Bit位，当找到Bit 1则退出，将
此Bit 1的位置赋给DEST (范围:0~31)。
例如：mov eax,4    ;00000000 00000000 00000000 00000100
bsr edx,eax ;edx=29ZF=0

xor eax,eax
bsr edx,eax ;edx=? ZF=0;===================================================================
嗯，讲了这么多没用的，呵呵。开始上面的那个解决问题^_^
代码一：          bsr eax,dword ptr ;0~31
         jz    A00
         add eax,32+8
         jmp A02
   A00:
         bsr eax,dword ptr ;0~31
         jz    A01
         add eax,8
         jmp A02
   A01:
         xor eax,eax
   A02:
         shr eax,3以上代码，先找高32位，如果不为0，则说明有效字节数>=4，可直接跳到A02.
否则，高位均为0，开始考虑低32位，如果也均为0，则跳转到A01，清0结束。
呵呵，上面的代码跳的有点晕，改进一下：
代码二：          bsr eax,dword ptr ;0~31
         jz    A00
         add eax,32
         jmp A01
   A00:
         bsr eax,dword ptr ;0~31
         jnz A01
         mov eax,-8
   A01:
         add eax,8
         shr eax,3呵呵，同样的功能，却省下了一个jmp A02 ，当均为0时，将执行mov eax,-8，
这样与下面的add eax,8相消，达到清0效果。
再改进一下：
代码三：          bsr eax, dword ptr ;0~31
         jnz A00
         bsr eax, dword ptr ;0~31
         jnz A01
         mov eax,-40
   A00:
         add eax,32
   A01:
         add eax,8
         shr eax,3经过一系列的逻辑流程调整，是不是清爽了许多咧。

G-Spider 发表于 2011-11-12 19:55:39

2. FNV hash 有名的hash函数。最近需要对以0结尾的字符串进行hash，找了下，觉得FNV合适。
参考：http://isthe.com/chongo/tech/comp/fnv/
FNV-1a片段如下：typedef unsigned int Fnv32_t;
Fnv32_t __stdcall fnv_32a_str(char *str)
{
unsigned char *s = (unsigned char *)str;
Fnv32_t hval= 2166136261;
while (*s) {
hval ^= (Fnv32_t)*s++;
hval *= 0x01000193;
}
return hval;
}考虑到while循环没有do while循环的良好流程形式，所以修改如下(这样将结尾的0也hash，没什么不当^_^ ，从上面提供的网址可以查看
到，他们提供的asm代码如fast_fnv32a，均如此)typedef unsigned int Fnv32_t;
Fnv32_t __stdcall fnv_32a_str_c(char *str)
{
unsigned char *s = (unsigned char *)str;
Fnv32_t hval= 2166136261;
do {
hval ^= (Fnv32_t)*s;
hval *= 16777619;
}while(*s++);
return hval;
}首先我参考fast_fnv32a写了一个：
代码一：       push esi
      push edi
      mov esi,    ;str
      mov eax,2166136261    ;FNV1_32A_INIT
      mov edi,16777619    ;fnv_32_prime
   ;---------------------------
   A00:
      movzx ecx,byte ptr
      xor eax,ecx
      mul edi
      inc esi
      test ecx,ecx
      jnz A00
   ;---------------------------
      pop edi
      pop esi
      retn 4以上代码实现了上面的c功能，然后vc下测试，启用/O2，发现不如fnv_32a_str_c的c代码高效。
查看c的反汇编如下：
代码二： mov edx,    ;str
push esi

mov eax,2166136261    ;FNV1_32A_INIT
;---------------------------
A00:
mov cl,byte ptr
mov esi,ecx
and esi,255
xor esi,eax

imul esi,16777619    ;fnv_32_prime
inc edx
mov eax,esi
test cl,cl
jnz A00
;---------------------------
pop esi
retn 4发现其巧用imul而省下了寄存器edx，少了一对push pop,你可能想到了用movzx，又可省下不少。
mov cl ,byte ptr
mov esi,ecx
and esi,255    ;占6字节
替换为:
movzx ecx,byte ptr
mov esi,ecx
一下省了5字节，效率上mov与movzx相当。
细心一点又会发现esi不需要。
代码三： mov edx,    ;str
mov eax,2166136261    ;FNV1_32A_INIT
;---------------------------
A00:
movzx ecx,byte ptr
xor eax,ecx
imul eax,16777619    ;fnv_32_prime
inc edx
test ecx,ecx
jnz A00
;---------------------------
retn 4呵呵，减小到28字节，效率也有提升。
接着，我将inc edx调整一下顺序，在我的赛扬处理器上获得了更佳的性能^_^。
代码四: mov edx,    ;str
mov eax,2166136261    ;FNV1_32A_INIT
;---------------------------
A00:
movzx ecx,byte ptr
inc edx
xor eax,ecx
imul eax,16777619    ;fnv_32_prime
test ecx,ecx
jnz A00
;---------------------------
retn 4

G-Spider 发表于 2011-11-13 10:37:24

本帖最后由 G-Spider 于 2011-11-13 10:38 编辑

对于上面的代码四，由于包含imul 乘法运算，难免有点。于是想到用逻辑运算代替乘法。
fnv_32_prime这个数有点特点：16777619=0x01000193
hval =hval * (0x01000000+256+128+16+2+1)
hval + = (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
首先我用Intel c++优化编译，得到如下结果，性能优于代码四：
代码五： mov eax,2166136261    ;FNV1_32A_INIT
mov edx,    ;str
push ebx
push esi
push edi
;---------------------------
A00:
movzx ecx, BYTE ptr
xor eax, ecx
mov edi, eax
mov esi, eax
shl edi, 4
inc edx
shl esi, 7
add edi, esi
mov esi, eax
shl esi, 8
lea ebx, DWORD ptr
shl eax, 24
add ebx, edi
add esi, eax
test ecx, ecx
lea eax, DWORD ptr
jne A00
;---------------------------
pop edi
pop esi
pop ebx
;---------------------------
retn 4个人自己写了个版本，性能优于代码五，且比代码五的总字节数更小：
代码六: mov eax,2166136261    //;FNV1_32A_INIT
mov edx,    //;str
pushesi
pushedi
//;---------------------------
//;hval ^= (Fnv32_t)*s;
//;hval *= 0x01000193;
//;hval =hval * (0x01000000+256+128+16+2+1)
//;hval + = (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24);
A00:
movzx ecx,byte ptr
xor eax,ecx             //;hval ^= (Fnv32_t)*s;
lea esi,    //;(hval)+(hval<<1)
shl eax,4             //;(hval<<4)
inc edx
lea edi,    //;(hval<<4) + (hval<<7)
shl eax,4
add esi,eax             //;(hval)+(hval<<1) +(hval<<8)
shl eax,16             //;(hval<<24)
add edi,eax             //;(hval<<24) +(hval<<4) + (hval<<7)
testecx,ecx
lea eax,
jnz A00
;---------------------------
pop edi
pop esi
;---------------------------
retn 4在我的赛扬机上的测试比较：

G-Spider 发表于 2011-11-13 10:53:03

基于楼上的思路，也可以对另一款不错的串hash进行优化：
BKDR_Cunsigned int __stdcall BKDRHash0(unsigned char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
do{
   hash = hash * seed + (*str);
}while(*str++);
return hash;
}启用优化后，vc会对131分解为128+4+1
BKDR_asm0 使用乘法指令:__declspec(naked)
unsigned int __stdcall BKDRHash1(unsigned char *str)
{
__asm{
   xor eax, eax
   mov edx,
A00:
   imuleax,131
   movzx ecx, BYTE ptr
   inc edx
   add eax, ecx
   testecx, ecx
   jne A00

   retn    4
   }
}BKDR_asm1 对分解的优化:__declspec(naked)
unsigned int __stdcall BKDRHash2(unsigned char *str)
{
__asm{
   xor eax,eax
   mov edx,
A00:
   mov ecx,eax
   shl ecx,6
   add ecx,eax
   inc edx
   lea eax,
   movzx ecx,byte ptr
   add eax,ecx
   testecx,ecx
   jnz A00
;---------------------------
   retn4
   }
}在我的赛扬机下的测试结果：

liangbch 发表于 2011-11-14 10:26:50

mark, 有时间好好学习一下

wayne 发表于 2011-11-14 10:56:22

膜拜一下

G-Spider 发表于 2011-11-14 14:28:38

接四楼，有点小问题修正一下，131=128+2+1 , BKDR_asm1中的inc edx 应该放在 movzx之后，这样三款hash值一致，当然不影响执行效率。
是不是很不错了呢？
对imul 与乘进行逻辑分解有个权衡，这与cpu有关。之前在赛扬上测试，imul 不如分解之后的快，今个在Intel Core i5上测试，BKDR_asm0 胜过BKDR_asm1.
可见imul 的执行效率已经大大改善。
可以设想，如果通过分解后与imul的执行效率相当，那么在稍差的机器上，分解版将完胜imul版，^_^。
出于这个想法，有必要再对BKDR_asm1做进一步优化，因为BKDR_asm1在i5上输给了BKDR_asm0.

还有可能优化吗？能否再减少A00循环体的指令数呢？
BKDRHash3：__declspec(naked)
unsigned int __stdcall BKDRHash3(unsigned char *str)

{ //131=128+2+1
//hash = hash * (128+2+1) + (*str);
__asm{
   xor eax,eax
   mov edx,
A00:
   lea ecx,
   shl eax,7
   add eax,ecx
   movzx ecx,byte ptr
   inc edx
   add eax,ecx
   testecx,ecx
   jnz A00
;---------------------------
   retn4
   }
}小结：
整个BKDR hash函数的优化过程，为了减少push pop 将movzx 置后，使得ecx 可以在movzx之前使用^_^，通过分解将乘转化为简单的逻辑运算，使用强大的指令lea 完成加乘赋值一体化。
好的组合分解又能减少不必要的操作^_^。
这次在Intel Core i5 CPU上测试，发现imul 与分解后的执行效率相当，这说明在赛扬必完胜imul ，见下图的BKDRHash1(imul版)和BDKRHash4(分解优化版)：

测试代码：#include <stdio.h>
#include <time.h>
#define N0 10000000

//string test
unsigned char buf[]="InitializeCriticalSectionAndSpinCount";

//=====================================================
unsigned int __stdcall BKDRHash0(unsigned char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;
do{
   hash = hash * seed + (*str);
}while(*str++);
return hash;
}
//=====================================================
__declspec(naked)
unsigned int __stdcall BKDRHash1(unsigned char *str)

{
__asm{
   xor eax, eax
   mov edx,
A00:
   imuleax, 131
   movzx ecx, BYTE ptr
   inc edx
   add eax, ecx
   testecx, ecx
   jne A00
   retn4
   }
}
//=====================================================
__declspec(naked)
unsigned int __stdcall BKDRHash2(unsigned char *str)
{//131=128+2+1
//hash =(hash * 64+hash)*2+hash + (*str);
__asm{
   xor eax,eax
   mov edx,
A00:
   mov ecx,eax
   shl ecx,6
   add ecx,eax
   lea eax,
   movzx ecx,byte ptr
   add eax,ecx
   inc edx
   testecx,ecx

   jnz A00
;---------------------------
   retn4
   }
}

//=====================================================
__declspec(naked)
unsigned int __stdcall BKDRHash3(unsigned char *str)

{ //131=128+2+1
//hash = hash * (128+2+1) + (*str);
__asm{
   xor eax,eax
   mov edx,
A00:
   lea ecx,
   shl eax,7
   add eax,ecx
   movzx ecx,byte ptr
   inc edx
   add eax,ecx
   testecx,ecx
   jnz A00
;---------------------------
   retn4
   }
}

//=====================================================
int main()
{
double t0,t1,t2,t3;
int i,j;
printf("Hash Value:\n");
printf("%x       ",BKDRHash0(buf));
printf("%x       ",BKDRHash1(buf));
printf("%x       ",BKDRHash2(buf));
printf("%x       ",BKDRHash3(buf));

printf("\nElapsed time: \nBKDRHash0    BKDRHash1    BKDRHash2\
   BKDRHash4(seconds)\n");

for(j=0;j<20;j++)
{
         //=======================================================
         t0=clock();

         for(i=0;i<=N0;i++)
         {
            BKDRHash0(buf);

         }
         printf("%.8f    ",(clock()-t0)/CLOCKS_PER_SEC);
         //=======================================================

         t1=clock();

         for(i=0;i<=N0;i++)
         {
            BKDRHash1(buf);

         }
         printf("%.8f    ",(clock()-t1)/CLOCKS_PER_SEC);
         //=======================================================
         t2=clock();

         for(i=0;i<=N0;i++)
         {
            BKDRHash2(buf);
         }

         printf("%.8f    ",(clock()-t2)/CLOCKS_PER_SEC);
         //=======================================================
         t3=clock();

         for(i=0;i<=N0;i++)
         {
            BKDRHash3(buf);
         }
         printf("%.8f\n",(clock()-t3)/CLOCKS_PER_SEC);
         //=======================================================
}
system("PAUSE");
return 0;

}

G-Spider 发表于 2011-11-14 14:38:44

5# liangbch
相互交流，共同进步^_^。

6# wayne
不敢当，我等荣幸。

页: [1]

数学研发论坛's Archiver

小代码的优化