編譯器，也就是將我們熟悉的高階語言，比如C++和OCaml，編譯為機器也能理解的程式碼。編譯器最佳化的好壞，會直接影響輸出程式碼的效能。我們知道編譯器自帶很多最佳化的手段，比如迴圈展開（loop unrolling）、公共子表示式消除（common subexpression elimination）等。這些都是比較標準的技巧，可以確認在任何情況下都能提高效能，對於任何程式碼都能進行，得到的效果也比較固定。

但除了這些純粹形式化的最佳化方法以外，編譯器也會使用一些“啟發式”的方法。經過這些方法調整過的程式碼，在機器上執行時，很多情況下會更快。

這是怎麼做到的呢？要說清楚，就要看看現代處理器的最佳化。

你可能會想，處理器還能有什麼最佳化呢？不就是從上往下一條一條執行彙編指令嗎，還能有什麼最佳化？

是的，但每一行彙編指令實際上都要完成幾項不同的工作：讀取資料，進行計算，設定flag，寫入暫存器或者記憶體，等等。每項工作使用的電路都不一樣，如果一條一條執行指令的話，每個瞬間就只有一部分在工作，極大地浪費了計算時間。

避免這種浪費的技術，就是耳熟能詳的流水線。

（圖片來自維基百科）

在流水線上，在每個瞬間都同時有幾條彙編指令在執行，但它們處於互不干擾的數個不同階段，這樣就既能有效利用所有的電路，又能保持指令之間的次序。

但流水線也有一個問題，就是分支指令。在分支指令執行完成之前，我們不知道下一步將要執行什麼程式碼。在這種情況下，我們似乎只能等待流水線上分支指令的完成，再繼續進行計算。因為一般的程式碼中含有大量的分支指令，所以這勢必會帶來巨大的效能損失。

工程師為了規避這個問題，提出了分支預測技術：在遇到分支指令時，不要等待分支指令的完成，而是根據程式碼的位置以及之前分支的結果，預判分支之後要執行的程式碼，然後投機性地執行這些程式碼。如果預判正確的話，就相當於分支完全沒有影響；但如果預判錯誤，就要將之前的計算結果全部丟棄，重新再來。也許你會覺得很浪費，但即使是預判錯誤，損失也只是相當於之前等待分支指令執行完成的損失。在通常的程式碼中，分支預測的準確性可以超過90%，所以基本上收益非常大。

分支預測，很多時候是一個機率性的事情，但編譯器也可以透過對程式碼的調整，比如具體分支方向的選擇和分支程式碼的refactoring，來幫助處理器更準確地進行分支預測。如果需要進行更精確的最佳化的話，可以透過profiling，記錄每一行程式碼執行的情況，以及每個分支的情況，然後讓編譯器根據實際執行的資料來進行程式碼調整，在最大程度上提升分支預測的準確性。