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++ 代码传递给汇编程序。

4

2 回答 2

4

但以上不适用于携带。

如果您的意思是 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 相信向量化操作会导致更快的代码，所以当您使用-O2or-O3标志进行编译时，它就是这样做的。在-O1，它总是使用ADD+ ADC。这是指令越少并不意味着代码越快的情况之一。（或者至少，GCC 不这么认为。实际代码的基准测试可能会讲述一个不同的故事。在某些人为的场景中开销可能很大，但在现实世界中无关紧要。）

对于它的价值，Clang 的行为方式与 GCC 在这里的行为方式非常相似。

如果您的意思是这段代码不会将前一个加法的结果传递给下一个加法，那么您是对的。您展示的第二段代码实现了该算法，GCC 确实使用ADC指令编译了它。

至少，它在针对 x86-32 时是这样。当以 x86-64 为目标时，您可以使用本机 64 位整数寄存器，甚至不需要“携带”；简单ADD的指令就足够了，需要的代码要少得多。事实上，这只是 32 位架构上的“bigint”算法，这就是为什么我在前面的所有分析和编译器输出中都假设 x86-32。

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

（请注意，它c可能应该是一个无符号整数以鼓励某些优化。在这种情况下，它只是确保 GCCXOR在准备进行 64 位加法时使用指令而不是CDQ. 虽然稍微快一点，但不是很大的改进，但里程可能因实际代码而异。）

（此外，令人失望的是 GCC 无法发出无分支代码以c在循环内部进行设置。如果输入值足够随机，分支预测将失败，并且您最终会得到相对低效的代码。几乎可以肯定，编写说服 GCC 发出无分支代码的 C 源代码，但这是一个完全不同的答案。）

我想学习如何嵌入内联（英特尔）汇编并做得更快。

ADC好吧，我们已经看到，如果您天真地发出一堆指令，它可能不一定会更快。除非您确信您对性能的假设是正确的，否则不要手动优化！

此外，内联汇编不仅难以编写、调试和维护，而且甚至可能使您的代码变慢，因为它抑制了某些本来可以由编译器完成的优化。您需要能够证明您的手工编码程序集在性能上足以胜过编译器生成的内容，这些考虑因素变得不那么相关了。您还应该确认没有办法让编译器生成接近理想输出的代码，无论是通过更改标志还是巧妙地编写 C 源代码。

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

正如 paddy 和 Christopher Oicles 所建议的那样，您应该更喜欢内部函数而不是内联汇编。不幸的是，没有内在函数会导致ADC发出指令。内联汇编是你唯一的办法——或者我已经建议编写 C 源代码，以便编译器自己做 Right Thing™。

不过，有_addcarry_u32和_addcarry_u64内在函数。这些原因ADCX或ADOX指令被发出。这些是ADC可以生成更高效代码的“扩展”版本。它们是英特尔 ADX 指令集的一部分，随 Broadwell 微架构引入。在我看来，Broadwell 没有足够高的市场渗透率，您可以简单地发出ADCX或ADOX指示并收工。许多用户仍然拥有旧机器，尽可能支持它们符合您的利益。如果您正在准备针对特定架构调整的构建，它们会很棒，但我不建议将其用于一般用途。

我确信有 64 位操作码，相当于：add+adc

当您以 64 位架构为目标时，有 64 位版本的ADDand ADC（和ADCXand ）。ADOX这将允许您使用相同的模式实现 128 位“bigint”算术。

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

于 2016-12-09T13:10:14.887 回答
4

我不完全确定这是否是您要找的东西，而且我的组装技能绝对不是最好的（例如缺少后缀），但这使用ADC并且应该可以解决您的问题。

注意 C++ for 循环的省略；我们需要在 asm 中循环，因为我们需要CF在迭代中生存下来。（GCC6 有标志输出约束，但没有标志输入；没有办法要求编译器将 FLAGS 从一个 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;
}

为了避免设置carry flag (CF)，我需要倒计时到 0 以避免做CMP. DEC不设置carry flag，因此它可能是此应用程序的完美竞争者。但是，我不知道如何使用%rdi比inc %rax.

volatile和clobber 是必要的"memory"，因为我们只向编译器询问指针输入，而不告诉它我们实际读取和写入的内存。

在某些较旧的 CPU 上，尤其是 Core2 / Nehalem，adc之后inc会导致部分标志停止。请参阅某些 CPU 上紧密循环中的 ADC/SBB 和 INC/DEC 问题。但在现代 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理想情况下，我们会为 the或 store使用单寄存器寻址模式，可能ans通过减去输入上的指针来相对于 索引其他两个数组。

但是我们需要一个单独的 LEA 来增加 8，因为我们仍然需要避免破坏 CF。尽管如此，在 Haswell 和更高版本上，索引商店不能在端口 7 上使用 AGU，而 Sandybridge/Ivybridge 它们未层压到 2 微秒。因此，对于英特尔 SnB 系列，在此处避免索引存储会很好，因为每次迭代我们需要 2x 加载 + 1x 存储。请参阅微融合和寻址模式

早期的 Intel CPU (Core2 / Nehalem) 在上述循环中会出现部分标志停顿，因此上述问题与它们无关。

AMD CPU 可能对上述循环没问题。 Agner Fog 的优化和微架构指南没有提到任何严重的问题。

不过，对于 AMD 或英特尔来说，展开一点不会有什么坏处。

于 2019-05-27T06:36:40.203 回答