內聯快取

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

基本介紹

  • 中文名:內聯快取
  • 外文名:Inline caching
  • 性質最佳化技術
  • 領域:計算機
運行時方法綁定,內聯快取,單態內聯快取,多態內聯快取,變形內聯快取,

運行時方法綁定

下面的ECMAScript函式接收一個對象,調用其toString方法,並在腳本嵌入的頁面上顯示結果。
function dump(obj) {    document.write(obj.toString());}
由於沒有指定對象的類型,並且有潛在的方法重載,所以不可能提前判斷toString方法被調用的具體實現,因而就必須在運行時執行動態查詢。在不採用某種形式快取的語言運行時中,每次調用方法都將執行該查詢。因為方法可能在多個繼承鏈下定義,所以動態查詢可能是一個昂貴的操作。
為獲取更好的性能,許多語言運行時採用某種形式的非內聯快取,其中將有限數量的方法查找結果存儲在關聯數據結構中。這可以大大提高性能,只要執行的程式“快取友好”,即有一組經常被調用的方法。這個數據結構通常稱為第一級方法查找快取(first-level method lookup cache)。

內聯快取

內聯快取的概念基於觀察到的經驗,即發生在特定調用點(call site)的對象通常是相同的類型。在這種情況下,存儲方法查詢內聯結果可以大幅提升性能,即直接抵達調用點。為做到這個過程,調用點會被分配不同的狀態。在最初,調用點被認作“未初始化”。當語言運行時到達特定的未初始化調用點,它會執行一次動態查詢,在調用點存儲結果並將其狀態改為“單態”。如果語言運行時再次來到相同的調用點,它接收此信息並直接調用,不再執行任何查找。考慮到同一調用點可能出現不同類型的對象,語言運行時也必須向代碼插入守衛條件。通常來說,這被插入到被叫方的前導代碼而非調用點,以便更好利用分支預測器和節約空間,因為前導代碼中的一個副本可以與多個調用點的副本關聯。如果處於“單態”狀態的調用站遇到期望類型之外的類型,則必須改回“未初始化”狀態並再次執行全動態查找。
典範實現是一個常量暫存器載入,後跟一個調用指令。“未初始化(uninitialized)”狀態稱為“未連結(unlinked)”更佳。暫存器載入了訊息選擇器(通常是某個對象的地址),而調用是查找當前接收器的類中訊息的一個例程,採用上面提過的一級方法查找快取。然後,運行時例程重寫指令,改變載入指令以載入具有當前接收器類型的暫存器,以及調用指令以調用目標方法的前導代碼,將調用點“連結”到目標方法。隨後繼續立即執行前導代碼。前導代碼將導出當前接收器的類型,並與暫存器中的類型比較;如果認可接收器為同一類型,則繼續執行該方法。如果不是,則前導代碼再次調用運行時,並可能採用各種策略,其中一種是重新連結新的接收器類型的調用點。

單態內聯快取

如果一個特定調用點經常看到不同類型的對象,內聯快取的性能優勢很容易被調用點狀態的頻繁變化引起的開銷所抵消。以下示例構成單態內聯快取的最壞情況:
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)”並且不再執行更多內聯快取。

變形內聯快取

如果運行時同時採用單態和多態內聯快取,那么在穩定狀態下,唯一的未連結的傳送將是來自多態內聯快取結束的傳送falling-off。由於這種傳送速度很慢,因此最佳化這些網站現在可能比較有收益。創建代碼來執行特定調用點的一級方法查找可以實現一個單態內聯快取。在這個方案中,一旦一個send falls-off在一個多態內聯快取的末尾,就會創建一個特定於調用點的選擇器的高速快取(如果已存在則共享),並且傳送站點被重新連結來調用它。這樣的代碼可以比普通的一級方法查詢探測器更有效率,因為選擇器現在是一個常量,可以降低暫存器壓力,查詢和調用代碼的執行無需進入運行時,並且調度可以從分支預測器中受益。
根據測量顯示,在大型Smalltalk程式中,所有活動方法的傳送點有大約1/3維持未連結,其餘2/3中,90%為單態(monomorphic),9%為多態(polymorphic),1%(準確來說0.9%)為復態(megamorphic)。

相關詞條

熱門詞條

聯絡我們