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

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

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

引言

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

代碼如下圖所示：

圖片

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

其實(shí)，這個(gè)題目還是源自大師之手，我只是做了少許修改。先來(lái)聊一下這段歷史淵源吧。

注：為了盡量解釋清楚，篇幅有點(diǎn)長(zhǎng)，請(qǐng)耐心讀完，相信你會(huì)有收獲的！

歷史淵源

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

圖片

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

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

圖片

下面講解一下這段代碼。

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

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

最簡(jiǎn)單的實(shí)現(xiàn)

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

圖片

代碼清晰簡(jiǎn)潔，很直觀(guān)，簡(jiǎn)直完美，對(duì)吧？

Duff卻對(duì)此很不滿(mǎn)意，因?yàn)樗X(jué)得這種寫(xiě)法雖然簡(jiǎn)單，但太過(guò)低效，無(wú)法接受。

如此簡(jiǎn)單的代碼，為何說(shuō)它性能低下呢？主要有兩個(gè)問(wèn)題：

? "無(wú)用"指令太多

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

我們來(lái)分析一下。

無(wú)用指令太多

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

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

*to = *from++;

而每次迭代過(guò)程中的while (--count > 0)產(chǎn)生的指令，以及每次迭代結(jié)束后的跳轉(zhuǎn)指令，對(duì)結(jié)果來(lái)說(shuō)都是無(wú)用指令。

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

我們看一下匯編代碼：

圖片

有些童鞋對(duì)匯編不太熟悉，我簡(jiǎn)單講解一下：

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

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

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

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

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

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

我們看到，熱點(diǎn)路徑中，無(wú)用指令數(shù)占了整個(gè)熱點(diǎn)路徑指令數(shù)的一半，其開(kāi)銷(xiāo)也占到整個(gè)函數(shù)的50%！

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

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

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

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

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

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

循環(huán)展開(kāi)

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

循環(huán)展開(kāi)，有以下優(yōu)點(diǎn)：

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

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

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

注：關(guān)于循環(huán)展開(kāi)的詳細(xì)講解，請(qǐng)參看文末推薦閱讀的兩篇文章(如果你還沒(méi)看過(guò)的話(huà))。

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

實(shí)例 - 循環(huán)展開(kāi)對(duì)性能的影響

測(cè)試環(huán)境：

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

測(cè)試代碼：

圖片

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

測(cè)試結(jié)果：

圖片

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

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

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

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

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

圖片

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

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

圖片

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

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

C語(yǔ)言switch-case的一些特性

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

? case語(yǔ)句后面的break語(yǔ)句不是必須的。

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

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

圖片

解釋下這段代碼：

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

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

所以：

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

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

揭曉答案

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

再看一下源碼：

圖片

編譯運(yùn)行：

圖片

所以，答案是：20