B计划之长加法最佳算法讨论

无心人 发表于 2008-3-28 22:25:35

有两个相同长度的双字串（可先不讨论四字串加）left, right，长度len
现求两个双字串的加法结果，所谓加法是双字串以低地址做起始表示的长二进制数字的算术加

无论汇编还是C/C++，不论是否用双字还是四字，以1024个双字做输入参数，函数执行一百万次后的时间最少为最好
函数原型
DWORD longAdd(DWORD * result, DWORD * left, DWORD * right, DWORD len);
返回值为进位结果

无心人 发表于 2008-3-29 16:28:45

目前有三个方案
1、一次加一个双字
2、一次加一个四字
3、一次加多个四字

无心人 发表于 2008-3-29 16:49:41

一次加一个双字的，未调试
DWORD longAdd4(DWORD * result, DWORD * left, DWORD * right, DWORD len)
{
__asm
{
mov eax,
mov edx,
mov ebx,
mov ecx,
pxor mm0, mm0
loop1:
movd mm1,
add eax, 4
paddq mm0, mm1
movd mm2,
paddq mm0, mm2
add edx, 4
movd , mm0
psrlq mm0, 32
add ebx, 4
sub ecx, 1
jne loop1
movd eax, mm0
emms
}
}

无心人 发表于 2008-3-29 16:56:31

一次加一个四字的，未调试
DWORD longAdd8(DWORD * result, DWORD * left, DWORD * right, DWORD len)
{
__asm
{
mov eax,
mov edx,
mov ebx,
mov ecx,
pxor mm0, mm0
loop1:
movd mm1,
movd mm3,
add eax, 8
paddq mm0, mm1
movd mm2,
movd mm4,
add edx, 8
paddq mm0, mm2
movd , mm0
psrlq mm0, 32
paddq mm0, mm3
paddq mm0, mm4
movd , mm0
add ebx, 8
psrlq mm0, 32
sub ecx, 2
jne loop1
movd eax, mm0
emms
}
}

无心人 发表于 2008-3-29 17:32:17

DWORD longAdd8(DWORD result[], DWORD left[], DWORD right[], DWORD len)
{
__asm
{
mov eax,
mov edx,
mov ebx,
mov ecx,
pxor xmm0, xmm0
loop1:
movq xmm1, qword ptr
pshufd xmm1, xmm1, 11011100b
paddq xmm0, xmm1
add eax, 8
movq xmm2, qword ptr
pshufd xmm2, xmm2, 11011100b
paddq xmm0, xmm2
add edx, 8
movd , xmm0
psrldq xmm0, 4
pshufd xmm1, xmm0, 11111001b
psrldq xmm0, 4
paddq xmm0, xmm1
movd , xmm0
add ebx, 8
psrldq xmm0, 4
sub ecx, 2
jne loop1
movd eax, xmm0
}
}

longAdd4 1024+1024 执行100万次 3.208s 约6.2时钟周期/双字
P4 XEON 2.0
//加法改XMM寄存器则时间会增大到200%
//一次加两个也不好，时间稍微增加
//如上面用XMM加两个，还不如用XMM一次加一个
//不知大家有什么一次加多个双字的好算法

无心人 发表于 2008-3-29 22:11:41

有时间测试下面指令少的
DWORD longAdd4(DWORD * result, DWORD * left, DWORD * right, DWORD len)
{
__asm
{
xor ecx, ecx
pxor mm0, mm0
loop1:
movd mm1, left
paddq mm0, mm1
movd mm2, right
paddq mm0, mm2
movd result, mm0
psrlq mm0, 32
add ecx, 1
cmp ecx,
jne loop1
movd eax, mm0
emms
}
}

无心人 发表于 2008-3-31 08:13:13

DWORD longAdd4s(DWORD result[], DWORD left[], DWORD right[], DWORD len)
{
__asm
{
mov eax,
mov edx,
mov ebx,
xor ecx, ecx
pxor mm0, mm0
loop1:
movd mm1, dword ptr
paddq mm0, mm1
movd mm2, dword ptr
paddq mm0, mm2
movd dword ptr , mm0
psrlq mm0, 32
add ecx, 1
cmp ecx,
jb loop1
movd eax, mm0
emms
}
}

同时宣布楼上代码作废
此代码时间稍微比三楼的longAdd4长一点点
证明直接使用一个寄存器保存的地址访问是最快的

无心人 发表于 2008-3-31 14:20:17

DWORD longAdd4c(DWORD result[], DWORD left[], DWORD right[], DWORD len)
{
__asm
{
mov esi,
mov edi,
mov ebx,
mov ecx,
clc
xor eax, eax
loop1:
mov edx,
add edx,
adc edx, eax
mov , edx
xor eax, eax
adc eax, 0
add esi, 4
add edi, 4
add ebx, 4
sub ecx, 1
jne loop1
}
}

DWORD longAdd4(DWORD result[], DWORD left[], DWORD right[], DWORD len)
{
__asm
{
mov eax,
mov edx,
mov ebx,
mov ecx,
pxor mm0, mm0
loop1:
movd mm1,
add eax, 4
paddq mm0, mm1
movd mm2,
paddq mm0, mm2
add edx, 4
movd , mm0
psrlq mm0, 32
add ebx, 4
sub ecx, 1
jne loop1
movd eax, mm0
emms
}
}

DWORD longAdd4s(DWORD result[], DWORD left[], DWORD right[], DWORD len)
{
__asm
{
mov eax,
mov edx,
mov ebx,
xor ecx, ecx
pxor mm0, mm0
loop1:
movd mm1, dword ptr
paddq mm0, mm1
movd mm2, dword ptr
paddq mm0, mm2
movd dword ptr , mm0
psrlq mm0, 32
add ecx, 1
cmp ecx,
jb loop1
movd eax, mm0
emms
}
}

100 万次 1024*32Bit加法
4 3423ms
4s 3415ms
4c 3710ms

无心人 发表于 2008-4-8 13:16:20

一次加四字
如果用
x< y: (~x&y) | ((~x|y) & (x-y))
判断进位，因为共5个逻辑运算
则因为需要判断两次
每次指令大于5条
即可能造成最终指令条数超过一次加双字的情况
能不能通过XMM寄存器一次得到两个结果？
可以考虑

liangbch 发表于 2008-4-8 16:12:58

使用循环展开应该可以显著提高速度，你可以使用4路循环展开试一试。

页: [1] 2 3 4 5 6

数学研发论坛's Archiver

B计划之长加法最佳算法讨论