c++ - 使用inline内联汇编器对带有进位的bigint add进行编码

Question

我想做一个快速代码，以大整数形式添加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];
}

但是，我想学习如何嵌入内联(intel)程序集并更快地完成它。
我确定有64位操作码，相当于:

add eax, ebx
adc ...

但是我不知道如何从其余的c++代码中将参数传递给汇编器。

Answer 1

but the above does not work with carry.

如果您的意思是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和 look at the disassembly进行编译时，您会看到一堆看上去很疯狂的代码。

Godbolt编译器资源管理器非常有用，它可以对C源代码行及其相应的汇编代码进行颜色编码(或者至少要尽其最大能力这样做；这在优化的代码中并不完美，但是效果很好这里)。紫色代码是在循环内部实现64位加法的原因。 GCC发出SSE2指令进行加法运算。具体来说，您可以选择 MOVDQU (将双四字从内存中不对齐地移到XMM寄存器中)， PADDQ (将双四字从压缩整数中移出)和 MOVQ (将四字从XMM寄存器中移到内存中) )。粗略地说，对于非汇编专家来说， MOVDQU是它加载64位整数值的方式， PADDQ执行加法，然后 MOVQ存储结果。

使此输出特别嘈杂和令人困惑的部分原因在于，GCC正在展开 for循环。如果禁用循环展开( -fno-tree-vectorize)，则会得到 output that is easier to read，尽管它仍使用相同的指令执行相同的操作。 (嗯，主要是。现在，它在各处都使用 MOVQ进行加载和存储，而不是使用 MOVDQU进行加载。)

另一方面，如果您明确禁止编译器使用SSE2指令( -mno-sse2)，则为 you see output that is significantly different。现在，由于它不能使用SSE2指令，因此它发出基本的x86指令来执行64位加法，而唯一的方法是 ADD + ADC。

我怀疑这是您期望看到的代码。显然，GCC相信对 vector 进行 vector 处理可以加快代码的速度，因此，这就是使用 -O2或 -O3标志进行编译时所做的事情。在 -O1处，它始终使用 ADD + ADC。这是其中更少的指令并不意味着更快的代码的情况之一。 (或者至少，GCC并不这么认为。实际代码的基准可能会讲一个不同的故事。在某些人为设计的场景中，开销可能会很大，而在现实世界中则无关紧要。)

就其值(value)而言，Clang的行为与GCC的行为非常相似。

如果您的意思是该代码没有将上一个加法的结果转移到下一个加法的结果，那么您是对的。您显示的第二段代码实现了该算法 GCC does compile this using the ADC instruction。

至少在以x86-32为目标时确实如此。在面向x86-64的情况下，如果您具有可用的 native 64位整数寄存器，则甚至不需要“携带”。 simple ADD instructions are sufficient，需要更少的代码。实际上，这只是32位体系结构上的“bigint”算法，这就是为什么我在所有上述分析和编译器输出中都假定使用x86-32的原因。

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

(请注意 c可能应该是一个无符号整数，以鼓励某些优化。在这种情况下，它只是确保GCC在准备进行64位加法而不是 XOR时使用 CDQ指令。尽管速度稍快，但并没有太大的改进，但里程可能会因实际代码而异。)

(同样，令人失望的是，GCC无法发出用于在循环内设置 c的无分支代码。如果输入值足够随机，则分支预测将失败，最终您将获得效率相对较低的代码。几乎可以肯定，有几种编写方法C语言说服GCC发出无分支代码，但这是一个完全不同的答案。)

I would like to learn how to embed inline (intel) assembly and do it faster.

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

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

但是 if you really wanted to，您可以阅读各种在线教程，这些教程可以教您如何使用GCC的内联汇编器。 This is a pretty good one;还有很多其他的。当然，还有 the manual。所有人都将说明 "extended asm"如何允许您指定输入操作数和输出操作数，这将回答您的问题“如何从其余的c++代码将参数传递给汇编器”。

正如paddy和Christopher Oicles所建议的那样，您应该更喜欢内部函数而不是内联汇编。不幸的是，没有任何内在因素导致 ADC指令被发出。内联汇编是您唯一的选择–或者，我已经建议编写C源代码，以便编译器自己执行Right Thing™。

虽然有 _addcarry_u32 and _addcarry_u64 intrinsics。这些导致 ADCX或 ADOX指令被发出。 These are "extended" versions of ADC that can produce more efficient code.它们是随Broadwell微体系结构引入的Intel ADX指令集的一部分。我认为，Broadwell没有足够高的市场渗透率，您仅可以发出 ADCX或 ADOX指令并将其命名为“day”即可。许多用户仍然拥有较旧的计算机，因此，尽可能地支持它们符合您的利益。如果您要准备针对特定体系结构进行了调整的构建，那么它们很棒，但是我不建议将其用于一般用途。

I am sure there are 64 bit opcodes, the equivalent of: add+adc

当您针对64位体系结构时，存在 ADD和 ADC(以及 ADCX和 ADOX)的64位版本。然后，这将允许您使用相同的模式实现128位的“bigint”算法。

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