Illustration of Google V8 16: how does V8 improve function execution efficiency through inline caching?

explain

The illustration Google V8 Learning notes

What is inline caching ？

inline caching （Inline caching） It is the optimization technology adopted by the runtime system of some programming languages , The earliest is Smalltalk Development . The goal of inline caching is to speed up runtime method binding by remembering the results of previous method queries directly at the call point . Inline caching is particularly useful for dynamically typed languages , Most of them （ If not all ） Method binding occurs at run time , So virtual method tables are usually not available .

Example ：

function loadX(o) {
     
    return o.x
}
var o = {
     
	x: 1,
	y: 3
}
var o1 = {
     
	x: 3,
	y: 6
}
for (var i = 0; i < 90000; i++) {
    
    loadX(o)
    loadX(o1)
}

V8 obtain o.x The process of ： Look for objects o The hidden class of , Then find... Through hidden classes x Property offset , Then get the attribute value according to the offset .

In the above code loadX The function will be executed repeatedly , So get o.x The process also needs to be executed repeatedly .V8 The strategy taken to speed up function execution is inline caching (Inline Cache), Referred to as IC.

IC How it works

V8 During the execution of the function , Will observe some call points in the function (CallSite) Key intermediate data on , Then cache the data , The next time the function is executed again ,V8 You can directly use these intermediate data , It saves the process of acquiring these data again .

IC The process

IC One for each function is maintained Feedback vector (FeedBack Vector), The feedback vector records some key intermediate data during the execution of the function .

Relation between function and feedback vector ：

What is a feedback vector ？

The feedback vector is actually a Table structure , It consists of many items , Each item is called a slot (Slot),V8 Will execute... In turn loadX The intermediate data of the function is written to the slot of the feedback vector .

The index of the slot is included in each slot (slot index)、 Type of slot (type)、 Status of the slot (state)、 Hidden class (map) The address of 、 And the offset of the attribute .

Example ：

function loadX(o) {
     
	o.y = 4
	return o.x
}

For example, the code above , When V8 When executing this function , It will judge o.y = 4 and return o.x These two paragraphs are Calling point (CallSite), Because they use objects and properties , that V8 Will be in loadX Each call point is assigned a slot in the feedback vector of the function .

How data is written to the feedback vector ？

Example ：

function loadX(o) {
     
    return o.x
}
loadX({
    x:1})

My bytecode here is ：

[generated bytecode for function: loadX (0x023600253611 <SharedFunctionInfo loadX>)]
Bytecode length: 5
Parameter count 2
Register count 0
Frame size 0
Bytecode age: 0
         00000236002537BE @    0 : 2d 03 00 00       GetNamedProperty a0, [0], [0]
         00000236002537C2 @    4 : a9                Return
Constant pool (size = 1)
0000023600253791: [FixedArray] in OldSpace
 - map: 0x023600002239 <Map(FIXED_ARRAY_TYPE)>
 - length: 1
           0: 0x023600253599 <String[1]: #x>
Handler Table (size = 0)
Source Position Table (size = 0)

First, it should be the same as that of big brother Li Bing ：

StackCheck
LdaNamedProperty a0, [0], [0]
Return

LdaNamedProperty： Its function is to take out parameters a0 The first property value of , And put the attribute value into the accumulator .

• a0 Namely loadX The first parameter of ;
• The second parameter [0] Indicates that the object is taken out a0 The first property value of .
• The third parameter is related to the feedback vector , It means LdaNamedProperty The intermediate data of the operation is written into the feedback vector , In the middle of square brackets 0 Indicates that it is written in the first slot of the feedback vector .

In function loadX In the feedback vector of , Data has been cached ：

• stay type bar ： Cached operation type , Here is LOAD type . In the feedback vector , Pass this through o.x The operation to access the value of an object property is called LOAD type .
• stay state bar ： Cached the status of the slot , there MONO ( Is singlet (monomorphic) Abbreviation );
• stay map bar ： Cached o The address of the hidden class ;
• stay offset bar ： Cached properties x The offset ;

Storage (STORE) Types and function calls (CALL) type

function foo(){
    }
function loadX(o) {
     
    o.y = 4
    foo()
    return o.x
}
loadX({
    x:1,y:4})

Bytecode ：

StackCheck
LdaSmi [4]
StaNamedProperty a0, [0], [0]
LdaGlobal [1], [2]
Star r0
CallUndefinedReceiver0 r0, [4]
LdaNamedProperty a0, [2], [6]
Return

Execution flow of bytecode ：

1. LdaSmi [4]： Will constant 4 Load into accumulator
2. StaNamedProperty： Put... In the accumulator 4 Assign to o.y
3. LdaGlobal： load foo The address of the function object into the accumulator
4. CallUndefinedReceiver0： Realization foo Function call

The resulting feedback vector ：

Polymorphism and hypermorphism

One slot of a feedback vector can contain information of multiple hidden classes ：

• If a slot contains only 1 A hidden class , Then we call this state Singlet (monomorphic);
• If a slot contains 2～4 A hidden class , Then we call this state polymorphic (polymorphic);
• If there is more than... In a slot 4 A hidden class , Then we call this state Superstate (magamorphic).

Execution efficiency ：

If the shape of the object is not fixed , signify V8 The hidden classes created for them are also different .V8 The offset information recorded in the feedback vector cannot be used .

Example ：

function loadX(o) {
     
    return o.x
}
var o = {
     
	x: 1,
	y: 3
}
var o1 = {
     
	x: 3,
	y: 6,
	z: 4
}
for (var i = 0; i < 90000; i++) {
    
    loadX(o)
    loadX(o1)
}

o The hidden class of is followed by o1 The hidden class of is not a hidden class ,V8 Will choose to record the new hidden class in the feedback vector .

When V8 Re execution loadX Function o.x When the sentence is , Also look up the feedback vector table , Compare .

utilize IC performance optimization

The performance of singlet is better than that of polymorphism and super state , Try to avoid polymorphic and hypermorphic situations .

Example ： The following two pieces of code , Which section is efficient , Why? ？

let data = [1, 2, 3, 4]
data.forEach((item) => console.log(item.toString()))

let data = ['1', 2, '3', 4]
data.forEach((item) => console.log(item.toString()))

The first is more efficient .

• In the first way , every last item Same type , Subsequent calls toString It's a direct hit , Is singlet .
• In the second way , because item Different types of errors , Change frequently , You need to cache multiple types at the same time , It's polymorphism .

Expand information

• V8 Polymorphic inline cache in PIC
• inline caching