V8 - Inline Caching

TL;DR

Inline caching ở trong V8 hoặc động dựa trên việc quan sát các lời gọi hàm lặp lại mà sử dụng cùng một kiểu dữ liệu của object.

Một cách kỹ thuật, V8 lưu trữ hidden class của object được dùng làm đối số trong những lần gọi hàm gần nhất vào bộ nhớ đệm và sử dụng thông tin trong đó để giả định hidden class của object sẽ được truyền vào hàm trong những lần gọi hàm tiếp theo. Nếu việc giả định này là đúng, V8 không cần phải xác định cách truy xuất thuộc tính của object mà chỉ cần dùng thông tin từ những lần truy xuất trước đó trên hidden class của object.

Cụ thể, khi có nhu cầu truy xuất thuộc tính, V8 sẽ tìm trong hidden class của object để xác định offset của thuộc tính. Sau một lần gọi hàm trên một hidden class, V8 sẽ bỏ qua bước tìm trong hidden class mà cộng trực tiếp offset của thuộc tính vào con trỏ của object dựa trên offset thu được ở lần gọi hàm trước đó.

Info

Inline cache không chỉ được áp dụng cho các lời gọi hàm mà còn có thể được áp dụng cho các toán tử chẳng hạn như +, -, *, / hoặc thậm chí cho việc thao tác với DOM.

Nếu chúng ta sử dụng hai object có cùng kiểu dữ liệu (cùng class) nhưng khác hidden class, V8 sẽ không thể sử dụng inline caching do offset của các thuộc tính là khác nhau:

Trong trường hợp đó, V8 sẽ deoptimize code¹ và thực hiện tìm trong hidden class mỗi khi cần truy xuất thuộc tính.

V8 Implementation

Để triển khai inline caching, V8 sẽ biên dịch những hàm truy xuất thuộc tính thành một hàm chuyên biệt mà ghi nhớ hidden class của object và offset của thuộc tính (đây cũng là lý do mà nó được gọi là inline caching). Cụ thể hơn, sau một lần truy xuất thuộc tính P thông qua một hàm không chuyên biệt, V8 sẽ dùng hidden class và offset mà nó đã lưu để biên dịch ra một hàm chuyên biệt và thay thế trong mã nguồn những chỗ có truy xuất đến thuộc tính P (cơ chế này còn được gọi là patching - vá).

Hàm chuyên biệt sẽ thực hiện việc kiểm tra hidden class của object mà cần truy cập thuộc tính. Nếu hidden class không khớp, hàm chuyên biệt sẽ bị chuyển lại thành hàm không chuyên biệt. Ngược lại, nó sẽ sử dụng offset mà nó đã lưu để trả về giá trị.

Simulation in JavaScript

Xét đoạn script sau:

function CheckResult(sum) {
  var x = LOAD(sum, 'x');
  var y = LOAD(sum, 'y');
  if (x !== 50000 || y !== -50000) {
    throw new Error("failed: x = " + x + ", y = " + y);
  }
}

Trình biên dịch ban đầu sẽ biên dịch thao tác truy xuất thuộc tính thành các hàm không chuyên biệt (không ghi nhớ hidden class của object và offset của thuộc tính):

var LOAD$13 = NAMED_LOAD_MISS;
var LOAD$14 = NAMED_LOAD_MISS;
 
function CheckResults(sum) {
  var x = LOAD$13(sum, 'x', 13);
  var y = LOAD$14(sum, 'y', 14);
  if (x !== 50000 || y !== -50000) throw new Error("failed x: " + x + ", y:" + y);
}

Mỗi thuộc tính sẽ có một hàm dùng để truy xuất riêng (do nếu hàm không chuyên biệt được biên dịch thành hàm chuyên biệt thì thông tin về offset của từng thuộc tính trong từng hàm là khác nhau).

Hàm NAMED_LOAD_MISS có dạng như sau:

function NAMED_LOAD_MISS(t, k, ic) {
  var v = LOAD(t, k);
  if (t.klass.kind === "fast") {
    // Create a load stub that is specialized for a fixed class and key k and
    // loads property from a fixed offset.
    var stub = CompileNamedLoadFastProperty(t.klass, k);
    PatchIC("LOAD", ic, stub);
  }
  return v;
}

Hàm LOAD(t, k) được gọi đến sẽ tiếp tục gọi hàm t.load(k) để truy xuất thuộc tính:

function LOAD(t, k) {
  CHECK_TABLE(t);
  return t.load(k);
}

Hàmt.load(k) là một hàm không chuyên biệt do nó cần phải đi tìm offset của thuộc tính.

Sau khi NAMED_LOAD_MISS được gọi lần đầu tiên, V8 sẽ tiến hành biên dịch ra một hàm chuyên biệt thông qua hàm CompileNamedLoadFastProperty và thay thế hàm không chuyên biệt bằng hàm chuyên biệt.

Hàm biên dịch có dạng như sau:

function CompileNamedLoadFastProperty(klass, key) {
  // Key is known to be constant (named load). Specialize index.
  var index = klass.getIndex(key);
 
  function KeyedLoadFastProperty(t, k, ic) {
    if (t.klass !== klass) {
      // Expected klass does not match. Can't use cached index.
      // Fall through to the runtime system.
      return NAMED_LOAD_MISS(t, k, ic);
    }
    return t.properties[index];  // Veni. Vidi. Vici.
  }
 
  return KeyedLoadFastProperty;
}

Do tính closure trong JavaScript, biến index khi được tham chiếu bởi một hàm bên trong thì nó sẽ không kết thúc vòng đời khi hàm CompileNamedLoadFastProperty kết thúc. Việc sử dụng closure như vậy giúp minh họa cách mà V8 lưu offset của thuộc tính ngay bên trong hàm.

Hàm KeyedLoadFastProperty lồng bên trong chính là hàm chuyên biệt mà ta cần thay thế cho hàm không chuyên biệt. Có thể thấy, hàm KeyedLoadFastProperty sẽ thực hiện việc kiểm tra hidden class và nếu như hidden class không khớp thì nó sẽ hạ cấp xuống hàm không chuyên biệt. Ngược lại, KeyedLoadFastProperty sẽ trả về giá trị của thuộc tính ngay lập tức thông qua index mà nó đã lưu.

Generated Code

Xét đoạn script sau:

function getX(obj) {
  return obj.x;
}

Minh họa bytecode của hàm chuyên biệt cho đoạn script trên:

0x28c500002194 @    0 : 65 af 01 03 01    CallRuntime [DebugPrint], a0-a0
0x28c500002199 @    5 : 2d 03 00 00       GetNamedProperty a0, [0], [0]
0x28c50000219d @    9 : ab                Return

Với GetNamedProperty là bytecode dùng để truy xuất một named property. Hai toán hạng theo sau đó lần lượt là địa chỉ của hidden class và giá trị của offset ở trong descriptors.

Minh họa mã nguồn hợp ngữ của hàm chuyên biệt:

Với “object check” là để kiểm tra xem con trỏ có phải là địa chỉ của object hay không (con trỏ trong V8 là một giá trị 32-bit với bit cuối là 1) và generic loopkup chính là tên gọi của hàm không chuyên biệt.

Deoptimization

Việc kiểm tra hidden class của object (class check) trước khi thực hiện thao tác được gọi là type guard và việc hạ cấp xuống hàm không chuyên biệt nếu như object không thỏa type guard được gọi là deoptimization.

Deoptimization còn có thể xảy ra trong một số trường hợp khác chẳng hạn như kết quả của thao tác bị tràn số hoặc thao tác đang cố gắng truy cập đến một phần tử arr[idx] với idx lớn hơn hoặc bằng kích thước của arr (out-of-bound access).

States

Inline cache có 3 trạng thái:

Chưa khởi tạo (uninitialized)
Đơn hình (monomorphic)
Siêu hình (megamorphic)

Monomorphic

Trạng thái thứ 2 xảy ra khi inline cache chỉ lưu thông tin về duy nhất một hidden class. Ví dụ:

function f(o) {
  return o.x
}
 
f({ x: 1 })
f({ x: 2 })

Polymorphhic

Tuy nhiên, nếu như có một lần gọi hàm nào đó mà đối số có hidden class khác với hidden class của những lần trước đó, trạng thái của inline cache sẽ chuyển sang polymorphhic (đa hình).

Trong ví dụ bên dưới, trạng thái của inline cache là đa hình cấp 2:

f({ x: 3 })
// o.x cache is still monomorphic here
f({ x: 3, y: 1 })
// what about now?

Khi trạng thái chuyển sang đa hình, V8 cần phải duyệt tuyến tính qua inline cache để tìm ra hidden class khớp với object mỗi lần cần truy cập thuộc tính.

Megamorphic

Nếu ta tiếp tục gọi hàm với những hidden class khác, cấp đa hình sẽ gia tăng:

f({ x: 4, y: 1 }) // polymorphic, degree 2
f({ x: 5, z: 1 }) // polymorphic, degree 3
f({ x: 6, a: 1 }) // polymorphic, degree 4
f({ x: 7, b: 1 }) // megamorphic

Đến một cấp đa hình nhất định nào đó (thường là giới hạn hidden class tối đa của inline cache), V8 sẽ chuyển sang trạng thái megamorphic và dừng lưu vào inline cache. Thay vào đó, nó sẽ lưu vào một global hashtable.

Tất nhiên, việc sử dụng bảng băm làm bộ đệm sẽ cho ra tốc độ truy xuất cực kỳ chậm. Tuy nhiên, điều này vẫn là tốt hơn IC miss (xảy ra khi thao tác truy xuất không có inline cache và cần phải thực hiện generic lookup).

Debug with D8

Xét đoạn script sau:

function getX(obj) {
  return obj.x;
}
 
for (let i = 0; i < 10; i++) {
  getX({ x: i });
}

Để hiển thị ra thông tin về inline cache, chúng ta có thể dùng option --log-ic. Option này sẽ tạo ra file v8.log và có thể được phân tích bởi công cụ Indicium (System Analyzer).

Danh sách inline cache (IC) mà công cụ hiển thị:

Grouped by type: 1#
100.00%	1	LoadIC
Grouped by category: 1#
100.00%	1	Load
Grouped by functionName: 1#
100.00%	1	~getX
Grouped by script: 1#
100.00%	1	Script(3): log-ic.js
Grouped by sourcePosition: 1#
100.00%	1	log-ic.js:2:14
Grouped by code: 1#
100.00%	1	Code(JS~)
Grouped by state: 1#
100.00%	1	0 → 1
Grouped by key: 1#
100.00%	1	x
Grouped by map: 1#
100.00%	1	Map(0x2560000da9e1)
Grouped by reason: 1#
100.00%	1

Danh sách trên có một inline cache là LoadIC, được dùng để truy xuất thuộc tính của object thông qua cache. Một số thông tin liên quan:

Tên hàm sử dụng nó: functionName: ~getX.
Địa chỉ của hidden class: Map(0x2560000da9e1).
Tên thuộc tính cần truy xuất: key: x

Thông tin quan trọng trong danh sách tên là state: 0 -> 1.

Tất cả các trạng thái của inline cache có trong mã nguồn của V8 là:

// State for inline cache call sites. Aliased as IC::State.
enum class InlineCacheState {
  // No feedback will be collected.
  NO_FEEDBACK,
  // Has never been executed.
  UNINITIALIZED,
  // Has been executed and only one receiver type has been seen.
  MONOMORPHIC,
  // Check failed due to prototype (or map deprecation).
  RECOMPUTE_HANDLER,
  // Multiple receiver types have been seen.
  POLYMORPHIC,
  // Many DOM receiver types have been seen for the same accessor.
  MEGADOM,
  // Many receiver types have been seen.
  MEGAMORPHIC,
  // A generic handler is installed and no extra typefeedback is recorded.
  GENERIC,
};

Đối với Indicium, nó biểu diễn các trạng thái trên bằng các ký hiệu như sau:

0: UNINITIALIZED
X: NO_FEEDBACK
1: MONOMORPHIC
^: RECOMPUTE_HANDLER
P: POLYMORPHIC
N: MEGAMORPHIC
D: MEGADOM
G: GENERIC

Như vậy, thông tin state: 0 -> cho ta biết rằng trạng thái của inline cache đã chuyển từ chưa khởi tạo (0) sang đơn hình (1).

Info

Trạng thái NO_FEEDBACK cho biết rằng hàm chưa được thu thập đủ các thông tin thống kê để được đưa vào hàng đợi của optimizing compiler.

Nếu chúng ta sử dụng nhiều hơn 1 hidden class:

function getX(obj) {
  return obj.x; // Polymorphic IC
}
 
for (let i = 0; i < 10; i++) {
  getX({ x: i, y: 0 });
  getX({ y: 0, x: i });
}

Thì LoadIC sẽ có dạng như sau:

Grouped by type: 2#
100.00%	2	LoadIC
Grouped by category: 2#
100.00%	2	Load
Grouped by functionName: 2#
100.00%	2	~getX
Grouped by script: 2#
100.00%	2	Script(3): log-ic.js
Grouped by sourcePosition: 2#
100.00%	2	log-ic.js:2:14
Grouped by code: 2#
100.00%	2	Code(JS~)
Grouped by state: 2#
50.00%	1	0 → 1
50.00%	1	1 → P
Grouped by key: 2#
100.00%	2	x
Grouped by map: 2#
50.00%	1	Map(0x378d000dab1d)
50.00%	1	Map(0x378d000daa3d)
Grouped by reason: 2#
100.00%	2

Có thể thấy, trạng thái của nó chuyển từ 0 sang 1 và 1 sang P (đa hình).

Như đã đề cập, trạng thái đa hình có một giới hạn về số lượng hidden class tối đa, mà cụ thể là 4 như được khai báo ở trong mã nguồn của V8:

// Maximum number of call targets tracked per call.
constexpr int kMaxPolymorphism = 4;

Tip

Chúng ta có thể chỉnh giới hạn này thông qua option --max-valid-polymorphic-map-count.

Speculative Optimizations

Thay vì biên dịch code một cách tối ưu rồi chạy, V8 chờ các đoạn code “làm nóng” (được thực thi nhiều lần) rồi mới tiến hành tối ưu. Việc này mang lại các lợi ích sau:

Giảm thời gian khởi động: do optimizing compiler chậm hơn rất nhiều so với non-optimizing compiler nên các đoạn code cần phải được sử dụng đủ nhiều để được tối ưu. Khi thỏa mãn được điều kiện này thì hàm sẽ được đưa vào hàng đợi của optimizing compiler.
Giúp có thêm thời gian thu thập các phản hồi về kiểu dữ liệu (type feedback) - chính là các hidden class mà sẽ được lưu ở trong inline cache.

Intermediate Representation (IR)

Như đã đề cập, các hàm chuyên biệt (inline cache stub) giúp truy cập và ghi thuộc tính nhanh nhờ vào inline cache. Cụ thể, các hàm này đã được optimizing compiler biên dịch ra ở dạng biểu diễn trung gian (Intermediate Representation - IR).

Sau khi biên dịch ra IR, optimizing compiler sẽ loại bỏ những instruction dư thừa. Một trong số những dư thừa phổ biến là các type guard bị lặp lại.

Ví dụ, xét đoạn script sau:

function g(o) {
  return o.x * o.x + o.y * o.y
}
 
g({x: 0, y: 0})

Đoạn script trên sẽ có 7 inline cache tương ứng với các thao tác:

Truy xuất thuộc tính x và y
Nhân hai số
Cộng hai số

Có thể thấy, do hoạt động độc lập với nhau, các inline cache bị dư thừa. Cụ thể:

Inline cache dùng để truy cập thuộc tính x và y bị lặp lại 2 lần.
Inline cache của toán tử + sẽ kiểm tra kiểu dữ liệu của đối số có phải là số hay không (hoặc kiểm tra xem nó là dạng số gì), mặc dù những thông tin này đã được suy ra từ inline cache của toán tử * trước đó.

IR ban đầu của đoạn script là:

	CheckMap v0, {x,y}  ;; shape check 
v1	Load v0, @12        ;; load o.x 
	CheckMap v0, {x,y} 
v2	Load v0, @12        ;; load o.x 
i3	Mul v1, v2          ;; o.x * o.x 
	CheckMap v0, {x,y} 
v4	Load v0, @16        ;; load o.y 
	CheckMap v0, {x,y} 
v5	Load v0, @16        ;; load o.y 
i6	Mul v4, v5          ;; o.y * o.y 
i7	Add i3, i6          ;; o.x * o.x + o.y * o.y

Optimizing compiler sẽ sử dụng GVN (Global Value Numbering) để loại bỏ những instruction dư thừa:

	;; After GVN 
	CheckMap v0, {x,y} 
v1	Load v0, @12 
i3	Mul v1, v1 
v4	Load v0, @16 
i6	Mul v4, v4 
i7	Add i3, i6

Note

Chú ý rằng việc loại bỏ những instruction dư thừa chỉ khả thi nếu không có các instruction gây ra các side-effect (chẳng hạn như làm thay đổi hidden class của v0).

Decision Tree

Việc xử lý các thao tác không phải là đơn hình (non-monomorphic) bởi optimizing compiler được thực hiện bằng cách xây dựng cây quyết định. Ví dụ, thao tác truy cập thuộc tính o.x mà liên quan đến ba hidden class sẽ được optimizing compiler xử lý như sau:

var o_x
if ($GetShape(o) === A) {
  o_x = $LoadByOffset(o, offset_A_x)
} else if ($GetShape(o) === B) {
  o_x = $LoadByOffset(o, offset_B_x)
} else if ($GetShape(o) === C) {
  o_x = $LoadByOffset(o, offset_C_x)
} else {
  // o.x saw only A, B, C so we assume
  // there can be *nothing* else
  $Deoptimize()
}
// Note: at this point we can only say that
// o is either A, B or C. But we lost information
// which one.

Note

Đoạn code trên chỉ là mã giả. Trong thực tế, optimizing compiler sẽ xây dựng một control flow graph (CFG).

Do có nhiều hidden class, optimizing compiler sẽ không thể thực hiện việc loại bỏ những IR instruction dư thừa. Thay vào đó, V8 sẽ cố gắng xây dựng một IR tối ưu nếu thuộc tính nằm ở cùng một offset ở tất cả các hidden class:

// Check that o's shape is one of A, B or C - deoptimize otherwise.
$TypeGuard(o, [A, B, C])
// Load property. It's in the same place in A, B and C.
var o_x = $LoadByOffset(o, offset_x)

Trong trường hợp siêu hình (megamorphic), optimizing compiler sẽ xây dựng cây quyết định khác đi một chút bằng cách gọi generic lookup ở trong khối lệnh của else thay vì thực hiện deoptimiztion (chuyển hoàn toàn hàm được sử dụng ở trong code thành generic lookup cho những lần thực thi sau):

var o_x
if ($GetShape(o) === A) {
  o_x = $LoadByOffset(o, offset_A_x)
} else if ($GetShape(o) === B) {
  o_x = $LoadByOffset(o, offset_B_x)
} else if ($GetShape(o) === C) {
  o_x = $LoadByOffset(o, offset_C_x)
} else {
  // We know that o.x is too polymorphic (megamorphic).
  // to avoid deoptimizations leave escape hatch to handle
  // arbitrary object:
  o_x = $LoadPropertyGeneric(o, 'x')
  //    ^^^^^^^^^^^^^^^^^^^^ arbitrary side effects
}
// Note: at this point nothing is known about
// o's shape and furthermore arbitrary
// side-effects could have happened.

Có một vài trường hợp mà optimizing compiler sẽ không thực hiện tối ưu, một trong số đó là không có type feedback, gây ra bởi code chưa được chạy hoặc garbage collector đã xóa đi type feedback.

list
from outgoing([[Inline Caching]])
sort file.ctime asc

Resources

xem phần Deoptimization ↩

Quartz 🪬

Explorer

V8 - Inline Caching

TL;DR

V8 Implementation

Simulation in JavaScript

Generated Code

Deoptimization

States

Monomorphic

Polymorphhic

Megamorphic

Debug with D8

Speculative Optimizations

Intermediate Representation (IR)

Decision Tree

Resources

Table of Contents

Backlinks

Quartz 🪬

Explorer

V8 - Inline Caching

TL;DR

V8 Implementation

Simulation in JavaScript

Generated Code

Deoptimization

States

Monomorphic

Polymorphhic

Megamorphic

Debug with D8

Speculative Optimizations

Intermediate Representation (IR)

Decision Tree

Related

Resources

Footnotes

Table of Contents

Backlinks