條件控制與條件傳送詳解

提要

CSAPP3e中文譯本 3.6.5 用條件控制來實現條件分支 3.6.6 用條件傳送來實現條件分支

CSAPP3e第三章前面主要是介紹了機器級代碼的二進制形式和匯編形式、反匯編、x86匯編的基礎指令、條件碼及其訪問方式等。

在介紹到匯編語言的條件分支時分了兩小節（3.6.5，3.6.6）分別介紹實現條件分支的兩種形式：

1. 用控制的條件轉移實現（結合有條件和無條件跳轉）
2. 用數據的條件轉移實現

并對這兩種方式的適用場景，哪種在哪些場景下效率更高進行了說明，以及一些可能會造成的錯誤。

筆者在這里要首先指出的是，如果使用C語言編程遇到條件分支（當時幾乎是肯定會遇到啦^^），大可以直接按照我們熟悉的if-else模板編寫代碼即可，

if (test-expr){then-statement;
}
else{else-statement;
}

無論我們的C語言代碼是按照哪種方式編寫的，聰明的編譯器會在保證安全的前提下自動優化條件分支的實現方式，將我們的C代碼用最合適的分支方式編譯為匯編代碼。本文內容是為了從機器級代碼匯編和現代CPU工作原理的層次，來幫助理解分支程序的性能，也反過來更好地理解現代計算機系統的工作原理。

以下筆者以計算兩個整型值的差的絕對值的程序為例，分析條件控制和條件傳送的區別和關系。

條件控制

要實現算兩個整型值的差的絕對值，我想大多數人的第一反應是以下程序：

int abs_diff(int x, int y)
{if(x < y)return y - x;elsereturn x - y;
}

先判斷兩個值哪個較大，然后用較大的減較小的，這個代碼完全沒有問題，這種條件分支的實現形式稱為條件控制。

然后我們來編譯以下這個代碼gcc -Og -S abs_diff.c -o abs_diff.s，注意這里的-Og參數是關閉編譯器的自動優化，使得編譯器忠實地編譯我們的C代碼。這里筆者把abs_diff.s文件的關鍵部分復制出來：

abs_diff:
.LFB0:.cfi_startproccmpl	%esi, %edijl	.L4movl	%edi, %eaxsubl	%esi, %eaxret
.L4:movl	%esi, %eaxsubl	%edi, %eaxret.cfi_endproc

筆者注：可以認為x保存在寄存器%edi中，y保存在寄存器%esi中。

可以看到，編譯器確實忠實地按照我們編寫的C代碼結構進行了編譯，比較兩個寄存器中的參數值，然后返回較大的值減去較小的值的結果。將這種條件控制的條件分支實現形式用C語法來表達應該是這樣的：

int goto_absdiff(int x, int y){if (x > y){goto x_ge_y;}return y - x;x_ge_y:return x - y;
}

當然，所有C語言老師都會要求大家不要使用goto，因為它會是的程序非常難以閱讀和調試，還容易出錯。我們這里使用goto是為了模擬匯編中的JMP類指令的行為。看到這里，想必讀者應該能明白上面所謂的結合有條件和無條件跳轉是什么意思了，在匯編語言中，需要結合有條件和無條件跳轉，才能利用JMP類命令實現在兩個分支（then-statement和else-statement）中必有一個被執行。

條件傳送

上述函數的條件傳送的實現形式如下：

int abs_diff(int x, int y){int result_0 = x - y;int result_1 = y - x;if (x < y){return result_1;}else{return result_0;}
}

可以看到，條件傳送的分支實現方式是先將兩種分支的值都算出來，然后再比較哪個參數較大，返回對應的結果。編譯上述代碼gcc -Og -S abs_diff_1.c -o abs_diff_1.s，得到的關鍵匯編代碼如下：

abs_diff:
.LFB0:.cfi_startprocmovl	%edi, %eaxsubl	%esi, %eaxmovl	%esi, %edxsubl	%edi, %edxcmpl	%esi, %edijl	.L3
.L1:rep ret
.L3:movl	%edx, %eaxjmp	.L1.cfi_endproc

沒有問題，編譯器同樣忠實地編譯了我們的C代碼結構。

那么，這兩種條件分支的實現方式到底有什么區別呢？為什么說在保證隨機輸入的情況下，第二種的運行速度是比第一種要快的。

條件控制和條件分支的效率

我們放開編譯器的優化選項，即讓編譯器自己去優化我們的C代碼，來編譯第一種實現方式條件控制。

gcc -S -O1 abs_diff.c -o abs_diff_opt.s，注意這里開啟O1級別的編譯器優化-O1。得到的abs_diff_opt.s的關鍵匯編代碼如下：

abs_diff:
.LFB0:.cfi_startprocmovl	%esi, %edxsubl	%edi, %edxmovl	%edi, %eaxsubl	%esi, %eaxcmpl	%esi, %edicmovl	%edx, %eaxret.cfi_endproc

大家可以對比一下上面條件傳送中得到的匯編代碼，幾乎是一樣的。所以說，在編譯器優化之后，這段匯編代碼實際上執行的是條件傳送的條件分支實現方式。也就是說，編譯器認為，在保證安全的前提下，這段代碼使用條件傳送來實現比使用條件控制來實現要更加高效。

原理

以下內容摘自CSAPP3e中文譯本 Page 146

為了理解為什么基于條件數據傳送的代碼會比基于條件控制轉移的代碼性能要好，我們必須了解一些關于現代處理器如何運行的知識。正如我們在第4章和第5章中看到的，處理器通過流水線（pipelining）來獲得高性能，在流水線中，一條指令的處理要經過一些列的階段，每個階段執行所需操作的一小部分（例如，從內存取指令，確定指令類型，從內存讀數據，執行算術運算，向內存寫數據，以及更新程序計數器）。這種方法通過重疊連續指令的步驟來獲得高性能，例如，在取一條命令的同時，執行它前面一條指令的算術運算。要做到這一點，要求能夠事先確定要執行的指令序列，這樣才能保持流水線中充滿了待執行的指令。當機器要到條件跳轉（也稱為“分支”）時，只有當分支條件求值完成后，才能決定分支往哪邊走，處理器采用非常精密的分支預測邏輯來猜測每條跳轉指令是否會執行。只要它的猜測還比較可靠（現代微處理器設計試圖達到90%以上的成功率），指令流水線就會充滿著指令。另一方面，錯誤預測一個跳轉，要求處理器丟掉它為該跳轉指令后所有指令已做的工作，然后再開始從正確位置其實的指令取填充流水線，正如我們會看到的，這樣一個錯誤預測會招致很嚴重的處罰，浪費大約15~30個時鐘周期，導致程序性能嚴重下降。

可以看到，當輸入比較隨機的情況下，CPU是很難在條件控制方式下精準地預測哪條分支會被執行的，而錯誤預測將付出高昂的代價（原書中有具體的錯誤預測代價計算方式，有興趣可自查），這時，我們通過條件傳送的實現方式，則會獲得相對更優、更穩定的性能。

條件傳送相當于把原本可能浪費在跳轉的時間用在了計算另外一條分支上，所獲得的性能提升取決于跳轉所浪費的時間和計算另外一條分支的時間對比。不過從另一點來看，由于只有最后返回之前才進行條件的判斷，條件傳送更有利于流水線一直處于滿的狀態，運行時間更加穩定。

條件傳送并不總是可行的

那有人可能就要問了，既然如此，我們把所有條件分支都實現為條件傳送的方式豈不是最優，那還要條件控制的方式做什么呢？事實上恰恰相反，條件傳送的可行情況是十分受限的，大部分情況下，編譯器會將條件分支實現為條件控制的形式。比如下面這個C程序（同樣來CSAPP）：

long cread(long *xp){return (xp ? *xp : 0);
}

當指針結果為空時返回0，否則返回指針所指向的值。貌似很適合實現為條件傳送：

cread:movq (%rdi), %raxtestq %rdi, %rdimovl $0, %edxcmov %rdx, %raxret

但實際上這個實現是非法的，因為即使當測試為假時，movq指令對xp的見解引用還是發生了，這將導致一個間接引用空指針的錯誤。所以，必須用條件控制分支方式來編譯這段C代碼。

使用條件傳送指令，也不總是會提高代碼的效率。因為畢竟要先計算出then-statemnt和else-statement的結果，如果這些計算比較復雜，而最終有沒有被執行，那很多計算就被白費了。因此，編譯器必須考慮浪費的計算和由于分支預測錯誤所早晨改的性能處罰之間的相對性能。根據CSAPP原書的說明，只有當兩個表達式都是很容易的計算時，例如都只是一條加法指令，編譯器才會使用條件傳送，而通常情況下，即使許多分支預測錯誤的開銷會超過更復雜的計算，編譯器還是會使用條件控制轉移。筆者理解，編譯器還是相對比較保守的。

__bulitin_expect

最后再說明一下，本文內容是為了從機器級代碼匯編和現代CPU工作原理的層次，來幫助理解分支程序的性能，也反過來更好地理解現代計算機系統的工作原理。而在日常的代碼編寫中，按照正常的邏輯來編寫程序即可，即使有優化的需求，現代編譯器都會幫你進行優化。

當然，如果你非常確定哪一條分支大概率會被執行，你也可以通過\_\_builtin_except來告訴編譯器。使用\_\_bulitin_expect這個宏來告訴編譯器這個if更有可能會選擇哪一個分支，從而讓編譯器生成出跳轉可能比較小的匯編代碼。

Ref:

https://blog.csdn.net/qq_33113661/article/details/90750145?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163081410616780366559662%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=163081410616780366559662&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_allsobaiduend~default-1-90750145.pc_search_insert_download&utm_term=%E6%9D%A1%E4%BB%B6%E6%8E%A7%E5%88%B6%EF%BC%8C%E6%9D%A1%E4%BB%B6%E4%BC%A0%E9%80%81%E4%B8%8E__builtin_expect&spm=1018.2226.3001.4187

CSAPP3e