行內快取

行內快取（Inline caching）是部分程式語言的執行時系統採用的最佳化技術，最早為Smalltalk開發。行內快取的目標是通過記住以前直接在呼叫點上方法查詢的結果來加快執行時方法繫結的速度。行內快取對動態型別語言尤為有用，其中大多數（如非全部）方法繫結發生在執行時，因此虛方法表通常無法使用。

執行時方法繫結

下面的ECMAScript函式接收一個對象，呼叫其toString方法，並在指令碼嵌入的頁面上顯示結果。

function dump(obj) {
    document.write(obj.toString());
}

由於沒有指定對象的類型，並且有潛在的方法多載，所以不可能提前判斷toString方法被呼叫的具體實現，因而就必須在執行時執行動態查詢。在不採用某種形式快取的語言執行時中，每次呼叫方法都將執行該查詢。因為方法可能在多個繼承鏈下定義，所以動態查詢可能是一個昂貴的操作。

為取得更好的效能，許多語言執行時採用某種形式的非行內快取，其中將有限數量的方法尋找結果儲存在關聯資料結構中。這可以大大提高效能，只要執行的程式「快取友好」，即有一組經常被呼叫的方法。這個資料結構通常稱為第一級方法尋找快取（first-level method lookup cache）。

行內快取

行內快取的概念基於觀察到的經驗，即發生在特定呼叫點（call site）的對象通常是相同的類型。在這種情況下，儲存方法查詢行內結果可以大幅提升效能，即直接抵達呼叫點。為做到這個過程，呼叫點會被分配不同的狀態。在最初，呼叫點被認作「未初始化」。當語言執行時到達特定的未初始化呼叫點，它會執行一次動態查詢，在呼叫點儲存結果並將其狀態改為「單態」。如果語言執行時再次來到相同的呼叫點，它接收此資訊並直接呼叫，不再執行任何尋找。考慮到同一呼叫點可能出現不同類型的對象，語言執行時也必須向代碼插入守衛條件。通常來說，這被插入到被叫方的前導代碼而非呼叫點，以便更好利用分支預測器和節約空間，因為前導代碼中的一個副本可以與多個呼叫點的副本關聯。如果處於「單態」狀態的呼叫站遇到期望類型之外的類型，則必須改回「未初始化」狀態並再次執行全動態尋找。

典範實現是一個常數暫存器載入，後跟一個呼叫指令。「未初始化（uninitialized）」狀態稱為「未連結（unlinked）」更佳。暫存器載入了訊息選擇器（通常是某個對象的位址），而呼叫是尋找當前接收器的類中訊息的一個常式，採用上面提過的一級方法尋找快取。然後，執行時常式重寫指令，改變載入指令以載入具有當前接收器類型的暫存器，以及呼叫指令以呼叫目標方法的前導代碼，將呼叫點「連結」到目標方法。隨後繼續立即執行前導代碼。前導代碼將匯出當前接收器的類型，並與暫存器中的類型比較；如果認可接收器為同一類型，則繼續執行該方法。如果不是，則前導代碼再次呼叫執行時，並可能採用各種策略，其中一種是重新連結新的接收器類型的呼叫點。

已隱藏部分未翻譯內容，歡迎參與翻譯。

The performance gains come from having to do one type comparison, instead of at least a type comparison and a selector comparison for the first-level method lookup cache, and from using a direct call (which will benefit from instruction prefetch and pipe-lining) as opposed to the indirect call in a method-lookup or a vtable dispatch.

單態行內快取

如果一個特定呼叫點經常看到不同類型的對象，行內快取的效能優勢很容易被呼叫點狀態的頻繁變化引起的開銷所抵消。以下範例構成單態行內快取的最壞情況：

var values = [1, "a", 2, "b", 3, "c", 4, "d"];
for (var i in values) {
    document.write(values[i].toString());
}

同樣，方法toString在一個無法事先預知類型的對象上呼叫。更重要的是，對象類型會隨著周遭迴圈的每一次迭代而改變。單態行內快取的天真實現會因此不斷在「未初始化」與「單態」狀態之間轉換。為了防止這種情況發生，單態行內快取的大多數實現支援第三種狀態，通常稱為「復態（megamorphic）」狀態。當某個特定呼叫點看到預定數量的不同類型時則會進入該狀態。一旦某個呼叫點進入「復態」狀態，它就會像「未初始化」狀態那樣表現，除了它不會再進入「單態」狀態（某些單態行內快取的實現會在一段時間或者執行一次完整的垃圾回收周期後將「復態」呼叫點改回「未初始化」狀態）。

多型行內快取

為更好地處理經常看到有限數量不同類型的呼叫點，一些語言執行時採用稱為多型行內快取（polymorphic inline caching）的技術。通過多型行內快取，一旦處於其「單態」狀態的呼叫點看到第二種類型，它不會迴轉到「未初始化」狀態，而是切換到稱為「多型」的新狀態。多型呼叫點根據當前呈遞的類型決定呼叫已知、有限的某一種方法。換句話說，通過多型行內快取可以在同一個呼叫點記錄多個方法尋找結果。由於程式中的每個呼叫點都可能會看到系統中的每個類型，因此每個呼叫點上的記錄上限通常是尋找結果的上限。一旦達到上限，呼叫點就變成「復態（megamorphic）」並且不再執行更多行內快取。

已隱藏部分未翻譯內容，歡迎參與翻譯。

典範實現是 is a jump table which consists of a preamble that derives the type of the receiver and a series of constant compares and conditional jumps that jump to the code following the preamble in the relevant method for each receiver type. The jump table is typically allocated for a particular call-site when a monomorphic call-site encounters a different type. The jump-table will have a fixed size and be able to grow, adding cases as new types are encountered up to some small maximum number of cases such as 4, 6 or 8. Once it reaches its maximum size execution for a new receiver type will "fall-off" the end and enter the run-time, typically to perform a method lookup starting with the first-level method cache. The observation that together, monomorphic and polymorphic inline caches collect per-call-site receiver type information as a side-effect of optimizing program execution led to the development of adaptive optimization in Self, where the run-time optimizes "hot spots" in the program using the type information in inline caches to guide speculative inlining decisions.

變形行內快取

如果執行時同時採用單態和多型行內快取，那麼在穩定狀態下，唯一的未連結的傳送將是來自多型行內快取結束的傳送falling-off。由於這種傳送速度很慢，因此最佳化這些網站現在可能比較有收益。建立代碼來執行特定呼叫點的一級方法尋找可以實現一個單態行內快取。在這個方案中，一旦一個send falls-off在一個多型行內快取的末尾，就會建立一個特定於呼叫點的選擇器的高速緩衝記憶體（如果已存在則共享），並且傳送站點被重新連結來呼叫它。這樣的代碼可以比普通的一級方法查詢探測器更有效率，因為選擇器現在是一個常數，可以降低暫存器壓力，查詢和呼叫代碼的執行無需進入執行時，並且排程可以從分支預測器中受益。

根據測量顯示，在大型Smalltalk程式中，所有活動方法的傳送點有大約1/3維持未連結，其餘2/3中，90%為單態（monomorphic），9%為多型（polymorphic），1%（準確來說0.9%）為復態（megamorphic）。

參見

• 記憶化（memoization）

外部連結

• Article on Inline Caching in the Cog Smalltalk VM （頁面存檔備份，存於網際網路檔案館）