條件控制與條件傳送詳解

提要

CSAPP3e中文譯本 3.6.5 用條件控制來實現(xiàn)條件分支 3.6.6 用條件傳送來實現(xiàn)條件分支

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

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

用控制的條件轉(zhuǎn)移實現(xiàn)（結(jié)合有條件和無條件跳轉(zhuǎn)）

用數(shù)據(jù)的條件轉(zhuǎn)移實現(xiàn)

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

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

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

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

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

條件控制

要實現(xiàn)算兩個整型值的差的絕對值，我想大多數(shù)人的第一反應(yīng)是以下程序：

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

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

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

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代碼結(jié)構(gòu)進行了編譯，比較兩個寄存器中的參數(shù)值，然后返回較大的值減去較小的值的結(jié)果。將這種條件控制的條件分支實現(xiàn)形式用C語法來表達應(yīng)該是這樣的：

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，因為它會是的程序非常難以閱讀和調(diào)試，還容易出錯。我們這里使用goto是為了模擬匯編中的JMP類指令的行為。看到這里，想必讀者應(yīng)該能明白上面所謂的結(jié)合有條件和無條件跳轉(zhuǎn)是什么意思了，在匯編語言中，需要結(jié)合有條件和無條件跳轉(zhuǎn)，才能利用JMP類命令實現(xiàn)在兩個分支（then-statement和else-statement）中必有一個被執(zhí)行。

條件傳送

上述函數(shù)的條件傳送的實現(xiàn)形式如下：

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

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

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代碼結(jié)構(gòu)。

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

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

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

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

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

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

原理

以下內(nèi)容摘自CSAPP3e中文譯本 Page 146

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

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

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

條件傳送并不總是可行的

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

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

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

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

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

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

__bulitin_expect

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

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

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

總結(jié)

以上是生活随笔為你收集整理的条件控制与条件传送详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。