小代码的优化

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=29 ZF=0
xor eax,eax
bsr edx,eax ;edx=? ZF=0

复制代码

;===================================================================
嗯，讲了这么多没用的，呵呵。开始上面的那个解决问题^_^
代码一：

bsr eax,dword ptr [buf+4] ;0~31
jz A00
add eax,32+8
jmp A02
A00:
bsr eax,dword ptr [buf] ;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 [buf+4] ;0~31
jz A00
add eax,32
jmp A01
A00:
bsr eax,dword ptr [buf] ;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 [buf+4] ;0~31
jnz A00
bsr eax, dword ptr [buf] ;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,[esp + 12] ;str
mov eax,2166136261 ;FNV1_32A_INIT
mov edi,16777619 ;fnv_32_prime
;---------------------------
A00:
movzx ecx,byte ptr [esi]
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,[esp + 4] ;str
push esi
mov eax,2166136261 ;FNV1_32A_INIT
;---------------------------
A00:
mov cl,byte ptr [edx]
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 [edx]
mov    esi,ecx
and    esi,255    ;占6字节
替换为:
movzx ecx,byte ptr [edx]
mov    esi,ecx
一下省了5字节，效率上mov与movzx相当。
细心一点又会发现esi不需要。
代码三：

mov edx,[esp + 4] ;str
mov eax,2166136261 ;FNV1_32A_INIT
;---------------------------
A00:
movzx ecx,byte ptr [edx]
xor eax,ecx
imul eax,16777619 ;fnv_32_prime
inc edx
test ecx,ecx
jnz A00
;---------------------------
retn 4

复制代码

呵呵，减小到28字节，效率也有提升。
接着，我将inc edx调整一下顺序，在我的赛扬处理器上获得了更佳的性能^_^。
代码四:

mov edx,[esp + 4] ;str
mov eax,2166136261 ;FNV1_32A_INIT
;---------------------------
A00:
movzx ecx,byte ptr [edx]
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,[esp + 4] ;str
push ebx
push esi
push edi
;---------------------------
A00:
movzx ecx, BYTE ptr [edx]
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 [eax+eax*2]
shl eax, 24
add ebx, edi
add esi, eax
test ecx, ecx
lea eax, DWORD ptr [ebx+esi]
jne A00
;---------------------------
pop edi
pop esi
pop ebx
;---------------------------
retn 4

复制代码

个人自己写了个版本，性能优于代码五，且比代码五的总字节数更小：
代码六:

mov eax,2166136261 //;FNV1_32A_INIT
mov edx,[esp + 4] //;str
push esi
push edi
//;---------------------------
//;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 [edx]
xor eax,ecx //;hval ^= (Fnv32_t)*s;
lea esi,[eax+eax*2] //;(hval)+(hval<<1)
shl eax,4 //;(hval<<4)
inc edx
lea edi,[eax+eax*8] //;(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)
test ecx,ecx
lea eax,[esi+edi]
jnz A00
;---------------------------
pop edi
pop esi
;---------------------------
retn 4

复制代码

在我的赛扬机上的测试比较：

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

基于楼上的思路，也可以对另一款不错的串hash进行优化：
BKDR_C

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;
}

复制代码

启用优化后，vc会对131分解为128+4+1
BKDR_asm0 使用乘法指令:

__declspec(naked)
unsigned int __stdcall BKDRHash1(unsigned char *str)
{
__asm{
xor eax, eax
mov edx, [4+esp]
A00:
imul eax,131
movzx ecx, BYTE ptr [edx]
inc edx
add eax, ecx
test ecx, ecx
jne A00
retn 4
}
}

复制代码

BKDR_asm1 对分解的优化:

__declspec(naked)
unsigned int __stdcall BKDRHash2(unsigned char *str)
{
__asm{
xor eax,eax
mov edx,[esp+4]
A00:
mov ecx,eax
shl ecx,6
add ecx,eax
inc edx
lea eax,[eax+ecx*2]
movzx ecx,byte ptr [edx]
add eax,ecx
test ecx,ecx
jnz A00
;---------------------------
retn 4
}
}

复制代码

在我的赛扬机下的测试结果：

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,[esp+4]
A00:
lea ecx,[eax+eax*2]
shl eax,7
add eax,ecx
movzx ecx,byte ptr [edx]
inc edx
add eax,ecx
test ecx,ecx
jnz A00
;---------------------------
retn 4
}
}

复制代码

小结：
整个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, [4+esp]
A00:
imul eax, 131
movzx ecx, BYTE ptr [edx]
inc edx
add eax, ecx
test ecx, ecx
jne A00
retn 4
}
}
//=====================================================
__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,[esp+4]
A00:
mov ecx,eax
shl ecx,6
add ecx,eax
lea eax,[eax+ecx*2]
movzx ecx,byte ptr [edx]
add eax,ecx
inc edx
test ecx,ecx
jnz A00
;---------------------------
retn 4
}
}
//=====================================================
__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,[esp+4]
A00:
lea ecx,[eax+eax*2]
shl eax,7
add eax,ecx
movzx ecx,byte ptr [edx]
inc edx
add eax,ecx
test ecx,ecx
jnz A00
;---------------------------
retn 4
}
}
//=====================================================
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
不敢当，我等荣幸。

账号		自动登录	找回密码
密码			欢迎注册

[原创] 小代码的优化

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。