採用英特爾內聯彙編編寫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一樣。