采用英特尔内联汇编编写BIGINT带有进

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]; 
} 

不过，我想学习如何嵌入内联（英特尔）组装做得更快。 我相信有64位操作码，相当于：

add eax, ebx 
adc ... 

，但我不知道如何从参数的C++代码的其余部分传递给汇编。

Answer 1

但上面的方法不适用于进位。

如果你的意思是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位加法的代码。海湾合作委员会正在发布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认为向量化操作会产生更快的代码，所以这是使用-O2或-O3标志进行编译时的功能。在-O1，它总是使用ADD + ADC。这是其中较少的指令并不意味着代码更快的情况之一。 （或者至少，GCC不这么认为，实际代码的基准可能会说明不同的情况，在某些人为设想的情况下开销可能很大，但在现实世界中无关紧要。）

对于它的价值，Clang的行为与海湾合作委员会在这里所做的非常类似。

---

如果你的意思是说这段代码没有把前面的结果加到下一个加法中，那么你是对的。你已经显示的代码的第二个片段实现了该算法，并且GCC does compile this using the ADC instruction。

至少，它的目标是x86-32。当针对x86-64，你有本地64位整数寄存器可用，没有“携带”甚至是必要的; simple ADD instructions are sufficient，要求显着较少的代码。实际上，这只是32位体系结构中的“bigint”算术，这就是为什么我在所有上述分析和编译器输出中都假定x86-32的原因。

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

（注意c也许应该是一个无符号整数鼓励某些优化。在这种情况下，它只是确保GCC使用准备做一个64位加法，而不是CDQ当XOR指令。虽然略更快，而不是一个巨大改善，但里程可能与真正的代码会有所不同。）

（此外，这是令人失望的是GCC是无法发出网点代码设置c环路内。随着足够随机的输入值，分支预测将会失败，并且最终会导致相对低效的代码。几乎可以肯定编写C源说服GCC发出网点代码的LY的方式，但是这是一个完全不同的答案。）

---

我想了解如何嵌入内联（英特尔）组装做得更快。

好吧，我们已经看到，如果您天真地导致一堆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指令并称之为一天。 用户仍然拥有较旧机器的批次为，并且尽可能为用户提供支持符合您的兴趣。如果您准备针对特定体系结构调整构建，它们非常棒，但我不推荐将其用于一般用途。

---

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

还有的ADD和ADC（和ADCX和ADOX）64位版本，当你”重新定位64位体系结构。这将允许您使用相同的模式实现128位“bigint”算术。

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