內聯緩存

內聯緩存（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 （頁面存檔備份，存於網際網路檔案館）