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

无心人

有两个相同长度的双字串（可先不讨论四字串加）left, right， 长度len 现求两个双字串的加法结果，所谓加法是双字串以低地址做起始表示的长二进制数字的算术加 无论汇编还是C/C++，不论是否用双字还是四字，以1024个双字做输入参数，函数执行一百万次后的时间最少为最好 函数原型 DWORD longAdd(DWORD * result, DWORD * left, DWORD * right, DWORD len); 返回值为进位结果

无心人

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

无心人

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

无心人

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

无心人

DWORD longAdd8(DWORD result[], DWORD left[], DWORD right[], DWORD len) { __asm { mov eax, [left] mov edx, [right] mov ebx, [result] mov ecx, [len] pxor xmm0, xmm0 loop1: movq xmm1, qword ptr [eax] pshufd xmm1, xmm1, 11011100b paddq xmm0, xmm1 add eax, 8 movq xmm2, qword ptr [edx] pshufd xmm2, xmm2, 11011100b paddq xmm0, xmm2 add edx, 8 movd [ebx], xmm0 psrldq xmm0, 4 pshufd xmm1, xmm0, 11111001b psrldq xmm0, 4 paddq xmm0, xmm1 movd [ebx+4], 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一次加一个 //不知大家有什么一次加多个双字的好算法

无心人

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

无心人

DWORD longAdd4s(DWORD result[], DWORD left[], DWORD right[], DWORD len) { __asm { mov eax, [left] mov edx, [right] mov ebx, [result] xor ecx, ecx pxor mm0, mm0 loop1: movd mm1, dword ptr [eax + 4*ecx] paddq mm0, mm1 movd mm2, dword ptr [edx + 4*ecx] paddq mm0, mm2 movd dword ptr [ebx + 4*ecx], mm0 psrlq mm0, 32 add ecx, 1 cmp ecx, [len] jb loop1 movd eax, mm0 emms } } 同时宣布楼上代码作废 此代码时间稍微比三楼的longAdd4长一点点 证明直接使用一个寄存器保存的地址访问是最快的

无心人

DWORD longAdd4c(DWORD result[], DWORD left[], DWORD right[], DWORD len) { __asm { mov esi, [left] mov edi, [right] mov ebx, [result] mov ecx, [len] clc xor eax, eax loop1: mov edx, [esi] add edx, [edi] adc edx, eax mov [ebx], 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, [left] mov edx, [right] mov ebx, [result] mov ecx, [len] pxor mm0, mm0 loop1: movd mm1, [eax] add eax, 4 paddq mm0, mm1 movd mm2, [edx] paddq mm0, mm2 add edx, 4 movd [ebx], 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, [left] mov edx, [right] mov ebx, [result] xor ecx, ecx pxor mm0, mm0 loop1: movd mm1, dword ptr [eax + 4*ecx] paddq mm0, mm1 movd mm2, dword ptr [edx + 4*ecx] paddq mm0, mm2 movd dword ptr [ebx + 4*ecx], mm0 psrlq mm0, 32 add ecx, 1 cmp ecx, [len] jb loop1 movd eax, mm0 emms } } 100 万次 1024*32Bit加法 4 3423ms 4s 3415ms 4c 3710ms

无心人

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

liangbch

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