對編譯、鏈接、OS內核、性能優(yōu)化等技術感興趣的童鞋，不妨右上角關注一下吧，近期會持續(xù)更新相關方面的專題文章！
昨天發(fā)了一個文章《簡歷上寫精通C語言？有道C語言的題來做一下吧》，引來很多童鞋圍觀。很多童鞋表示不太明白，于是就有了這篇文章，詳細解釋下這個題目的來龍去脈。
題目如下圖所示（對原題目做了少許改動）：
如果你是第一次看到的話，不妨試一下，看你能得出正確答案嗎？
其實，這個題目還是源自大師之手，我只是做了少許修改。先來聊一下這段歷史淵源吧。
注：為了盡量解釋清楚，篇幅有點長，請耐心讀完，相信你會有收獲的！
1983年11月，一位叫Tom Duff的大牛在編寫串口通信程序時，發(fā)現(xiàn)使用一般的寫法時，性能總是不能讓人滿意。后來，這位老兄憑借深厚的編程功底和精湛的C語言技巧，利用C語言中switch語句的一個鮮為人知的特性，發(fā)明如了下圖所示的經(jīng)典代碼：
結果，引來無數(shù)吃瓜群眾膜拜。在此之前，還沒有人發(fā)現(xiàn)并利用過C語言的這個特性，于是他便以自己的名字命名這段代碼，叫做Duff's Device，一般譯為“達夫機器”。
先來看一下大牛的風采吧：
下面來講解一下這段代碼吧。
當時Duff的需求是把一段起始地址為from，長度為count的數(shù)據(jù)，寫入到一個內存映射的I/O（Memory Mapped I/O ）寄存器to中。
最簡單的實現(xiàn)
需求很簡單，對吧？很容易想到直接用for或者while循環(huán)就可以解決了，如下圖所示：
代碼清晰簡潔，很直觀，對吧？
Duff卻對此很不滿意，因為他覺得這種寫法雖然簡單，但太過低效，無法接受。
那么，為什么如此簡單的代碼，卻說它性能低下呢？其實主要有兩個問題：
我們來分析一下。
所謂無用指令，是指不直接對所期望的結果產(chǎn)生影響的指令。
對于這段代碼，我們期望的結果就是把數(shù)據(jù)都拷貝到I/O寄存器to中。那么對于這個期望的結果來說，真正有用的代碼，其實只有中間那一行賦值操作：
*to = *from++;而每次迭代過程中的while (--count > 0)產(chǎn)生的指令，以及每次迭代結束后的跳轉指令，對結果來說都是無用指令。
上面最簡單的實現(xiàn)中，每次循環(huán)迭代只拷貝一個字節(jié)數(shù)據(jù)。這就意味著，有多少個字節(jié)的數(shù)據(jù)，就需要執(zhí)行多少次跳轉和條件判斷，以及--count的操作。
我們看一下匯編代碼：
有些童鞋對匯編不太熟悉，我簡單講解一下：
所以，第9~19行屬于熱點路徑，也就是主循環(huán)體。第9~14行屬于有效指令，第15~19行對于期望的數(shù)據(jù)結果來說就是無用指令。
我們看到，熱點路徑中，無用指令數(shù)占了整個熱點路徑指令數(shù)的一半，其開銷也占到整個函數(shù)的50%！
現(xiàn)代CPU為了提高指令執(zhí)行的速度和吞吐率，提升系統(tǒng)性能，不僅一直致力于提升CPU的主頻，還實現(xiàn)了多種ILP(Instruction-Level Parallelism 指令級并行)技術，如超流水線、超標量、亂序執(zhí)行、推測執(zhí)行、分支預測等。
一個設計合理的程序，往往能夠充分利用CPU的這些ILP機制，以使性能達到最優(yōu)。
但是，在代碼熱點路徑上，分支指令太多，導致程序運行中產(chǎn)生大量指令流水線停頓，無法充分發(fā)揮ILP的技術優(yōu)勢，從而導致巨大的性能優(yōu)勢。
注：由于ILP涉及到很底層的CPU硬件知識，很多童鞋可能不熟悉，要講清楚的話，需要花費大量篇幅。而且，很多童鞋可能也不會有耐心去看，所以這里就暫時先不展開了。
但是，了解一些ILP的知識，對于進行系統(tǒng)性的性能優(yōu)化大有裨益。而且，要想真正理解并掌握如perf這樣的性能測量工具，ILP更是必須要掌握的知識。
因此，后續(xù)我會更新專題文章進行講解這方面的知識，有興趣的童鞋可以關注一下。
現(xiàn)在，我們知道上面那個簡單實現(xiàn)性能低下的原因了，那么如何去優(yōu)化它呢？這就需要用到循環(huán)展開的優(yōu)化手段了。
循環(huán)展開
所謂循環(huán)展開，是通過增加每次迭代內數(shù)據(jù)操作的次數(shù)，來減小迭代次數(shù)，甚至徹底消除循環(huán)迭代的一種優(yōu)化手段。
循環(huán)展開，有以下優(yōu)點：
循環(huán)展開是一個很常用的性能優(yōu)化手段。幾乎所有的現(xiàn)代編譯器，在編譯代碼時，都會嘗試進行循環(huán)展開優(yōu)化。
有童鞋可能會好奇，循環(huán)展開到底能提升多少性能呢？我們還是用數(shù)據(jù)說話，看一個實例吧。
實例 - 循環(huán)展開對性能的影響
測試環(huán)境：
測試代碼：
loop1.c和loop2.c做的事情一樣，唯一的區(qū)別是：
編譯：
測試結果：
做同樣的事情，通過循環(huán)展開優(yōu)化，所消耗時間直接從25.4秒降到了14.7秒，提升了42.4%！
第一次優(yōu)化嘗試
了解了循環(huán)展開對性能提升的好處之后，我們就可以對上面的簡單實現(xiàn)進行第一次優(yōu)化嘗試了。
我們先嘗試把每次循環(huán)內拷貝字節(jié)的個數(shù)，由1個提高到到8個，這樣就可以把迭代次數(shù)降低8倍。
我們先假設，send()函數(shù)的參數(shù)count總是8的倍數(shù)，那么上面的代碼就可以修改為：
上面的代碼很好理解，就是把原來迭代里的操作復制了8次，然后把迭代次數(shù)降低到了8倍。
但是，我們前面做了一個假設，就是count是8的倍數(shù)。那如果不是8的整數(shù)倍呢，比如20？那我們可能會想到這樣的實現(xiàn)：
其實，到了這里，相比原始的實現(xiàn)來說，性能已經(jīng)能提升了不少了。但是，Duff仍然不滿意，他看著第二個while循環(huán)非常不爽，盡管對整體性能已經(jīng)沒有太大影響了。
也許這就是大牛與我等普通碼農(nóng)的區(qū)別，大?？偸亲非髽O致，總是可以在看似不可能的時候，再往前走一步。
C語言switch-case的一些特性
Duff注意到C語言中switch-case語句的一些特性：
于是，Duff便利用switch-case的特性，用來處理第一個while循環(huán)之后仍然剩余的count % 8個字節(jié)的數(shù)據(jù)。于是便有了這樣的代碼：
稍微解釋下這段代碼：
我們假設count = 20，那么：
n = (count + 7) / 8 = 27 / 8 = 3count % 8 = 4所以：
好了，到這里，大家應該理解Duff's Device了吧？還是不清楚的話，可以嘗試單步跟蹤一下，就會很清晰了。
理解了Duff's Device之后，文章開頭的那個題目就很好理解了，現(xiàn)在揭曉答案：
再看一下源碼：
編譯運行：
所以，答案是：20
隨著硬件的性能越來越好，容量越來越大，導致很多童鞋覺得，現(xiàn)在去糾結諸如Cache、ILP、循環(huán)展開等優(yōu)化手段沒有太大的現(xiàn)實意義。
但是，當系統(tǒng)遇到性能瓶頸而又找不到解決思路時，往往在這些平時被絕大多數(shù)人忽略的地方，能收到意想不到的收獲！而且，一個設計精良的系統(tǒng)，往往設計之初就要充分考慮到這些因素，只有這樣才能把硬件的性能充分挖掘出來。
限于篇幅原因，對Cache、ILP技術無法展開介紹，后續(xù)我會更新一系列文章，詳細介紹這些技術細節(jié)。感興趣的童鞋，不妨右上角關注一下！謝謝！
最后，友情提示：Duff's Device雖然很精妙，但是對于絕大多數(shù)童鞋來說，理解起來還是相對比較困難的。因此，產(chǎn)品代碼中，不建議使用。否則，輕則被其他童鞋群毆，重則直接被拿來祭天！
你對Duff's Device有什么想法嗎？歡迎留言討論！覺得有用的話，點個贊唄！
對編譯器，OS內核、性能調優(yōu)等童鞋感興趣的話，不妨去看下我正在更新的另一個系列專題:-)
聯(lián)系客服
