Understanding of JS engine optimization

I have read a blog by Mathias Bynens (one of the V8 authors) about the optimization principle of JS engine, and I think it is relatively clear and easy to understand. I have my own understanding of this problem in the simplest way.

This note is a simple summary of my personal understanding of the issue. The original text has been written clearly enough good enough, I hope to use their own way to describe, help understand and memory. Perhaps I have some in-depth principles can not be accurately described, I suggest that if you have time to read the original text to further study.

Note: Most of the pictures in this article are from the author’s original text.

How the JS engine works

First, some background, such as what JS engines are and how they work.

Current mainstream JS engines:

1. V8 (Chrome and NodeJS)
2. SpiderMonkey (FireFox)
3. Chakra (IE and Eage)
4. JavaScriptCore (Safari/ReactNative)

The JS engine executes the flow of code

Different JS engines differ in some of the details of execution and optimization, but they have the following common processes.

1. The JS source code is first parsed by the parser to generate an AST (Abstract Syntax Tree).
2. The interpreter can generate bytecode on top of the AST and execute it;
3. For some code that is “hot” (i.e. called frequently), the interpreter sends profiling data to the compiler for optimization.
4. Optimization is to make some guesses on the basis of existing code and analysis information, and then generate optimized machine code. After optimization, this part of the code is replaced by the optimized machine code, which can be directly executed in the system processor.
5. The compiler also “de-optimizes” the code back to the interpreter if a particular assumption is wrong when a node is found to be optimized.

code	producer	practitioners	Generating efficiency	Execution efficiency	Space efficiency
The bytecode	The interpreter (interpreter)	The interpreter	high	low	high
Machine code	The compiler (optimizer)	CPU*	low	high	low

* note: The CPU here is my own interpretation, Bytecode needs an interpreter to run, whereas the optimized code can be executed directly by the processor.

Simply be the interpreter can get first-hand from the abstract syntax tree quickly bytecode and perform, but the code is not optimized, if a frequent call method requires access to a particular attribute from an object, so every one call perform complete query process, the efficiency is low;

Tuning code takes time and requires more space to store optimization-related information and larger optimizations, but it can make code like the above more efficient.

So it’s a tradeoff between startup time, footprint, and execution efficiency. Previous VERSIONS of V8 compiled all source code into machine code, skipping the bytecode step and sacrificing some startup time, which made execution very efficient, but machine code also took up a lot of memory, which caused problems with code caching. It’s a little over-optimized in a way. It’s not that more optimization is better, it’s that “better for the best” and only optimize the parts of the code that “better code can significantly improve performance.” This is what the author calls “Hot Code”.

Implementation of different browser engines

JS engine	interpreter	optimizer
V8	ignition	TurboFan
SpiderMonkey	interpreter	Baseline + IonMonkey
Chakra	interpreter	SimpleJIT + FullJIT
JavaScriptCore	LLInt	Baseline + DFG + FTL

Although their interpreters and optimized compilers seem to have different names, all JS engines share the same architecture: parser (for generating AST) and parser + optimized compiler pipeline structure. It is a pipe structure because the bytecode execution by the parser and the optimized compiler can be executed in parallel. When the interpreter sends the code to be optimized to the compiler of another thread for optimization, it can still execute the currently unoptimized bytecode. After the optimization process is complete, the optimized code will merge into the main thread and then execute the optimized code.

The adoption of multiple optimization layers also sets up more intermediate nodes between “unoptimized” and “highly optimized”, which is equivalent to “grading” — increasing the degree of optimization according to the degree of “Hot”, so that the tradeoff decision between time/space/execution efficiency can be controlled with finer granularity.

Objects and Arrays

In EcmaScript, all objects are essentially dictionaries, that is, collections of key-value pairs of string keys and attribute values. Attributes of the object also has “properties”, is to define the nature of the property and not directly exposed to the JavaScript descriptors: [[Value]], [[Writable]], [[Enumerable]], [[Configurable]]. Each attribute has its own descriptor. For a custom attribute we add to an object, [[Value]] is the Value we assign to that attribute, and all other descriptors default to true.

Arrays can actually be treated as objects, but arrays have special treatment for numeric indexes. The range of valid string integer I is reduced to +0 <= I < 232-1, whereas integer indexes in normal objects need only be safe integers (+0 <= I <= 253-1). The array contains the length attribute, which is not enumerable or configurable and is automatically updated when the array element is modified. Arrays of numerically indexed elements are treated similarly to descriptors for custom object attributes by default.

JS engine optimization

The Shapes and the Inline Caches

Imagine a bookshelf (object) with many cells (contiguous storage locations), each cell can hold a book (property), and each time we buy a new book we put it directly in the next space. When we want to check the information of a book, we need to start from the beginning to check the title of a book, just look for it once, if we do this every time, it will be inefficient. So we can think of ways to find before the location of the serial number to remember, to avoid repeated work next time.

But there is a problem. What if the books on the shelf are added or removed or moved? Then the original information is not reliable. But how do you know if it’s changed?

We create a list of books with the title and its corresponding location, and if there is any change, we update it and mark it. Then we can check whether there has been any change by comparing the list. This way is very convenient for people who need to find a certain book often. He only needs to remember which book list and the position of the book he is looking for. Next time, as long as the book list has not changed, even the step of searching for the title of the book is saved, and he can directly take the book he wants from the corresponding position.

If the metaphor object’s property values are all books and the property name is the title of the book, Shape is something similar to the “book list” described above. Shape is a general term. It has different names in different JS engines, but has similar meanings. Shape is related only to the property information (including the memory location and description of the property) and is decoupled from the value of the actual object, so as long as the property names/descriptions and order of the properties are the same, the two objects can share a Shape.

Inline Caches (ICs) are key to speeding up JS execution, which can be interpreted as important information cached to reduce repeated retrieval of Hot code. The name (inline caching) probably comes from the fact that this cache information is stored in the structure of the command embedded in Hot Code, which is used for instant checksum retrieval each time the Code is executed.

Object storage and access

In fact, attribute names and attribute values of objects are stored separately in THE JS engine. The attribute values themselves are stored in the object in order, and the attribute name creates a Shape, storing the “offset” and other descriptor attributes of each attribute name.

If you add new properties to an object at runtime, that property list transitions to a new Shape and links back to the old Shape. Transition Chains. You can go back to the previous list to retrieve it.

Shape is reused because different objects have the same attribute name list. When they change, they will transition to their new Shape, forming a transition tree.

But what if constantly extending objects makes the Shape chain very long? The engine will create a ShapeTable that lists all the attributes and links them to their respective shapes. This still seems cumbersome, but it’s all about not wasting “work done” and making it easier to keep Inline Caches, useful retrieval information.

To quote examples from the article:

function getX(o) {
    return o.x;
}
// For the first time, retrieve and cache the Shape link and offset
getX({x: "a"});
// Check that the Shape is the same and decide whether to use caching
getX({x: "b"});
Copy the code

It retrieves Shape for the first time and retrieves the value of the object after obtaining offset. The Shape link and the result of this retrieval are also cached inline in the code structure.

If the Shape is the same as before (object reuse benefits of Shape), the cached offset is used.

Array storage and access

An array is itself a special kind of object. The length property of an array is stored in the same way as the property of an object. For array elements, the value of the key attribute is a string (value). By default, the description information is the same as that of the object’s custom attribute (except [[value]], which is writable, enumerable, and configurable).

The JS engine stores all of the numerically indexed elements separately in the Elements Backing Store of the array, which acts as a backup repository for its neatly placed stuff. If the attribute description of any index is not artificially modified, there is no need to store “offset”, because the index itself is” offset” when accessed through a numeric index, and the attribute descriptor only needs to store a copy for each index attribute to share.

But the above is the general situation, if unfortunately met array indexing descriptors to be redefined, even change a new one, JS engines also have to give up the above optimization strategy, it should also have to become a “dictionary” and warehouse structure, open up a bigger place, for each element to its index attributes intact description information. This makes array manipulation relatively inefficient.

It’s easy to recall a particularly common example of a “manual cache attribute” :

const arr = new Array(100000);
Arr. Length is inlined in the check condition for each loop
for (let i = 0; i < arr.length; i++) {
    // ...
}
Copy the code

In the for loop, the check condition is I < arr.length, which is equivalent to retrieving the length property value of arR every time. The more times the loop is used, the more wasteful this operation is. The general recommendation is to cache arr. Length in a variable ahead of time, and then use the variable directly during the loop, so that the array length property is read only once.

I have seen in some articles that this best practice has become less important with the optimization capabilities of the latest JS engines. If I understand correctly, this means that the JS engine can find Hot code and Cache the results using Inline Cache even without manual caching. However, instead of caching the result of length directly, the cache can be used to read the memory location of Length directly, so it is still not as fast as caching the base value in the variable.

After roughly testing the loop in console, one million times, the result is that it takes ~150ms to read the length attribute each time the cache variable execution is less than 20ms. Here is the test code:

// Each loop reads arr.length
const arr = new Array(1000000);
let count = 0;
console.time("inline")
Arr. Length is inlined in the check condition for each loop
for (let i = 0; i < arr.length; i++) {
    count++;
}
console.timeEnd("inline")
console.log(count);
/ / the inline: 148.780029296875 ms
/ / 1000000

// Cache the length variable
const arr1 = new Array(1000000);
const len = arr1.length;
let count1 = 0;
console.time("len")

for (let i = 0; i < len; i++) {
    count1++;
}
console.timeEnd("len")
console.log(count1);
/ / len: 13.648193359375 ms
/ / 1000000
Copy the code

Prototype chain optimization

The prototype itself is also an object, and when an attribute is accessed through an object, if the object is not found in the current object, it is searched up the prototype chain until it is found or stopped when the prototype is null and returns undefined.

If we treat stereotypes like objects, when accessing an object’s property, we need to first check its Shape to see if it exists. If it does not, we need to access the object’s prototype, then check its Shape, and so on — one at a time. This is equivalent to two retrievals, looking up the property in the current Shape and accessing the prototype through the object. In fact, in the JS engine, the reference to the prototype is stored in the Shape of the object rather than the object itself, which can be directly linked to the next prototype object when checking that there is no target attribute in the current Shape, so that each jump of the prototype only needs to complete one retrieval.

But doing so still requires retrieving attributes along the prototype chain, and there is limited optimization for repeated access to specific attributes. Finding attributes along the stereotype chain can be an expensive operation, especially since there are many cases where the stereotype chain of an object can be very long and important operations are commonly performed on the stereotype. For example, in the example of the A element in HTML, we can print the stereotype chain on console:

function protoChain(node) {
    const p = Object.getPrototypeOf(node); / / or node. __proto__
    console.dir(p);
    return p == null || protoChain(p);
};
const a = document.createElement("a");
protoChain(a);
Copy the code

The printed result is:

If the target attribute is on a deeper prototype, each retrieval is a string of expensive operations. According to the object cache attribute offset train of thought, we can put the prototype properties on position also cache, obviously at the same time, you have to keep the prototype object is also a reference, so that if the next time you visit the prototype chain and prototype object itself, there have been no changes, can directly use the cached results last, skip find operations. Note that the prototype of any object can be changed dynamically. How do you determine if the prototype chain has changed?

The JS engine does this by giving each stereotype object a unique Shape (not to be reused by any other object) that links to a ValidityCell that marks whether the stereotype and its upstream stereotype chain have changed. When the properties of a stereotype object change, the ValidityCell of that stereotype and all stereotypes downstream of it in the stereotype chain is set to false. So to ensure that the cache is valid, just verify that the check bit for the immediate prototype of the instance object is still true.

So, in addition to caching the prototype object with the Shape link, offset, and target attributes of the instance object itself, you also need to save the link to the ValidityCell of the immediate prototype of the instance object.

Take this code for example:

class Bar {
    constructor(x) { this.x = x; }
    getX() { return this.x; }}const foo = new Bar(true);
const $getX = foo.getX;
Copy the code

When executing $getX = foo.getX, which loads the corresponding value of foo.getX and then assigns it to $getX, the first step is to access the object property, which obviously needs to be retrieved from the prototype, the Inline Cache of this code will hold the following information after a single retrieval:

• Offset result – Memory location of the target attribute
• Shape links for the instance object itself – whether the object’s property list and immediate stereotype have changed
• Link to the prototype object where the target property is located — gets the value of the property
• A link to the ValidityCell of the immediate prototype of the instance object – confirming whether the prototype chain has changed

The next time this code is called, in addition to the need to compare the Shape of the instance object, we also need to compare whether there is any change on the prototype chain. If there is no change, then we no longer need to retrieve the property value of the corresponding prototype object by directly using the cached offset. This will greatly reduce the time spent looking up stereotype attributes.

If you change any link in the prototype chain, the valid value pointed to by the previously saved ValidityCell link will be set to false. In this case, the cache will be invalidated, and the standard retrieval will have to be repeated the next time.

In particular, when the prototype object on the prototype chain changes, the ValidityCell corresponding to the Shape of any prototype object downstream will be marked as “invalid”. As you can imagine, some of the Inline Cache based on stereotype attributes is invalidated during code execution when top-level stereotypes such as Object.prototype are modified.

As in the example of the A element in HTML mentioned above, the author has a very graphic diagram:

When you performObject.prototype.x = 42To change the top-level prototype:

Suggestions for optimizing your code

Based on the above information, the author gives the following suggestions to JS developers from the perspective of the engine:

1. Always initialize objects the same way.

On the one hand, the reusability of Shape is improved, on the other hand, the length/depth of transition chain or transition tree is reduced as much as possible, and the retrieval time of attributes along the Shape chain is shortened.

2. Do not modify the attribute description of an array’s elements (numerically indexed attributes).

This preserves the engine’s optimization of arrays and makes array storage and access more efficient.

3. Do not modify prototypes, especially for deep level prototypes such as Object.prototype, and even if you do need to modify them, do so before all code is executed rather than during code execution.

Otherwise, the engine would have to abandon the inline cache and go back to finding and retrieving attributes in the stupidest way possible in order to get the correct values.

Original link:

• JavaScript engine fundamentals: Shapes and Inline Caches
• JavaScript engine fundamentals: optimizing prototypes

Chinese Translation:

• JavaScript engine basics: Shapes and Inline Caches
• JavaScript Engine basics: Prototyping optimization

Reference:

• V8 Ignition: The JS Engine’s Connection to bytecode