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

无心人

那必须保证数字bit长度是128倍数

liangbch

No,循环展开可处理任意长度，加上一个 收尾处理部分 即可。 如长度为 103，使用4路循环展开，则 第1部分：循环步：25，每步 处理 4DWORD， 总共处理 25×4=100 DWORD 第2部分（收尾部分)：循环步：3， 每步处理 1 DWORD， 总共处理 3×1=3 DWORD 二者合计，共处理了 103 DWORD。

无心人

movd mm1, [esi] movd mm2, [edi] paddq mm1, mm2 movd mm3, [esi+4] movd mm4, [edi+4] paddq mm3, mm4 movd mm5, [esi+8] movd mm6, [edi+8] paddq mm5, mm6 movd mm7, [esi+12] movd mm2, [edi+12] paddq mm7, mm2 paddq mm0, mm1 movd [ebx], mm0 psrlq mm0, 32 paddq mm0, mm3 movd [ebx+4], mm0 psrlq mm0, 32 paddq mm0, mm5 movd [ebx+8], mm0 psrlq mm0, 32 paddq mm0, mm7 movd [ebx+12], mm0 psrlq mm0, 32 add esi, 16 add edi, 16 add ebx, 16 sub ecx, 1 jne label 29条， 如果使用ecx做地址参数，可到27条 原4次循环是最低36条， 节约的有限， 主要看并行度 [ 本帖最后由 无心人 于 2008-4-16 11:30 编辑 ]

无心人

确实能提高速度 原始的3220ms/100万次*1024DWORD 4个一起2588ms/100万次*1024DWORD 不过这个128bit长度的倍数要提前做好限定 否则只能考虑在程序里处理剩余部分！！

无心人

收尾倒好做 mov ecx, [len] mov edx, ecx shr ecx, 2 //ecx 为128单位的数量 je label收尾 //肯定长度不够128 。。。 。。。 //收尾 mov ecx, edx and ecx, 3 //ecx = 尾部双字个数 je 退出 //没有尾部 。。。 。。。 //退出 如果考虑并行，还一个问题，一次加多少合适，最多加的数字是很大的 7个寄存器轮流来，可以无限并行下去， 我想合适的数字在下面中选 2, 4, 8, 16个双字一起加 =================================== 刚计算了，4个一起加， 每个双字消耗约等于5时钟 一个的大概是6， 呵呵，基数太小了 改进1个时钟就造成程序复杂很多啊

liangbch

对于编写高性能的程序，常常需要权衡程序效率和复杂度之间的平衡。1路->4路，性能提高明显， 4路 -〉8路 则性能提高的就很有限了。从GMP的源代码可以看出，他使用的循环展开一般为4-6路。个人觉得4路循环展开应该是一个不错的选择，兼顾了复杂性和性能。

无心人

恩 回家路上也想了 就在四个加上最合适了 不过，29条指令消耗了大约20个时钟 不知道算不算好 ===================================== 另外，似乎乘法也能一次乘四个吧

liangbch

我觉得，如果采用基为 $2^30$,使用ALU指令来做，速度应该也很快。有空我给出一个实现。

无心人

你是说加法么？ 加法用2^30多一个and操作

liangbch

这次你说对了。但是，AND指令很快，相对于使用$2^32$必须使用ADC 指令，速度也应该快不少，另外使用一些快速的ALU指令，也许比64bit的SSE2加法指令更快。