能要求

編寫一個控制臺應用程序，使用for循環輸出10“我不敢了！”

實現步驟

for i in range(1, 11):

print("%d：我不敢了！" % i)

運行結果

代碼分析

for i in range(1, 11):

print("%d：我不敢了！" % i：循環變量i在1~11之間，包括1但不包括11，i從1開始，執行循環體中的print("%d：我不敢了！" % i語句后，i加1，循環結構繼續執行，直到i等于11時，跳出循環體，執行循環體后面的語句，即結束循環。

功能要求

編寫一個控制臺應用程序，使用for循環計算出5的階乘，即求1到5的成績，求1 * 2 * 3 * 4 * 5的值。

實現步驟

sum = 1

for i in range(1, 6):

sum *= i

print("1 * 2 * 3 * 4 * 5 = %d" % sum)

運行結果

代碼分析

for i in range(1, 6):

sum *= i：循環變量i在1~6之間，包括1但不包括6，i從1開始，執行循環體中的sum *= i語句后，sum的值變為sum = sum * i，i加1，循環結構繼續執行，直到i等于6時，跳出循環體，結束循環。執行循環體后面的print("1 * 2 * 3 * 4 * 5 = %d" % sum)語句，即將1~5的乘積結果打印輸出，結束程序。

知識說明

循環語句：可以在滿足循環條件的情況下，反復執行某一段代碼。這段被重復執行的代碼被稱為循環體。當反復執行這個循環體時，需要在合適的時候把循環條件改為假，從而結束循環；否則循環將一直執行下去，形成死循環。

for循環格式

for 變量 in 范圍:

循環執行語句

當循環“變量”的值在一定的“范圍”內，執行“循環語句”，當循環“變量”的值不在“范圍”內時跳出循環體，循環程序結構結束。

range函數

range意為在……范圍內，其語法如下：

range([start, ]end[, step])

其中，start是循環開始的地方，可以省略不寫，若省略，默認為0；end是循環結束的地方，但不包含end。step這個參數也可以不寫，若省略，默認步長為1。

歸是一種編程技術，其中一個函數直接或間接調用自身。在C#中，遞歸通常用于解決可以分解為更小相似問題的問題，例如計算階乘、斐波那契數列等。

下面是一個使用C#編寫的遞歸函數的簡單例子，用于計算一個整數的階乘。階乘函數是遞歸的一個經典例子，因為計算n的階乘（記為n!）涉及到計算(n-1)的階乘，以此類推，直到達到最基本的情況（例如0的階乘是1）。

csharp

復制

using System;

class RecursionExample
{
    static void Main()
    {
        Console.WriteLine("請輸入一個整數以計算其階乘：");
        int number = int.Parse(Console.ReadLine());
        
        // 檢查輸入是否為非負整數
        if (number < 0)
        {
            Console.WriteLine("負數沒有階乘。");
        }
        else
        {
            // 調用遞歸函數
            long factorial = Factorial(number);
            Console.WriteLine($"階乘 {number}! = {factorial}");
        }
    }

    // 遞歸函數計算階乘
    static long Factorial(int n)
    {
        if (n == 0) // 遞歸的基本情況
        {
            return 1;
        }
        else
        {
            // 遞歸調用：n的階乘是n乘以(n-1)的階乘
            return n * Factorial(n - 1);
        }
    }
}

在這個例子中，Factorial 函數將一直遞歸調用自身，直到它達到基本情況（n == 0），此時它返回1。每次遞歸調用返回時，它會乘以當前的n值，從而計算出階乘。

請注意，遞歸函數需要有一個終止條件，否則它會無限遞歸下去，這可能會導致堆棧溢出錯誤。此外，遞歸函數可能不是解決某些問題的最有效方法，因為它們可能會占用大量的內存和處理器時間。在某些情況下，使用循環和迭代可能是更好的選擇。

文講解一個非常重要的性能調優方法，會涉及到CPU內部非常重要的一些基礎知識，為講解清楚，篇幅較長，請務必看完，你一定會有收獲！

一切都要從一個面試題說起！

一道面試題

有朋友私信給我，聊了下自己的一段面試經歷，有這么一段代碼：

面試官：這段求階乘的代碼怎么樣？

答：挺簡潔的，簡單易懂。不過如果參數n值比較大的話，會導致fact溢出，結果是錯的。

面試官：嗯，是的。不過，咱們先不考慮溢出的問題，你覺得這段代碼的性能怎么樣？

答：時間復雜度是O(n)，而且代碼比較精煉，性能應該還挺不錯的吧？(心虛ing...)

面試官：你能想辦法把它優化一下，讓性能更好嗎？

思考ing...

答：在多CPU系統上，如果n的值比較大的話，可以考慮用多線程來實現。

面試官：嗯，這是一個思路。如果是單CPU呢？

再次思考ing...

答：用GCC編譯的話，可以加上優化選項-O3，應該能提高性能。

面試官：嗯，還有嗎？

答：沒了。

面試官：好了，感謝來參加面試，回去等通知吧！

思考一下，如果是你的話，會怎么回答呢？

下面，來深入講解一下，隱藏在這道題背后的深層次知識！

本文較長，且涉及到CPU內部很底層的知識，請耐心看完，一定會有收獲！

測試程序

測試程序test.c非常簡單，計算1000000000的階乘：

注：calc()加__attribute__((noinline))是禁止GCC把calc內聯在main()中，只是為了方便對比性能，不必糾結。

編譯一下，然后用time命令測量下運行耗時：

然后，把程序稍微改一下，命名為test_2.c：

編譯，并用time命令測量下運行耗時：

運行耗時從原來的3.29秒降到了1秒，性能提升了200%！

看到這里，有人會說，不就是循環展開嘛，很簡單的，沒什么好研究的，而且加了優化選項之后，編譯器會自動進行循環展開的，沒必要手動去展開，也就沒有研究的價值了！

真的是這樣嗎？先嘗試回答下面幾個問題：

1. 循環展開為什么能提高程序性能，其背后的深層次原理是什么？
2. 循環隨便怎么展開都一定可以提高性能嗎？
3. 用了優化選項，編譯器一定會幫我們自動進行循環展開優化嗎？

第一個問題后面會詳細講解，我們先用實例回答下第2個和第3個問題。

先看第2個問題。

循環隨便展開都能提高性能嗎？

我們把test_2.c稍微改一下，命令為test_3.c：

仍然是循環展開，只不過把循環展開的方式稍微改了一下。 再編譯一下，用time命令測量下運行耗時：

和test.c相比運行耗時只減少了0.2秒！為什么同樣是循環展開，test_2.c只需要1.6秒，而test_3.c卻要3秒，為什么性能差異這么大呢？別著急，后面細講。

再看第三個問題，加了優化選項，編譯器一定會幫我們自動進行循環展開優化嗎？一試便知！

加了-O3，編譯器一定會循環展開嗎？

重新編譯下test.c, test_2.c, 和test_3.c，只不過，這次我們加上-O3優化選項，然后分別用time命令再測量下運行時間。

先是test.c：

加了-O3優化后，程序耗時從原來的3.29秒降到了1.07秒，性能提升確實非常明顯！ 是否好奇，-O3選項對test.c做了什么樣的優化，能夠把程序耗時降到三分之一？這個后面再講。

現在，我們先試下test_2.c：

同樣，加了-O3后，程序耗時從原來的1秒降到了0.368秒！ 此外，在同樣加了-O3的情況下，使用了手段循環展開的test_2.c，程序耗時仍然是test.c的三分之一！ 可見，編譯器確實優化了一些東西，但是，無論是否加-O3優化選項，進行手動循環展開的test.c仍然是性能最好的！

最后，再試下test_3.c:

看到了吧？同樣加了-O3優化選項的前提下，性能仍然與test_2.c相差甚遠！

小結一下我們現在得到的幾組測試結果：

在解釋這些性能差異的原因之前，必須要先補充一些CPU相關的基礎知識，否則無法真正理解這背后的原因！所以，請務必認真看完！

這會涉及到CPU內部實現細節的知識，相對比較底層，而且對絕大多數程序員是透明的，因此很多人甚至都沒聽說過這些概念。不過，也不用擔心，跟之前一樣，我會盡量用通俗易懂的語言來解釋這些概念。

指令流水線(pipeline)

所謂流水線，是把指令的執行過程分成多個階段，每個階段使用CPU內部不通的硬件資源來完成。以經典的5級流水線為例，一條指令的執行被分為5個階段：

• 取指(IF)：從內存中取出一條指令。
• 譯碼(ID)：對指令進行解碼，確定該指令要執行的操作。
• 執行(EX)：執行該指令要執行的操作。
• 訪存(MEM)：進行內存訪問操作。
• 寫回(WB)：把執行的結果寫回寄存器或內存。

在時鐘信號的驅動下，CPU依次來執行這些步驟，這就構成了指令流水線(pipeline)。如下圖所示：

在CPU內部，執行每個階段使用不同的硬件資源，從而可以讓多條指令的執行時間相互重疊。當第一條指令完成取指，進入譯碼階段時，第二條指令就可以進入取指階段了。以此類推，在一個5級流水線中，理想情況下，可以有5條不同的指令的不同階段在同時執行，因此每個時鐘周期都會有一條指令完成執行，從而大大提高了CPU執行指令的吞吐率，從而提高CPU整體性能。這就叫做ILP - 指令級并行（Instruction Level Parallelism）。如下圖所示：

通過把指令執行分為多個階段，CPU每個時鐘周期只處理一個階段的工作，這樣大大簡化了CPU內部負責每個階段的功能單元，每個時鐘周期要做的事情少了，提高時鐘頻率也變得簡單了。

前面說過，有了流水線技術，理想情況下，每個時鐘周期，CPU可以完成一條指令的執行。那有沒有什么方法，可以讓CPU在每個時鐘周期，完成多條指令的執行呢，這豈不是會大大提高CPU整體性能嗎？

當然有！這就是Superscalar技術！（除此之外還有VLIW，不是本文重點，不再展開討論。）

超標量(Superscalar)

Superscalar，通過在CPU內部實現多條指令流水線，可以真正實現多條命令并行執行，也被稱為多發射數據通路技術。以雙發射流水線為例，每個時鐘周期，CPU可以同時讀取兩條指令，然后同時對這兩條指令進行譯碼，同時執行，然后同時寫回。如下圖所示：

目前為止，這一切看起來都很完美，對吧？然而，現實往往沒有理想那么豐滿！接著往下看吧。

流水線沖突

大家可能注意到了，前面多次強調過，“在理想狀態下”，為什么呢？

現實中程序的指令序列之間往往存在各種各樣的依賴和相關性，而CPU為了解決這種指令間的依賴和相關性，有時候不得不“停頓”下來，直到這些依賴得到解決，這就導致CPU指令流水線無法總是保持“全速運行”。

這種現象被稱之為Pipeline Hazard，很多資料翻譯為“流水線冒險”，我覺得“流水線沖突”更為貼切易懂。

歸結起來，有三種情況：

• 數據沖突(Data Hazard)
• 控制沖突(Control Hazard)
• 結構沖突(Structure Hazard)

下面分別舉例解釋這三種類型的沖突。

數據沖突

所謂數據沖突，簡單講，就是兩條在流水線中并行執行的指令，第二條指令需要用到第一條指令的執行結果，因此第二條指令的執行不得不暫停，一直到可以獲取到第一條指令的執行結果為止。

比如，用偽代碼舉例：

x = 1;
y = x;

要對y進行賦值，必須要先得到x的值，因此這兩條語句無法完全并行執行。

這只是其中的一種典型情況，其他情況不再贅述。

控制沖突

所謂控制沖突，簡單講，就是在CPU在執行分支跳轉時，無法預知下一條要執行的指令。

比如：

if(a > 100) {
    x = 1;
} else {
    y = 2;
}

在CPU計算出a > 100這個條件是否成立之前，無法確定接下來是應該執行x = 1 還是執行 y = 2。

為了解決這個問題，CPU可以簡單的讓流水線停頓一直到確定下一條要執行的指令，也可以采取如分支預測(branch prediction)和推測執行(speculation execution)等手段，但是，預測失敗的話，流水線往往會受到比較嚴重的性能懲罰。之后會有專門的文章分析這個問題，感興趣的話，可以右上角關注一下！

結構沖突

結構沖突，簡單來說，就是多條指令同時競爭同一個硬件資源，由于硬件資源短缺，無法同時滿足所有指令的執行請求。如兩條并行執行的命令需要同時訪問內存，而內存地址譯碼單元可能只有一個，這就產生了結構沖突。

有了上面這些基礎知識做鋪墊，接下來就可以開始真正分析這個問題了。

test.c為什么性能最差？

對于計算階乘，test.c可能是最簡單直觀、可讀性最強的算法。不過可惜的是，它也是性能最差的。

我們再看一下test.c的源碼：

說它性能最差，主要有三點原因：

1. 熱點路徑無用指令太多。
2. 熱點路徑跳轉指令太多。
3. 熱點路徑內存訪問太多。

注意，這里說的無用指令，是指對計算階乘本身不產生直接影響的指令，但是它們對整個算法的正確性仍然是必不可少的！

為例方便理解，我們來分別看下test.c不解優化選項和加了-O3編譯之后的匯編代碼。

test.c不加優化選項時

先是不加優化選項的：

綠色方框標注出來的8 ~ 14行是for循環，也就是主循環體。其中，藍色方框標注出來的8 ~ 11行是真正計算階乘的代碼，12 ~ 14行是循環控制代碼，對計算階乘來說，則是無用代碼。

不難看出：

1. 熱點路徑上，也就是循環體內無用指令占比是3/7 = 42%！即便在不考慮其他因素的情況下，CPU單單用來執行這些無用的指令，也是一筆不小的開銷！
2. 整個階乘計算過程中，循環體內需要執行1000000000次條件跳轉指令！條件跳轉又會造成控制沖突，使得流水線無法全速運行，從而造成巨大的性能損失。
3. 整個函數一共有10個內存訪問操作，而循環體內就有6個內存操作！盡管很多時候可以通過Cache來緩解，但相對與CPU計算速度來說，內存操作仍然是非常慢的，而且容易造成流水線沖突！

那加了-O3優化選項之后，編譯器能不能幫我們解決這些問題呢？

test.c加了-O3優化選項后

現在我們看下加了-O3之后的匯編代碼：

首先，不得不感嘆，現在的編譯器的優化真的是太強大了！直接把整個for循環優化成了4條指令！

不難看出，對于test.c而言，加了-O3之后，GCC做的最大的優化是把所有變量存放在寄存器中，消除了所有的內存訪問操作！

可以回過頭去看下優化之前的匯編代碼，整個函數一共有10個內存訪問操作，其中6個是在循環體內，而加了-O3之后，整個函數沒有任何內存訪問操作！難怪-O3編譯后性能提升那么多！由此可見，內存訪問相對寄存器訪問的開銷實在是太大了！當然，即便不使用-O3，也有優化內存操作的辦法，這個后面再講。

但是，也不難看出，對于其他兩個問題，GCC并沒有幫我們解決：現在無用指令占比是 2/4 = 50%! 整個階乘計算過程，仍然需要執行1000000000次條件跳轉指令，仍然無法充分發揮流水線和superscalar的指令并行執行能力！

知道了test.c性能差的原因之后，現在我們來看看，通過手動循環展開，test_2.c又幫我們解決什么問題呢？

test_2.c性能提升原因

再看下test_2.c的源碼：

通過對循環進行4次展開，之前每次循環執行1次乘法，現在每次循環執行4次，這就帶來了三點很重要的變化：

1. 循環次數減少了75%，無用指令減少了，相應的CPU執行這些指令本身的開銷也少了。
2. 計算過程中，熱點路徑的條件跳轉指令少了75%，這樣就減少了由于控制相關引起的流水線沖突，提升了流水線執行的效率。
3. 提升了指令的并行度，使得CPU superscalar的技術得到更充分的發揮，提高了每個時鐘周期并行執行指令的條數。

這也就是為什么在使用同樣的編譯選項時，test_2.c比test.c的性能提升了200%！不過，熱點路徑上內存訪問操作太多的問題仍然存在。其實，這個其實很好解決，我會在下文給出解決方法。我們先把注意里放在這里所說的三點變化上。

對于第1點和第2點，有了前面介紹的指令流水線的背景知識，即便從C語言的角度也很好理解，不需要過多解釋。

至于第3點，為了便于理解，我們和test_3.c對比來看。

test_3.c性能差的原因

再看下test_3.c的代碼:

test_3.c雖然也把循環進行了4次展開，但是展開的方式和test_2.c是不一樣的。

test_2.c是這樣展開的：

fact0 *= i;
fact1 *= i + 1;
fact2 *= i + 2;
fact3 *= i + 3;

而test_3.c則是這樣做的：

fact *= i;
fact *= i + 1;
fact *= i + 2;
fact *= i + 3;

很明顯，后面一條指令執行前，必須要先知道前面一條語句計算的結果。還記得前面講過的造成流水線沖突的三個原因嗎？這就是典型的數據依賴，會造成流水線沖突！

可見，雖然test_3.c也通過循環展開，減少了無用指令，也減少了熱點路徑上分支跳轉引起的流水線控制沖突，但它同時引入了數據依賴，進而導致流水線沖突，仍然無法發揮流水線和superscalar的指令級并行執行的能力！

這就是為什么，用同樣的選項編譯時，test_3.c雖然比未經過循環展開的test.c性能稍微提升了一點點，但相比同樣循環展開且沒有引入數據相關性的test_2.c來說，性能仍然是非常差的！

講到這里，本想演示下用perf測量出來的性能指標的，但由于篇幅過長，就不再展開討論了，以后會專門更新文章介紹perf相關工具的使用，感興趣的童鞋，歡迎右上角關注！

最后，來看一下前面遺留的那個問題：不加優化選項的情況下，怎么解決熱點路徑內存訪問過多的問題。

最后的殺手锏：優化熱點路徑內存訪問

其實很簡單，只需要把test_2.c中定義局部變量的時候加上register關鍵字就可以了：

C語言中，register關鍵字的作用是建議編譯器，盡可能地把變量存放在寄存器中，以加快其訪問速度。

我們現在看下，加了register關鍵字后，test_2.c的性能如何呢？

為方便對比，我們再看下添加register之前，test_2.c的耗時：

然后是加了register關鍵字之后的耗時：

看到差異了吧，相差3倍！加了register后，幾乎達到了和加-O3優化選項一樣的性能！

當然，register的使用還有很多限制，而且它只是給編譯器的一種建議，不是強制要求，編譯器只能盡量滿足，當變量太多，寄存器不夠用的時候，還是不得不把變量放到棧中，這和-O3的行為是一樣的。

register不是本文重點，限于篇幅，不在贅述，感興趣的童鞋可以留言討論或私信，如果感興趣童鞋比較多的話，我會專門更新一篇文章來講解register關鍵字，歡迎關注。

小結

循環展開是一種非常重要的優化方法，也是編譯器后端中常用的一種優化方式，它可以通過減少熱點路徑上的“無用指令”以及分支指令的個數，來更好地發揮CPU指令流水線的指令并行執行能力，從而提高程序整體性能。

很多時候，我們可以借助編譯器來幫我們實現這種優化，但編譯器也有失效的時候，比如文中這個例子。這時，我們就不得不手動來進行循環展開來優化程序性能。循環展開時，必須盡量減少語句間的相互依賴。

此外，循環展開的次數并沒有一個固定的公式，需要根據具體代碼和CPU來決定，通常需要多次嘗試來找到一個最優值。

不過，手動循環展開往往是以犧牲代碼可讀性為代價的，因此使用時也做好取舍。此外，循環展開還會在一定程度上增加程序代碼段的大小，還可能會影響到程序局部性，對cache產生影響，因此使用時候，要小心評估。

推薦閱讀

如果你對本文感興趣，那這一篇文章你肯定也會喜歡，介紹另外一種非常實用卻很少人知道的性能調優手段，強烈推薦：

<<改一行代碼，數組遍歷耗時從10.3秒降到0.5秒！>>

最近會更新一系列涉及CPU底層相關的文章，如Cache、指令流水線、分支預測、指令亂序、內存屏障等，如果對這些方面感興趣，歡迎右上角關注！

原創不易，別忘了留言點贊！右上角關注！有任何疑問或建議，歡迎留言、私信討論！