內聯快取

內聯快取是部分程式語言的執行時系統採用的最佳化技術，最早為Smalltalk開發。內聯快取的目標是透過記住以前直接在上方法查詢的結果來加快執行時方法繫結的速度。內聯快取對動態型別語言尤為有用，其中大多數方法繫結發生在執行時，因此通常無法使用。執行時方法繫結.下面的ECMAScript函式接收一個物件，呼叫其toString方法，並在指令碼嵌入的頁面上顯示結果。function dump(obj) {document.write(obj.toString());由於沒有指定物件的型別，並且有潛在的方法過載，所以不可能提前判斷toString方法被呼叫的具體實現，因而就必須在執行時執行動態查詢。在不採用某種形式快取的語言執行時中，每次呼叫方法都將執行該查詢。因為方法可能在多個繼承鏈下定義，所以動態查詢可能是一個昂貴的操作。為取得更好的效能，許多語言執行時採用某種形式的非內聯快取，其中將有限數量的方法查詢結果儲存在關聯資料結構中。這可以大大提高效能，只要執行的程式“快取友好”，即有一組經常被呼叫的方法。這個資料結構通常稱為第一級方法查詢快取。內聯快取.內聯快取的概念基於觀察到的經驗，即發生在特定呼叫點的物件通常是相同的型別。在這種情況下，儲存方法查詢內聯結果可以大幅提升效能，即直接抵達呼叫點。為做到這個過程，呼叫點會被分配不同的狀態。在最初，呼叫點被認作“未初始化”。當語言執行時到達特定的未初始化呼叫點，它會執行一次動態查詢，在呼叫點儲存結果並將其狀態改為“單態”。如果語言執行時再次來到相同的呼叫點，它接收此資訊並直接呼叫，不再執行任何查詢。考慮到同一呼叫點可能出現不同型別的物件，語言執行時也必須向程式碼插入。通常來說，這被插入到被叫方的前導程式碼而非呼叫點，以便更好利用分支預測器和節約空間，因為前導程式碼中的一個副本可以與多個呼叫點的副本關聯。如果處於“單態”狀態的呼叫站遇到期望型別之外的型別，則必須改回“未初始化”狀態並再次執行全動態查詢。典範實現是一個常量暫存器載入，後跟一個呼叫指令。“未初始化，而呼叫是查詢當前接收器的類中訊息的一個例程，採用上面提過的一級方法查詢快取。然後，執行時例程重寫指令，改變載入指令以載入具有當前接收器型別的暫存器，以及呼叫指令以呼叫目標方法的前導程式碼，將呼叫點“連結”到目標方法。隨後繼續立即執行前導程式碼。前導程式碼將匯出當前接收器的型別，並與暫存器中的型別比較；如果認可接收器為同一型別，則繼續執行該方法。如果不是，則前導程式碼再次呼叫執行時，並可能採用各種策略，其中一種是重新連結新的接收器型別的呼叫點。已隱藏部分未翻譯內容，歡迎參與[ 翻譯]。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 dispatch.單態內聯快取.如果一個特定呼叫點經常看到不同型別的物件，內聯快取的效能優勢很容易被呼叫點狀態的頻繁變化引起的開銷所抵消。以下示例構成單態內聯快取的最壞情況：var values = [1, "a", 2, "b", 3, "c", 4, "d"];for (var i in values) {document.write(values[i].toString());同樣，方法toString在一個無法事先預知型別的物件上呼叫。更重要的是，物件型別會隨著周遭迴圈的每一次迭代而改變。單態內聯快取的天真實現會因此不斷在“未初始化”與“單態”狀態之間轉換。為了防止這種情況發生，單態內聯快取的大多數實現支援第三種狀態，通常稱為“復態。多型內聯快取.為更好地處理經常看到有限數量不同型別的呼叫點，一些語言執行時採用稱為多型內聯快取”並且不再執行更多內聯快取。已隱藏部分未翻譯內容，歡迎參與[ 翻譯]。典範實現是 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 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%為單態。