優(yōu)化C++代碼（4）：消除冗余代碼
這篇文章講述了消除冗余代碼（Dead Code Elimination）的優(yōu)化方法，我簡寫為DCE。顧名思義：只要其計算結(jié)果沒有被程序所使用， 該計算就被丟棄。
這時你可能會說，你的代碼只會計算有用的結(jié)果，從沒有無用的東西，只有白癡才會平白無故地添加那些無用的代碼—–例如，會在做一些有用事情的同時，還在計算著圓周率的前1000位。那么消除冗余代碼的優(yōu)化，到底什么時候才有用呢?
我之所以這么早就開始講述DCE的優(yōu)化，是因為如果不清楚DCE的話，在探索其他一些更有趣的優(yōu)化方法中會造成一些破壞和混亂。看一下下面的小例子，文件Sum.cpp：
- int main() {
- long long s = 0;
- for (long long i = 1; i <= 1000000000; ++i) s += i;
- }
我們對于在計算這十億個數(shù)的和時，循環(huán)的執(zhí)行速度很感興趣。（的確，這種做法太愚蠢了，我們高中時就學過有一個閉公式可以計算出結(jié)果，但這不是重點）
使用命令 CL /Od /FA Sum.cpp 來 構(gòu)建這個程序，并用Sum命令來運行程序。注意這個構(gòu)建使用/Od開關(guān)禁用了代碼優(yōu)化。 在我的PC機上，運行這個程序花費了4秒。 現(xiàn)在試著使用CL /O2 /FA Sum.cpp 來編譯優(yōu)化過的代碼。這次運行很快，幾乎察覺不到有延遲。編譯器對我們的代碼的優(yōu)化有這么出色嗎？答案是否定的（但它的確是以一種奇怪的方式改變了我們的 代碼）
我們看一下/Od版本生成的代碼，它保存在Sum.asm里。我精減了一些代碼并注釋了一些文本，讓它只顯示循環(huán)體：
這些指令跟你預料中的差不多。 變量i保存以在RSP為寄存器，i$1為偏移量的棧上；在asm文件的其他地方，我們發(fā)現(xiàn)i$1=0. 使用RAX寄存器讓i自增長。同樣地，變量s保存在RSP為寄存器，S$為偏移量的棧上，s$=8. 并在RCX中來計算每次循環(huán)的累積和。
我們注意到每次循環(huán)時，先從棧上獲取i的值，再把新值寫回去，變量s同樣如此。可以說這段代碼很幼稚—–它是由很愚蠢的編譯器生成的（也就說，優(yōu)化被禁用了）。 例如，我們本來可以將變量i和s一直保存在寄存器中，而不用每次循環(huán)迭代時都要訪問內(nèi)存。
關(guān)于未優(yōu)化的代碼就說這么多了。那么進行優(yōu)化后所生成代碼是什么樣呢? 來看一下使用/O2構(gòu)建的程序?qū)?yīng)的Sum.asm文件，再一次把文件精簡到只剩下循環(huán)體的實現(xiàn)，
結(jié)果是：
- ;; there’s nothing here!
對，它是空的，沒有任何計算s的指令。
你可能會說，那這個答案肯定錯了.但是我們怎么知道這個答案就是錯的呢?因為優(yōu)化器已經(jīng)推斷出程序在任何時候都沒用到S， 所以才懶得計算它。你不能說答案是錯的，除非你需要核對該答案，對吧？
我們這不是被DCE優(yōu)化給耍了嗎？ 如果你不需要觀察計算結(jié)果，程序是不會進行計算的。
優(yōu)化器的這個問題其實跟量子物理學的基本原理很類似，可以用大眾科普文章里經(jīng)常提到的一句話來解釋，“如果森林里一棵樹倒下了，但是如果周圍都沒人，它還會有聲音嗎？”。
我們可以在代碼里添加打印變量s的語句來觀察計算結(jié)果，代碼如下：
- #include <stdio.h>
- int main() {
- long long s = 0;
- for (long long i = 1; i <= 1000000000; ++i) s += i;
- printf("%lld ", s);
- }
運行/Od版本的程序打印出了正確結(jié)果，還是花費了4秒，/O2版本打印出同樣的結(jié)果，速度卻快得多（具體快多少，可以看下下面的可選部分，實際上，速度高達7倍多）。
到現(xiàn)在為止，我已經(jīng)講述了這篇文章的主要觀點：在進行編譯器優(yōu)化分析的時候一定要十分小心，衡量它們的優(yōu)點時，千萬不要被DCE給誤導了。 下面是使用DCE優(yōu)化時需要注意的四個步驟：
- 檢查計時，確保沒有突然提高一個數(shù)量級；
- 檢查生成的代碼（使用 /FA）
- 如果不太確定，可以添加一個printf語句
- 把你感興趣的代碼放到一個獨立的.CPP文件里，和含有main函數(shù)的文件分開。只要你不進行整個程序的優(yōu)化，就一定會奏效（使用/GL，我們后面會講到）。
不管怎么樣，我們從這個例子中還是學到了一些很有意思的東西，下面四個小節(jié)為可選部分。
- xor edx, edx
- mov eax, 1
- mov ecx, edx
- mov r8d, edx
- mov r9d, edx
- npad 13
- $LL3@main:
- inc r9
- add r8, 2
- add rcx, 3
- add r9, rax ;; r9 = 2 8 18 32 50 ...
- add r8, rax ;; r8 = 3 10 21 36 55 ...
- add rcx, rax ;; rcx = 4 12 24 40 60 ...
- add rdx, rax ;; rdx = 1 6 15 28 45 ...
- add rax, 4 ;; rax = 1 5 9 13 17 ...
- cmp rax, 1000000000 ;; i <= 1000000000 ?
- jle SHORT $LL3@main ;; yes, so loop back
注意看循環(huán)體包含了和未優(yōu)化版本一樣多的指令，為什么會快很多呢？那是因為優(yōu)化后的循環(huán)體的指令使用的是寄存器，而不是內(nèi)存地址。 我們都知道，寄存器的訪問速度比內(nèi)存快得多。 下面的延遲就展示了內(nèi)存訪問時如何將你的程序降到蝸牛般的速度：
|
Location |
延時 |
|
Register |
1 cycle |
|
L1 |
4 cycles |
|
L2 |
10 cycles |
|
L3 |
75 cycles |
|
DRAM |
60 ns |
所以，未優(yōu)化版本是在棧上進行讀寫的，比起在寄存器中進行計算慢多了（寄存器的存取時間只需一個周期）。
但是還有其他原因的，注意/Od版本的執(zhí)行循環(huán)的時候計數(shù)器每次加1，/O2版本的計數(shù)器（保存在RAX寄存器中）每次加4。
優(yōu)化器已經(jīng)展開循環(huán)，每次迭代都會把四項加起來，像這樣：
s = (1 + 2 + 3 + 4) + (5 + 6 + 7 + 8) + (9 + 10 + 11 + 12) + (13 + . . .
通過展開這個循環(huán)，可以看到每四次迭代才對循環(huán)做一個判斷，而不是每次都進行判斷，這樣CPU可以節(jié)省更多的時間做一些有用的事，而不是在不停地進行循環(huán)判斷。
還有，它不是將結(jié)果存在一個地方，而是使用了四個獨立的寄存器，分別求和，像這樣：
RDX = 1 + 5 + 9 + 13 + ... = 1, 6, 15, 28 ...
R9 = 2 + 6 + 10 + 14 + ... = 2, 8, 18, 32 ...
R8 = 3 + 7 + 11 + 15 + ... = 3, 10, 21, 36 ...
RCX = 4 + 8 + 12 + 16 + ... = 4, 12, 24, 40 ...
循環(huán)結(jié)束時，再把四個寄存器的和加起來，得到最終結(jié)果。
（讀者朋友們可以思考下這個練習，如果循環(huán)總數(shù)不是4的倍數(shù)，那優(yōu)化器會怎么處理？）
可選2： 精確的性能測試
之前，我在沒有使用printf函數(shù)的/O2版本的程序中說過，“運行速度之快以致于你察覺不到有任何延遲”， 下面就用一個例子更準確地描述下這種說法：
- #include <stdio.h>
- #include <windows.h>
- int main() {
- LARGE_INTEGER start, stop;
- QueryPerformanceCounter(&start);
- long long s = 0;
- for (long long i = 1; i <= 1000000000; ++i) s += i;
- QueryPerformanceCounter(&stop);
- double diff = stop.QuadPart - start.QuadPart;
- printf("%f", diff);
- }
程序中使用了QueryPerformanceCounter 來計算運行時間（這就是我之前的博客里寫到的精簡版本的高分辨率計時器）。 在測量性能的時候，心中一定謹記一些注意事項（我以前有寫過一個列表），但是對這個特殊的例子，其實也沒什么用，我們一會兒就能看到：
我在PC機上運行了/Od版本的程序，打印diff的值，大約為7百萬。（計算結(jié)果的單位并不重要，只需知道 這個值越大，程序運行的時間就越長）。而/O2版本，diff的值則為0.原因就得歸功于DCE優(yōu)化了。
我們?yōu)榱俗柚笵CE，添加一個printf函數(shù)，/Od版本的diff值大約為1百萬—-速度提升了7倍。
可選3：x64 匯編程序 “擴展”
我們在回頭看看文章里的匯編代碼部分，在初始化寄存器部分，會發(fā)現(xiàn)有點奇怪：
- xor edx, edx ;; rdx = 0 (64-bit!)
- mov eax, 1 ;; rax = i = 1 (64-bit!)
- mov ecx, edx ;; rcx = 0 (64-bit!)
- mov r8d, edx ;; r8 = 0 (64-bit!)
- mov r9d, edx ;; r9 = 0 (64-bit!)
- npad 13 ;; multi-byte nop alignment padding
- $LL3@main:
記得原始C++語言會使用long long類型的變量來保存循環(huán)計數(shù)器和總和。 在VC++編譯器中，會映射成64位的整數(shù)，所以我們會料到生成碼應(yīng)該會用x64的64位寄存器。
上一篇文章中，我已經(jīng)講過了，指令xor reg， reg是 用來將reg的值置為0的一種高效的方法。但是第一條指令是在對EDX寄存器（RDX寄存器的低32位字節(jié)）進行xor運算，下一條指令是將 EAX（也就是RAX寄存器的低32位字節(jié)）賦值為1。下面的三條指令也是同樣的方式。從表面來看，這樣每一個目標寄存器的高32位字節(jié)都存儲的是一個任 意的隨機數(shù)，而循環(huán)體的計算部分是在擴展的64位寄存器上進行的，這樣的計算結(jié)果怎么可能是對的？
答案是因為最初由AMD發(fā)布的x64位指令集，會將64位的目標寄存器的高32位字節(jié)自動擴展為零。 下面是該手冊的3.4.5小節(jié)的兩個知識點：
1. 32位寄存器的零擴展： 如果寄存器為32位，自動將通用目標寄存器的高32位擴展為零。
2. 8位和16位字節(jié)寄存器 無擴展： 如果是8位和16位寄存器，則不對64位通用寄存器做改變。
最后，注意一下npad 13 這條指令（其實是一個偽操作，一條匯編指令）。用來確保下一條指令（從循環(huán)體開始）遵循16字節(jié)的內(nèi)存對齊，可以提高性能(有時，用于微架構(gòu))。
可選4: printf 和 std::out
你也許會問，在上個實驗中，為什么我使用了C的printf函數(shù)，而不是C++的std::out呢? 試試看，其實兩者都可以，但是后者生成的asm文件要大很多，所以瀏覽起來不太方便: 相比前面的1.7K字節(jié)文件， 后者生成的文件達0.7M 字節(jié)。
