使用Intel内联汇编来编写带进位的大整数加法

Question

使用Intel内联汇编来编写带进位的大整数加法

3

我希望能够快速编写一个用于在大整数中添加 64 位数字的代码：

uint64_t ans[n];
uint64_t a[n], b[n]; // assume initialized values....
for (int i = 0; i < n; i++)
  ans[i] = a[i] + b[i];

但是上面的方法在进位时不起作用。

我在这里看到另一个问题，建议使用if语句来检查哪个更优雅：

ans[0] = a[0] + b[0];
int c = ans[0] < a[0];
for (int i = 0; i < n; i++) {
  ans[i] = a[i] + b[i] + c;
  c = ans[i] < a[i];
}

然而，我想学习如何嵌入内联（英特尔）汇编并更快地执行它。我确信有64位操作码相当于：

add eax, ebx
adc ...

但是我不知道如何从其他c++代码中向汇编程序传递参数。

- Dov

你正在使用哪个编译器？至少 MSVC 不支持 64 位内联汇编。 - Govind Parmar

考虑使用Intel Intrinsics。 - paddy

想一想，“c = ans[i] < (a[i] + c);”应该以与原设计同样优雅的方式解决这个问题，对吧？ - Ped7g

1

在Paddy的链接中查找 _addcarry_u64。 - Christopher Oicles

2

使用GMPlib。大整数库的设计和实现非常困难，因此不要重新发明轮子，使用现有的库即可。 - Basile Starynkevitch

显示剩余3条评论

2个回答

4

我不确定这是否是您要找的内容，我的汇编技能肯定不是最好的（例如缺乏后缀），但这使用了ADC，应该解决了您的问题。

请注意省略了C++循环；我们需要在asm中循环，因为我们需要CF在迭代之间保持不变。（GCC6具有输出约束标志，但没有输入约束标志；没有办法要求编译器将FLAGS从一个asm语句传递到另一个asm语句，即使有语法也可能会导致gcc通过setc/cmp低效地执行。）

#include <cstdint>
#include <iostream>

#define N 4

int main(int argc, char *argv[]) {

  uint64_t ans[N];
  const uint64_t a[N] = {UINT64_MAX, UINT64_MAX, 0, 0};
  const uint64_t b[N] = {2, 1, 3, 1};

  const uint64_t i = N;
  asm volatile (
      "xor %%eax, %%eax\n\t"      // i=0  and clear CF
      "mov %3, %%rdi\n\t"         // N

      ".L_loop:\n\t"

      "mov (%%rax,%1), %%rdx\n\t" // rdx = a[i]

      "adc (%%rax,%2), %%rdx\n\t" // rdx += b[i] + carry

      "mov %%rdx, (%%rax, %0)\n\t"// ans[i] = a[i] + b[i]

      "lea 8(%%rax), %%rax\n\t"   // i += 8 bytes

      "dec %%rdi\n\t"             // --i

      "jnz .L_loop\n\t"   // if (rdi == 0) goto .L_loop;
      : /* Outputs (none) */
      : /* Inputs */ "r" (ans), "r" (a), "r" (b), "r" (i)
      : /* Clobbered */ "%rax", "%rbx", "%rdx", "%rdi", "memory"
  );

  // SHOULD OUTPUT 1 1 4 1
  for (int i = 0; i < N; ++i)
    std::cout << ans[i] << std::endl;

  return 0;
}

为了避免设置进位标志（CF），我需要倒数到0以避免执行CMP指令。DEC不会设置进位标志，因此它可能是这个应用程序的完美选择。但是，我不知道如何使用%rdi从数组开头更快地进行索引，而不需要额外的指令和寄存器。

volatile和"memory"清除是必要的，因为我们只向编译器请求指针输入，并没有告诉它我们实际读写的内存。

在一些旧的CPU上，特别是Core2/Nehalem，inc后的adc会导致部分标志停顿。参见ADC/SBB和INC/DEC在某些CPU上紧密循环中的问题。但在现代CPU上，这非常高效。

编辑：正如@PeterCordes所指出的那样，我的inc %rax和使用lea缩放8倍是极其低效的（现在想想还很愚蠢）。现在，它只是lea 8（%rax），%rax。

编辑注：通过使用从数组末尾开始的负索引，我们可以使用更少的指令，向0计数并使用inc / jnz。

（这将在硬编码中将数组大小设置为4。您可以通过请求数组长度作为立即常量和-i作为输入来使其更加灵活。或者要求指向结尾的指针。）

// untested
  asm volatile (
      "mov   $-3, %[idx]\n\t"        // i=-3   (which we will scale by 8)

      "mov   (%[a]), %%rdx  \n\t"
      "add   (%[b]), %%rdx  \n\t"    // peel the first iteration so we don't have to zero CF first, and ADD is faster on some CPUs.
      "mov    %%rdx, (%0) \n\t"

      ".L_loop:\n\t"                        // do{
      "mov    8*4(%[a], %[idx], 8), %%rdx\n\t"   // rdx = a[i + len]
      "adc    8*4(%[b], %[idx], 8), %%rdx\n\t"   // rdx += b[i + len] + carry
      "mov    %%rdx,  8*4(%[ans], %[idx], 8)\n\t"  // ans[i] = rdx

      "inc    %[idx]\n\t"
      "jnz    .L_loop\n\t"                  // }while (++i);

      : /* Outputs, actually a read-write input */ [idx] "+&r" (i)
      : /* Inputs */ [ans] "r" (ans), [a] "r" (a), [b] "r" (b)
      : /* Clobbered */ "rdx", "memory"
  );

循环标签应该使用%%=，以防GCC复制此代码，或者使用像1：这样的编号本地标签。

使用缩放索引寻址模式不比我们之前使用的常规索引寻址模式（2个寄存器）更昂贵。理想情况下，我们将为adc或存储使用单寄存器寻址模式，可能相对于ans索引其他两个数组，通过在输入时减去指针。

但是，然后我们需要单独使用LEA增加8，因为我们仍然需要避免破坏CF。但是，在Haswell及更高版本中，索引存储无法使用端口7上的AGU，在Sandybridge/Ivybridge上，它们会取消层压到2个uops。因此，对于Intel SnB系列，在此处避免索引存储将是有益的，因为我们每次迭代需要2倍的加载+1倍的存储。请参见Micro fusion and addressing modes 早期的英特尔CPU（Core2 / Nehalem）在上述循环中将出现部分标志停顿，因此上述问题对它们来说是不相关的。

AMD CPU可能可以处理上述循环。Agner Fog的优化和微体系结构指南没有提到任何严重的问题。不过，对于AMD或英特尔来说，稍微展开一下也无妨。

- buhao

1

你需要一个 "memory" clobber 或虚拟的 "m" 输入和输出；编译器不会假设寄存器输入指向的内存也是输入或输出，因此可以在 asm 语句中移动对这些数组的读取或写入。此外，xor %eax,%eax 比 mov $0,%eax 单独使用更有效率地将 EAX 清零并设置 CF=0 (clc)。 - Peter Cordes

1

inc + lea 扩大 8 倍的效率不高；使用 lea 8(%%rcx), %%ecx 可以在不影响标志位的情况下增加 8。 - Peter Cordes

1

@PeterCordes 谢谢您的见解，我会更新我的答案以反映这一点。 - buhao

另一个减少循环开销的技巧是从数组末尾进行索引，即在循环之前使用 mov $-3, %rax。在循环内部，您可以使用 inc %rax / jnz，并使用缩放索引寻址模式，例如 (%0, %rax, 8)。您还可以通过位移来嵌入“数组末尾”这个东西，或者向编译器请求将数组末尾的指针作为输入。我会编辑您的答案，因为这比解释更容易。 - Peter Cordes

我可能应该把我的编辑放到一个单独的答案中；因为没有一种简单的最优解决方案适用于每个微架构，所以有很多要说的。 - Peter Cordes

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cody Gray · Accepted Answer

但是上述方法在进位时不起作用。

如果你的意思是GCC没有生成使用ADC指令的代码，那是因为其优化器已经确定有更优化的实现方式来执行加法。

这是我测试版的代码。我将数组提取为参数传递给函数，以便代码不能被省略，我们可以限制研究相关部分。

void Test(uint64_t* a, uint64_t* b, uint64_t* ans, int n)
{
    for (int i = 0; i < n; ++i)
    {
        ans[i] = a[i] + b[i];
    }
}

现在，如果您使用现代版本的GCC进行编译并查看反汇编代码, 您会看到一堆看起来很疯狂的代码。

Godbolt编译器浏览器非常有帮助，它会对C源代码和相应的汇编代码进行颜色编码（至少在优化代码中可能不完美，但在这里足够好了）。紫色代码是内部循环中实现64位加法的内容。GCC发出SSE2指令来执行加法。具体来说，您可以挑选MOVDQU（从内存中移动双倍四字节的未对齐数据到XMM寄存器）、PADDQ（对打包整数四字节进行加法运算）和MOVQ（将XMM寄存器中的四字节移动到内存）等指令。简单来说，对于非汇编专家，MOVDQU是如何加载64位整数值的，PADDQ执行加法，然后MOVQ存储结果。

这个输出特别嘈杂和混乱的一部分原因是GCC正在展开for循环。如果你禁用循环展开(-fno-tree-vectorize)，你会得到更容易阅读的输出，尽管它仍然使用相同的指令执行相同的操作。(好吧，大部分情况下。现在它到处都使用MOVQ来进行加载和存储，而不是用MOVDQU来加载。)

另一方面，如果你明确禁止编译器使用SSE2指令(-mno-sse2)，你会看到非常不同的输出。现在，因为它不能使用SSE2指令，所以它会发出基本的x86指令来进行64位加法操作——唯一的方法就是ADD+ADC。

我猜测这是您期望看到的代码。显然，GCC认为将操作向量化可以得到更快的代码，因此在使用-O2或-O3标志编译时会这样做。在-O1时，它始终使用ADD+ADC。这是少量指令不意味着更快代码的情况之一。（或者至少，GCC并不这么认为。实际代码上的基准测试可能会有不同的结果。在某些人为情况下，开销可能很大，但在现实世界中则无关紧要。）

就此而言，Clang在这里的行为方式与GCC非常相似。

如果你的意思是这段代码没有将前一次加法的结果传递到下一次加法中，那么你是正确的。你展示的第二个代码片段实现了这种算法，GCC使用ADC指令对其进行编译。

至少在x86-32目标平台上是这样。当目标平台为x86-64时，即使你有本地64位整数寄存器可用，也不需要"进位"，简单的ADD指令就足够了，需要的代码数量显著减少。事实上，这只是32位架构上的"大整数"算术，这也是我在所有前述分析和编译器输出中假定x86-32的原因。

在评论中，Ped7g想知道为什么编译器似乎没有ADD+ADC链式用法的概念。我不太确定他指的是什么，因为他没有分享任何尝试的输入代码示例，但正如我所展示的，编译器确实在这里使用了ADC指令。然而，编译器不会跨循环迭代链接进位。这在实践中太难实现，因为许多指令都会清除标志。手写汇编代码的人可能能够做到，但编译器不会。

（请注意，c应该是一个无符号整数，以鼓励某些优化。在这种情况下，它只是确保GCC在准备进行64位加法时使用XOR指令而不是CDQ。虽然速度稍快，但并没有非常大的改进，但在实际代码中可能会有所不同。）

另外，令人失望的是GCC无法在循环内部发出无分支代码以设置c。随着足够随机的输入值，分支预测将失败，您最终会得到相对低效的代码。几乎肯定有编写C源代码的方法可以说服GCC发出无分支代码，但那是完全不同的答案。

我想学习如何嵌入内联（intel）汇编并使其更快。但是，如果你天真地引发了一堆ADC指令，那么它可能不一定更快。除非你确信自己对性能的假设是正确的，否则不要手动优化！此外，内联汇编不仅难以编写、调试和维护，而且可能会使代码变慢，因为它会抑制某些编译器本来可以执行的优化。您需要能够证明，与编译器生成的代码相比，您手工编写的汇编代码在性能上具有足够显著的优势，这样这些考虑因素就变得不那么相关了。您还应该确认是否有办法通过更改标志或巧妙编写C源代码来让编译器生成接近理想输出的代码。

但是如果你真的想要, 你可以阅读各种在线教程，教你如何使用GCC的内联汇编。这是一个非常好的教程；还有很多其他的教程。当然，还有手册。所有这些都将解释{{link4：“扩展汇编”}}如何允许您指定输入操作数和输出操作数，这将回答您“如何从其余的C ++代码向汇编程序传递参数”的问题。

正如Paddy和Christopher Oicles建议的那样，您应该优先选择内置函数而不是内联汇编。不幸的是，没有内置函数会发出ADC指令。在这种情况下，内联汇编是您唯一的选择——或者，像我之前建议的那样，编写C源代码，以便编译器自行做正确的事情™。

虽然有 _addcarry_u32 和 _addcarry_u64 内置函数, 但是它们会导致ADCX或ADOX指令的发出。这些是“扩展”的ADC版本，可以生成更高效的代码。它们是Intel ADX指令集的一部分，引入了Broadwell微架构。在我看来，Broadwell市场渗透率还不够高，你不能简单地发出ADCX或ADOX指令并结束。许多用户仍然使用旧设备，支持他们尽可能地是符合你的利益的。如果你正在准备针对特定体系结构调整的构建，则它们非常好，但我不建议用于通用用途。

我确定存在64位操作码，相当于：add+adc 当你针对64位架构时，ADD和ADC（以及ADCX和ADOX）都有64位版本。这将允许您使用相同的模式实现128位“bigint”算术。

在x86-32上，基本指令集中没有这些指令的64位版本。您必须转向SSE2，就像我们看到的GCC和Clang一样。