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路循环展开试一试。