分支預測與誤測懲罰（branch prediction and the misprediction penalty）

一個管線化的中央處理器在執行指令之前許多週期就先抓取它們，但分支（一個 if、一個迴圈判斷、一次函式指標呼叫）製造了難題：在分支的條件被算出之前，中央處理器還不知道接下來是哪些指令。乾等答案會讓整條管線在每個分支上閒置——而分支無所不在，大約每五條指令就有一個。所以中央處理器不等。它用一塊叫做分支預測器的硬體去「猜」，並沿著猜中的路徑推測性地繼續抓取。

分支預測器從一個分支的歷史學習模式，為每個分支預測它會不會被採取（taken），並透過分支目標緩衝區（BTB）預測它會跳到哪個位址。現代預測器好得驚人——在典型程式上準確率遠高於 95%——因為大多數分支高度規律（迴圈除了最後一次外每次都被採取；錯誤檢查幾乎從不被採取）。當預測正確時，被推測抓取的指令正是正確的那些，幾乎零成本：那個分支實質上免費。當預測「錯誤」時，沿著錯誤路徑抓取與執行的一切都必須丟棄——管線被清空（flush）——並從正確的目標重新開始抓取。那次清空就是分支誤測懲罰，在深管線上典型為 15 到 20 多個浪費掉的週期，因為那正是有多少正在途中的階段被丟掉。

這種不對稱——預測正確的分支幾乎免費、誤測的分支卻要付一次深度清空——正是讓分支行為成為真實效能因素的原因。一個難以預測的分支（在沒有可學習模式下大約一半一半往兩邊走的，典型是對隨機或未排序資料分支）可能比可預測的貴上一個數量級，這正是「處理已排序資料可能比同樣的程式跑在打亂的資料上快得多」的著名原因。這也是為何存在無分支程式：當一個分支真的不可預測時，把它換成無分支的算術，就完全消除了誤測風險。