大家好，我是江南一散人。周末逛知乎時，無意間看到阿里云開發者官方賬號的一篇文章中，居然引用了我三年前在今日頭條寫的一篇文章。有些感概，看來還真的在互聯網上留下了點痕跡。

那篇文章，其實和那篇《改幾行代碼，for循環耗時從3.2秒降到0.3秒！真正看懂的都是牛人！》是相關的，算是前傳吧，所以在這里發一下，感興趣的小伙伴不妨圍觀下！

全文如下，僅作微調。

引言

昨天發了一段有趣的代碼，引來很多童鞋圍觀。很多童鞋表示不太明白，于是就有了本文，詳細解釋下這段代碼的來龍去脈。

代碼如下圖所示：

圖片

如果你是第一次看到的話，不妨試一下，看你能得出正確答案嗎？

其實，這個題目還是源自大師之手，我只是做了少許修改。先來聊一下這段歷史淵源吧。

注：為了盡量解釋清楚，篇幅有點長，請耐心讀完，相信你會有收獲的！

歷史淵源

1983年11月，一位叫Tom Duff的大牛在編寫串口通信程序時，發現使用一般的寫法時，性能總是不能讓人滿意。后來，這位老兄憑借深厚的編程功底和精湛的C語言技藝，利用C語言中switch語句的一個鮮為人知的特性，發明如了下圖所示的經典代碼：

圖片

結果，引來無數吃瓜群眾膜拜。在此之前，還沒有人發現并利用過C語言的這個特性，于是他便以自己的名字命名這段代碼，叫做Duff's Device，一般譯為"達夫設備"。

先看一下大牛的風采吧：

圖片

下面講解一下這段代碼。

Duff's Device - 達夫設備

當時，Duff的需求，是把一段起始地址為from，長度為count的數據，寫入到一個內存映射的I/O(Memory Mapped I/O)寄存器to中。

最簡單的實現

需求很簡單，對吧？很容易想到直接用for或者while循環就可以解決了，如下圖所示：

圖片

代碼清晰簡潔，很直觀，簡直完美，對吧？

Duff卻對此很不滿意，因為他覺得這種寫法雖然簡單，但太過低效，無法接受。

如此簡單的代碼，為何說它性能低下呢？主要有兩個問題：

? "無用"指令太多

? 無法充分發揮CPU的ILP(Instruction-Level Parallelism)技術

我們來分析一下。

無用指令太多

所謂無用指令，是指不直接對所期望的結果產生影響的指令。

對于這段代碼，我們期望的結果就是把數據都拷貝到I/O寄存器to中。那么，對于這個期望的結果來說，真正有用的代碼，其實只有中間那一行賦值操作：

*to = *from++;

而每次迭代過程中的while (--count > 0)產生的指令，以及每次迭代結束后的跳轉指令，對結果來說都是無用指令。

上面最簡單的實現中，每次循環迭代只拷貝一個字節數據。這就意味著，有多少個字節的數據，就需要執行多少次跳轉和條件判斷，以及--count的操作。

我們看一下匯編代碼：

圖片

有些童鞋對匯編不太熟悉，我簡單講解一下：

? x64上優先使用寄存器傳遞，對于send()函數，第一個參數to存放在寄存器rdi中，第二個參數from存放在rsi中，第三個參數count存放在寄存器edx中。

? 第2~7行，把三個參數分別壓入棧中；

? 第9~14行，對應C語言的*to = *from++；

? 第15~19行，對應C語言的while (--count > 0)；

? 最后幾句，恢復棧幀并返回

所以，第9-19行屬于熱點路徑，也就是主循環體。第9-14行屬于有效指令，第15-19行對于期望的數據結果來說就是無用指令。

我們看到，熱點路徑中，無用指令數占了整個熱點路徑指令數的一半，其開銷也占到整個函數的50%！

無法充分發揮ILP技術優勢

現代CPU為了提高指令執行的速度和吞吐率，提升系統性能，不僅一直致力于提升CPU的主頻，還實現了多種ILP(Instruction-Level Parallelism 指令級并行)技術，如超流水線、超標量、亂序執行、推測執行、分支預測等。

一個設計合理的程序，往往能夠充分利用CPU的這些ILP機制，以使性能達到最優。

但是，在代碼熱點路徑上，無用指令太多，且每個迭代只執行一條*to = *from++，無法充分發揮ILP的技術優勢。

注：這里解釋不夠清楚，詳細講解請參看文末推薦閱讀的兩篇文章，詳細介紹了ILP技術(如超流水線、超標量、推測執行、分支預測)。

現在，知道上面那個簡單實現性能差的原因了，那么如何去優化它呢？

循環展開

所謂循環展開，是通過增加每次迭代內數據操作的次數，來減小迭代次數，甚至徹底消除循環迭代的一種優化手段。

循環展開，有以下優點：

? 有效減少循環控制指令。前面說過，這些指令，是對結果不產生影響的無用指令。減少這些指令，就可以減少這些指令本身執行所需的開銷，從而提升整體性能。

? 通過合理的展開，可以更加有效地利用指令級并行ILP(Instruction-Level Parallelism 指令級并行)技術。

循環展開是一個很常用的性能優化手段，所有現代編譯器，通過合適的選項，都支持循環展開優化。

注：關于循環展開的詳細講解，請參看文末推薦閱讀的兩篇文章(如果你還沒看過的話)。

有童鞋可能會好奇，循環展開到底能提升多少性能呢？我們還是用數據說話，看一個實例吧。

實例 - 循環展開對性能的影響

測試環境：

OS：Ubuntu 19.04(Linux Kernel 5.0.0)
CPU：Intel(R) Xeon(R) Gold 6130
主頻：2.10GHz
Cache 大小：22MB
Cache line 大小：64 Bytes

測試代碼：

圖片

loop1.c和loop2.c做的事情一樣，唯一的區別是：

? loop1.c每次循環迭代執行一次k++

• ? loop2.c每次循環執行8次k++，但是循環的次數比loop1.c少了8倍

編譯：

gcc loop1.c -o loop1
gcc loop2.c -o loop2

測試結果：

圖片

做同樣的事情，通過循環展開優化，所消耗時間直接從25.4秒降到了14.7秒！

第一次優化嘗試

了解了循環展開對性能提升的好處之后，我們就可以對上面的簡單實現進行第一次優化嘗試了。

我們先嘗試把每次循環內拷貝字節的個數，由1個提高到到8個，這樣就可以把迭代次數降低8倍。

我們先假設，send()函數的參數count總是8的倍數，那么上面的代碼就可以修改為：

圖片

上面的代碼很好理解，就是把原來迭代里的操作復制了8次，然后把迭代次數降低到了8倍。

但是，我們前面做了一個假設，就是count是8的倍數。那如果不是8的整數倍呢，比如20？那我們可能會想到這樣的實現：

圖片

其實，到了這里，相比原始的實現來說，性能已經能提升了不少了。但是，Duff仍然不滿意，他看著第二個while循環非常不爽，盡管對整體性能已經沒有太大影響了。

也許這就是大牛異于常人之處，大牛總是追求極致，總是可以在看似不可能的時候，再往前走一步。

C語言switch-case的一些特性

Duff注意到C語言中switch-case語句的一些特性：

? case語句后面的break語句不是必須的。

? 在switch語句內，case標號可以出現在任意的子語句之前，甚至運行出現在if、for、while等語句內。

于是，Duff便利用switch-case的特性，用來處理第一個while循環之后仍然剩余的count % 8個字節的數據。于是便有了這樣的代碼：

圖片

解釋下這段代碼：

我們假設count = 20，那么：

n = (count + 7) / 8 = 27 / 8 = 3
count % 8 = 4

所以：

1. 1. switch語句會落入case 4的標簽內，然后依次執行了case 4、3、2、1四條語句。自此之后，其實就跟switch-case語句再也沒有關系了。
2. 2. while語句判斷--n > 0，條件成立，于是跳轉到case 0進入循環體執行，于是依次執行case 0、7、6、5、4、3、2、1一共8條語句。此時n = 2.
3. 3. 再次進入while語句處判斷--n >0，條件成立，再次跳轉到case 0處進入循環體執行。此時n = 1。
4. 4. 此時，while語句處判斷--n >0，條件失敗，退出循環，函數結束。

好了，到這里，大家應該理解Duff's Device了吧？還是不清楚的話，可以嘗試單步跟蹤一下，就會很清晰了。

揭曉答案

理解了Duff's Device之后，文章開頭的那個題目就很好理解了，現在揭曉答案：

再看一下源碼：

圖片

編譯運行：

圖片

所以，答案是：20