V8 optimizations behind the scenes

This article aims to scratch the surface of how V8 (or any modern JS engine nowadays) uses the power of inline caching and hidden classes to optimize execution of JavaScript code under the hood.

A little about JavaScript Engines

JavaScript engines are computer programs that takes your JS code and executes it with the help of runtime environment (eg. browsers, node). JS engine mainly consists of -

1. Parser — takes source code and converts it into Abstract Syntax Tree
2. Compiler and interpreter — to execute parsed JS code.
3. Call stack — a data structure to store state of program.
4. Heap — memory allocation area.
5. Garbage collector — to free up unused memory.

Some of the popular JS engines are V8 in Google Chrome and Node, Spidermonkey in Mozilla Firefox, Chakra in Microsoft Edge.

Almost all JS engines nowadays perform similar steps. They take JS code and parse it to construct an Abstract Syntax Tree. This AST is fed into an interpreter that produces slightly optimized bytecode (using function inlining, etc). This makes your application start up really quick. However, there is more scope of optimizations that JS engine can perform (we shall see soon). To do this, there is an additional Just In Time (JIT) compiler which continously takes feedback from the code running and generate highly optimized machine code based on some assumptions. If at any point of time, assumption turns out to be incorrect, there is also a deoptimization step.

JavaScript code compilation

A little about V8

V8 is Google’s open source high-performance JavaScript and WebAssembly engine, written in C++. It is used in Chrome and in Node.js, among others. V8 has an interpreter Ignition that produces some optimised bytecode for fast application start up and a Just In Time compiler TurboFan that keeps running in background and generates optimized machine code for faster execution. V8 uses many different techniques to optimize machine code. In this post we will see one of them.

But first, some background.

Memory allocation in V8

Javascript is a dynamically typed language. Type of a variable is known only at runtime and type of a variable can change during it’s life cycle. This also opens up the possibility of adding or deleting properties from an object. These arbitrary events make it really hard for JS engines to determine the memory address of the value of a property inside an object.

In static typed languages like Java, compiler knows at compile time what will be the layout of the object. Since object structure cannot change after being defined, compiler can store the offsets of the location of property in memory. So any object’s property value can be retrieved in one attempt (by checking in memory at stored offset). This cannot happen in dynamically typed languages because object structure can change at runtime.

One technique would be to use a hash based dictionary to store memory address of value of a property with key as property name.

It would look something like -

// get value of a property
function getKeyValue(key) {
   let address = calculateAddressOfKey(key);
   // get value from memory address
}
// set value of a property
function setKeyValue(propName, value) {
   let address = calculateAddressOfKey(key);
   // set value for key at memory address
}
// calculate hash of key
function calculateAddressOfKey(key) {
   let memoryAddress = getHash(key); // calculate hash
   return memoryAddress;
}

The above code works, but one major issue is every time we call getKeyValue or setKeyValue, we in turn use getHash function, which can be computationally expensive.

V8 does not use the above method. Instead it takes care of object structure with the help of hidden classes.

Hidden classes

Hidden classes store the offsets of all the properties of an object like a fixed layout similar to Java except that hidden classes are created runtime. Every object corresponds to a hidden class (internally called shape/map). This works in the following ways -

1. When an object is created, an empty hidden class is attached to it.

var obj = {};

obj = {}

2. Every time a new property is added to the object, a transition takes place where now object starts pointing to a new hidden class which is referred by old hidden class.

obj.x = 1;

obj = {x : 1}

3. Each hidden class stores the offset to the newly added property in the object which now points to a new hidden class.

obj.y = 2;

obj = {x : 1, y : 2}

This makes retrieval of memory address of a property much easier and less expensive. JS engine just require to find the appropiate hidden class, then it can get all the required offsets.

Since each transition in properties is recorded, hidden class transitions form a tree like structure with all objects pointing to any one of the node.

One thing to note here is that these hidden classes can be shared among objects. So same objects points to same hidden class. However, for two objects to be same, assignment order of their properties must also be same.

var obj1 = {};
var obj2 = {};
obj1.a = 1;
obj1.b = 2;
obj2.b = 2;
obj2.a = 1;

In the above code example, obj1 and obj2 will have different hidden classes even though they are structurally same because there corresponding hidden classes took different transition paths. For above code block, hidden classes would be stored like -

different hidden classes

Here, order of assignments of a and b are different for obj1 and obj2, so there hidden classes are different.

V8 does not always start with an empty hidden class. Engines apply some optimizations for object literals that already contain properties. For obj = {a :1},
it starts with a hidden class that contains offset of ‘a’.

Inline Caching

Inline caching is an optimization technique that relies upon the observation that repeated calls to same function tends to occur on same type of objects. This is a huge help in dynamically typed languages like JS where objects can change at runtime because now compiler can assume the type of object at the call site, store that type in cache. The next time when same function is called, compiler can directly search for the type in cache.

var x = {a : 1, b : 2};
/* 
at some point compiler will realize obj structure is always like:
{a : <int>, b : <int>}
*/
function process(obj) {
   //process obj
}
for(let i=0; i<1000; i++) {
   process(x);
}

There are broadly 3 types of inline caching —

1. Monomorphic (optimized) — always same type of objects are passed.
2. Polymorphic (slightly optimized) — limited number of different types of objects passed.
3. Megamorphic (unoptimized) — any number of different objects passed.

Optimization

V8 uses both hidden classes and inline caching to optimize hot functions. Hot functions here are those functions which are called repeatedly with same type of objects (objects with same hidden class). When a function becomes hot, instead of searching for object’s hidden class every time function is called, V8 stores the offsets of different properties of the object so subsequent calls does not check for hidden class but directly access properties using stored offsets. This increases execution speed because there is no need to look for object’s hidden class.

V8 optimistically optimizes code execution. It can show significant improvements.

However, as the saying goes…

quote

Responsibility

We discussed how V8 hopes to find same type of object as argument for a hot function. But since JS is a dynamically typed language, the argument object’s shape may change. When this happens, it triggers deoptimization of machine code because now V8 cannot directly lookup for stored offsets to find properties. This causes problems as now if the function is called, appropiate hidden class should be searched. Now, again if the function is called with some parameters, V8 cannot directly assume its hidden class and hence its layout, instead it looks into the memory and find the matching hidden class for this object to access its properties later.

Experiment

Above optimization and deoptimization concepts can be demonstrated using fairly simple code block.

Before looking into results, just try to guess the output of the above code (hint : no trick question)

Results

On my machine upon running it 10 time, outputs are -

122 196 237
122 198 238
121 198 237
120 197 237
121 197 238
120 196 252
120 198 236
120 198 237
120 197 238
119 197 238

This was expected because passing same type of object helps V8 to optimize whereas passing different types of objects causes deoptimizations.

In the above code, processPoint is always called with objects (p1 and p3) having same hidden class, processPoint2 is called with objects (p2 and p1) having different hidden classes. processPoint3 is called with generic variables (p1 object and integer 1) and is even slower than processPoint2.

Takeaways

We noticed that V8 (and other JS engines) have implemented pretty good techniques to improve performance of this dynamically typed language. But it also depends upon us, to use this power by writing code responsibly.

Some steps we can follow to bring this power into good use are -

1. Initialize object properties in same order so that a hidden class can be shared — less hidden classes.
2. Always call functions with same type of objects so that inline caching can be used for optimization — functions remains hot.
3. After initializing an object, don’t add properties so that no hidden class transition takes place — faster hidden class search.

Closing

There are lots of topics that we did not discuss here. For example, maintaining states of inline caches for each function, On stack replacement (OSR) of hot functions, hidden classes for arrays, tagging/untagging of elements in arrays. There exists a whole bunch of optimizations out there that we can use to write better and faster code. We can aim to learn as much of these techniques to get maximum out of what advantages JS engines have to offer.

Happy coding!

References

Javascript Hidden Classes and Inline Caching in V8

JavaScript engine fundamentals: Shapes and Inline Caches

How JavaScript works: inside the V8 engine + 5 tips on how to write optimized code

JavaScript Engines Hidden Classes (and Why You Should Keep Them in Mind)