跳轉到

4.3 內嵌快取與形態推測優化（Self 的 inline cache）#

問題：動態分派的代價#

在動態語言中，receiver.draw() 這一行的成本由分派語義決定：查 receiver 的類別 → 查其方法表 → 未命中則沿繼承鏈上溯。Smalltalk-80 的解法是全域方法快取（把 selector+class 的查詢結果集中快取），但 1984 年 Deutsch 與 Schiffman 指出更好的辦法：把快取放在呼叫點本身。這就是內嵌快取（inline cache, IC）——名字借自硬體的快取概念，但快取的是「軟體查表」的結果，而且直接內嵌在生成碼中。

Self 團隊（Ungar、Chambers、Hölzle，1987-1995）把這個想法推到極致，因為 Self 沒有類別、物件可隨時改形，分派壓力最大。其成果成為今日 V8、JVM、.NET、LuaJIT 中多型分派解決方案的共同祖先。

三代 inline cache#

第一代：單形 IC（monomorphic IC）。呼叫點只記得最後見過的型別。以偽機器碼表示：

CALL_SITE:
  cmp  receiver_class, [cached_class]   ; 型別符合嗎？
  jne  miss_handler                     ; 不符 -> 查表並更新快取
  call [cached_target]                  ; 直呼上次解析出的目標

命中時只需一次比較＋一次間接呼叫，把 O(查表) 降為 O(1)。未命中時由執行時期查表、更新快取（自修改程式碼）並照常呼叫——這是「樂觀假設 + 退路」的最小實例。

第二代：多形 IC（polymorphic IC）。若一個呼叫點常見多個型別（例如迴圈中交替處理 Circle 與 Square），單形 IC 會持續 miss。多形 IC 改為一串比較：

  cmp  rc, [class1]; je call1
  cmp  rc, [class2]; je call2
  cmp  rc, [class3]; je call3
  jmp megamiss_handler

呼叫點維護一個小型陣列（V8 通常上限 4 個，超過即稱 megamorphic）。硬體視角：這串比較對分支預測器極友善，因為型別序列有強烈的局部性。

第三代：內聯化與呼叫點內的 IC。IC 的真正威力在於它不只是快取，更是優化的資訊來源：多形 IC 中每個 (型別 → 目標) 對應關係，正是 JIT 編譯該方法時需要的 profile。編譯器把每個目標方法內聯到呼叫點、以型別比較作守衛，得到：

  cmp rc, Point ; je <inlined Point::draw>
  cmp rc, Circle; je <inlined Circle::draw>
  jmp deoptimize

這使「動態呼叫」在熱路徑上完全消失，內聯又打開常數傳播、逃逸分析等後續優化的空間——4.1 節所說的「內聯—特化乘數效應」在此具體化。

隱藏類別（Hidden Classes / Shapes）：JavaScript 的答案#

JavaScript 比自省的 Smalltalk 更惡劣：物件是字典，隨時可以加刪屬性，obj.x 是雜湊查詢。V8（Lars Bak 團隊，2008）以隱藏類別（hidden class，學界稱 shape/map）解決：每個物件內部藏一個指向其 shape 的指標，shape 描述屬性名到偏移的佈局；物件以相同順序加相同屬性時共享同一 shape。於是 obj.x 變成「比對 shape → 依常數偏移讀取」，完美套用 IC：

  cmp [obj.shape], cached_shape
  jne  miss
  mov  eax, [obj + offset_x]     ; 直接以常數偏移取值

這是把「Self 的形態推測」翻譯成「JavaScript 的物件模型」的教科書案例。後續 React 工程（Inline Caches 的滥用如 map-check 消除、 TurboFan 對 IC feedback 的使用）、以及 SpiderMonkey 的 shape 系統、Ruby 的 YJIT（2022 起，Shopify 與 Ruby 團隊）都是此路線的後裔。YJIT 甚至展示了另一個教訓：在 IR 層面直接實作 IC（把 IC 表示為 SSA 值與守衛）比傳統「runtime patching」更易維護與優化，這是對二十年 IC 實作經驗的簡化回歸。

形態推測的其他應用#

形態推測不只服務呼叫分派：

  • 型別特化的算術：JavaScript 的 + 可能是數字加法或字串串接。引擎觀測後為「double+double」生成專用碼，守衛檢查運算元是否皆為數（NaN boxing、Smi tagging 等值表示法與此密切相關）。
  • 陣列元素形態：V8 為 packed double array 與一般 object array 建立不同的內部表示，依觀測形態特化 a[i] 的存取碼。
  • 逃逸分析的形態前提：「物件不逃逸」的判斷依賴對呼叫點形態的推測（若被呼叫方法可能把 this 存起來，標量替換就不安全）。
  • Java 世界的對應物：HotSpot 的 speculative widening（如根據 profile 把 Object 推測成 ArrayList 以消除強制轉型檢查）、以及 C2 的 div by constant、null check elimination 等，同樣建立在「profile + guard + deopt」的骨架上。

正確性：失效與去優化#

形態推測的正確性依賴失效機制：當程式執行「改變形態」的操作（Self/JS 修改物件結構、Java 動態載入新子類別推翻單實作假設），VM 必須找到所有受影響的 IC 與已編譯碼，使其失效（去優化或回退為未特化版本）。實作上依賴依賴圖（dependency graph）：編譯時登記「此編譯碼依賴 class C 無新子類」等假設，執行期違約時遍歷該圖觸發失效。這個機制與 2.3 節的類別載入、4.2 節的去優化互相鎖定，構成動態優化的正確性閉環。

小結#

內嵌快取把硬體快取的思想移植到軟體分派：以呼叫點為快取單位、以執行歷史為預測依據、以守衛與去優化為保險絲。它與分代 GC、分層 JIT 並列為現代高效 VM 的三大支柱技術，且三者共享同一設計哲學——用觀測到的形態把不確定性轉化為可優化的靜態假設。