加速x64汇编ADD循环

Question

我正在处理非常长整数的乘法算术问题（约100,000个十进制数字）。作为我的库的一部分，我需要添加两个长数字。

性能测试显示，我的代码运行时间中有多达25％用于add()和sub()例程，因此它们尽可能快是很重要的。但是我还没有看到太多潜力。也许你可以给我一些帮助、建议、见解或想法。我会测试它们并回复你。

到目前为止，我的加法例程做了一些设置，然后使用了8次展开的循环：

mov rax, QWORD PTR [rdx+r11*8-64]
mov r10, QWORD PTR [r8+r11*8-64]
adc rax, r10
mov QWORD PTR [rcx+r11*8-64], rax

接下来还有7个不同偏移的块，然后进入循环。

我之前尝试过从内存中加载值，但没有帮助。我猜这是因为良好的预取。我使用的是英特尔i7-3770 Ivy Bridge 4核CPU。但我想编写适用于任何现代CPU的代码。

编辑：我做了一些计时：它大约需要2.25个周期/单词添加1k个字。如果我删除ADC，只剩下MOV，仍然需要大约1.95个周期/单词。因此，主要瓶颈似乎是内存访问。一个库memcpy()大约在0.65个周期/单词内工作，但只有一个输入，而不是两个。尽管如此，由于其使用SSE寄存器，它要快得多，我想。

一些问题：

• 使用“加载、加载、加、存储”结构是否有用，还是“加载、加到内存”有帮助？到目前为止，我的测试没有显示出任何优点。
• 通常情况下，不应期望从SSE（2,3,4）获得帮助吗？
• 地址计算（比例指数加基地址加偏移量）会产生严重影响吗？我可以使用ADD r11, 8代替。
• 关于循环展开怎么样？我读到循环展开对Sandy Bridge架构不利（Agner Foghttp://www.agner.org/optimize/）。是应该优选还是应该避免？
• （编辑）我可以使用SSE寄存器从内存中加载和存储单词并高效地在通用寄存器和SSE寄存器之间交换单词吗？

非常感谢任何评论。

- cxxl

---

我所知道的最快乘法大数的方法是快速傅里叶变换。http://en.wikipedia.org/wiki/Multiplication_algorithm 我从未尝试过在汇编中实现它的逻辑。显然，Prime95包含了x86汇编逻辑的快速傅里叶变换，你可以从那里（免费）获取。 - Benjamin Gruenbaum

谢谢，我知道那个。现在我只想要添加快速。 - cxxl

你可以查看GMP源代码。 - zch

尝试运行IACA，看看它是否提供有用的输出：http://software.intel.com/en-us/articles/intel-architecture-code-analyzer - Necrolis

IACA 看起来很酷，但文档最多只是简略的介绍。我需要花更多时间去理解它。有什么资源可以提供吗？ - cxxl

Answer 1

我相信memcpy更快，因为它在执行下一个操作之前不需要等待数据的获取。如果您可以安排您的代码让它像这样做：

mov rax, QWORD PTR [rdx+r11*8-64]
mov rbx, QWORD PTR [rdx+r11*8-56]
mov r10, QWORD PTR [r8+r11*8-64]
mov r12, QWORD PTR [r8+r11*8-56]
adc rax, r10
adc rbx, r12
mov QWORD PTR [rcx+r11*8-64], rax
mov QWORD PTR [rcx+r11*8-56], rbx

我不能完全确定-56的偏移量是否适用于您的代码，但是概念“正确”。此外，我建议考虑缓存命中/冲突。例如，如果您有三个数据块[似乎确实如此]，请确保它们不对齐到缓存中的相同偏移量。一个不好的例子是如果您将所有块都分配在缓存大小的倍数处，从缓存中的同一位置开始。为了过度分配并确保您的不同数据块至少偏移512字节[因此超额分配4K，并将其舍入到4K边界开始地址，然后将第二个缓冲区添加512，第三个缓冲区添加1024]。

如果您的数据足够大（大于L2缓存），则可能需要使用MOVNT来获取/存储您的数据。这将避免读入缓存 - 这仅在具有非常大的数据时才有益，其中下一个读取将只是导致您可能会发现“有用”的其他东西被踢出缓存，并且您在将其踢出之前无法再次访问它 - 因此将值存储在缓存中实际上并没有帮助...

编辑：使用SSE或类似方法无法帮助，如此涵盖： Can long integer routines benefit from SSE?

- Mats Petersson

Answer 2

最困难的依赖关系是在每个内存块之间传播进位；我会先尝试制定一种处理这个问题的方法。

以下片段模拟了进位传播，但“好处”是不使用进位标志。可以将其并行化为三到四个单独的线程，每个线程产生大约25000十进制数字（或10000字节）左右的半进位。然后，这些进位只影响一个字节、字、双字等的概率将渐近地趋近于零。

 long long carry=0;
 for (int i=0;i<N;i++) {
     carry += (long long)*a++ + (long long)*b++;
     *c++ = carry; carry>>=32;
 }

根据我的分析，使用xmm进行无进位加法需要约550毫秒（10亿个单词），模拟进位需要约1020毫秒，4路并行化版本则需约820毫秒（没有任何汇编优化）。

架构优化可能包括使用冗余数字系统，其中进位不必一直传递，并且可以将进位的评估推迟到几乎无限期。

- Aki Suihkonen

Answer 3

尝试先预取数据（您可以尝试先读取更多的数据块到x64寄存器中，然后再进行计算），检查数据在内存中是否对齐，将循环代码放置在标签对齐到16处，尝试删除SIB寻址。

您还可以尝试缩短您的代码：

mov rax, QWORD PTR [rdx+r11*8-64]
adc rax, QWORD PTR [r8+r11*8-64]
mov QWORD PTR [rcx+r11*8-64], rax

- Bartosz Wójcik

---

我尝试了所有的方法，但没有得到任何好处，有时甚至会更糟。主要时间似乎都浪费在内存访问上了。 - cxxl