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

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

全文如下，僅作微調(diào)。

引言

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

代碼如下圖所示：

圖片

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

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

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

歷史淵源

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

圖片

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

先看一下大牛的風(fēng)采吧：

圖片

下面講解一下這段代碼。

Duff's Device - 達夫設(shè)備

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

最簡單的實現(xiàn)

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

圖片

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

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

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

? "無用"指令太多

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

我們來分析一下。

無用指令太多

所謂無用指令，是指不直接對所期望的結(jié)果產(chǎn)生影響的指令。

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

*to = *from++;

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

上面最簡單的實現(xiàn)中，每次循環(huán)迭代只拷貝一個字節(jié)數(shù)據(jù)。這就意味著，有多少個字節(jié)的數(shù)據(jù)，就需要執(zhí)行多少次跳轉(zhuǎn)和條件判斷，以及--count的操作。

我們看一下匯編代碼：

圖片

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

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

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

? 第9~14行，對應(yīng)C語言的*to = *from++；

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

? 最后幾句，恢復(fù)棧幀并返回

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

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

無法充分發(fā)揮ILP技術(shù)優(yōu)勢

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

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

但是，在代碼熱點路徑上，無用指令太多，且每個迭代只執(zhí)行一條*to = *from++，無法充分發(fā)揮ILP的技術(shù)優(yōu)勢。

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

現(xiàn)在，知道上面那個簡單實現(xiàn)性能差的原因了，那么如何去優(yōu)化它呢？

循環(huán)展開

所謂循環(huán)展開，是通過增加每次迭代內(nèi)數(shù)據(jù)操作的次數(shù)，來減小迭代次數(shù)，甚至徹底消除循環(huán)迭代的一種優(yōu)化手段。

循環(huán)展開，有以下優(yōu)點：

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

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

循環(huán)展開是一個很常用的性能優(yōu)化手段，所有現(xiàn)代編譯器，通過合適的選項，都支持循環(huán)展開優(yōu)化。

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

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

實例 - 循環(huán)展開對性能的影響

測試環(huán)境：

OS：Ubuntu 19.04(Linux Kernel 5.0.0)
CPU：Intel(R) Xeon(R) Gold 6130
主頻：2.10GHz
Cache 大?。?2MB
Cache line 大?。?4 Bytes

測試代碼：

圖片

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

? loop1.c每次循環(huán)迭代執(zhí)行一次k++

• ? loop2.c每次循環(huán)執(zhí)行8次k++，但是循環(huán)的次數(shù)比loop1.c少了8倍

編譯：

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

測試結(jié)果：

圖片

做同樣的事情，通過循環(huán)展開優(yōu)化，所消耗時間直接從25.4秒降到了14.7秒！

第一次優(yōu)化嘗試

了解了循環(huán)展開對性能提升的好處之后，我們就可以對上面的簡單實現(xiàn)進行第一次優(yōu)化嘗試了。

我們先嘗試把每次循環(huán)內(nèi)拷貝字節(jié)的個數(shù)，由1個提高到到8個，這樣就可以把迭代次數(shù)降低8倍。

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

圖片

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

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

圖片

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

也許這就是大牛異于常人之處，大?？偸亲非髽O致，總是可以在看似不可能的時候，再往前走一步。

C語言switch-case的一些特性

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

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

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

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

圖片

解釋下這段代碼：

我們假設(shè)count = 20，那么：

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

所以：

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

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

揭曉答案

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

再看一下源碼：

圖片

編譯運行：

圖片

所以，答案是：20