Check out the latest in the series: How V8 Works — V8’s JavaScript Execution Pipeline

This article is based on Chrome 73.

preface

V8, perhaps, is familiar but unfamiliar territory for front-end developers.

By the time you read this article, it will have gone through three iterations. The only purpose is to present it in a more intuitive way and make it more acceptable to everyone on the premise of ensuring that it is as accurate as possible. This article does not require much preparatory knowledge, just a basic understanding of JavaScript objects.

To make the article less boring, and to verify the accuracy of the points, the article includes a number of small experiments that you can play with on the console.

Prep — View memory snapshots in Chrome

First we run a program like this on the console.

function Food(name, type) {
  this.name = name;
  this.type = type;
}
var beef = new Food('beef'.'meat');
Copy the code

Switch to Memory and click the circle on the left to take a snapshot of the current Memory.

An object is created through a constructor primarily to make it easier to find in a snapshot. Click on the snapshot and enter Food in the filter to find all the objects constructed by Food.

The structure of objects in V8

In V8, objects are made up of three Pointers: Hidden Class, Property, and Element.

Hidden classes are used to describe the structure of an object. Property and Element are used to hold the attributes of an object. The difference between them is whether the key name can be indexed.

The Property and the Element

// Indexable attributes are stored in the Elements pointer {1:"a", 2: "b"} // Named Properties are stored in the area pointed to by the Properties pointer {"first": 1, "second"2} :Copy the code

In fact, this was designed to meet the requirements of the ECMA specification. As described in the specification, indexable attributes should be arranged in ascending order of index value size, while named attributes should be arranged in ascending order of creation.

Let’s do a simple little experiment.

var a = { 1: "a", 2: "b"."first": 1, 3: "c"."second": 2 }

var b = { "second": 2, 1: "a", 3: "c", 2: "b"."first": 1 }

console.log(a) 
// { 1: "a", 2: "b", 3: "c", first: 1, second: 2 }

console.log(b)
// { 1: "a", 2: "b", 3: "c", second: 2, first: 1 }
Copy the code

The difference between a and B is that A begins with an indexable attribute and B begins with a named attribute. In a, indexable properties are arranged in ascending order, with named properties first followed by second. In b, the index-able properties are sorted out of order, and the named properties are second followed by first.

You can see

  • Attributes of an index are listed in ascending order by index value size, while named attributes are listed in ascending order by the order in which they were created.
  • In the case of using both indexable and named properties, there is a distinct separation between the two different properties in the console print result.
  • Whether indexable properties or named properties are declared first, they always appear in the same order in the console (in my browser, indexable properties always appear first).

Both of these can be seen from the side that these two properties are stored separately.

That’s the side. Let’s look at the front. Let’s take a look at snapshots of these two properties using the method shown in our preliminary knowledge.

// Experiment 1: Storing indexable attributes and named attributesfunction Foo1 () {}
var a = new Foo1()
var b = new Foo1()

a.name = 'aaa'
a.text = 'aaa'
b.name = 'bbb'
b.text = 'bbb'

a[1] = 'aaa'
a[2] = 'aaa'
Copy the code

Both A and B have named attributes name and text, and A has two additional indexable attributes. It is obvious from the snapshot that indexable properties are stored in Elements, and that A and B share the same structure (which is described below).

You might wonder how these two objects have the same structure because they have different properties. To understand this question, first ask yourself three questions.

  • Why do you save objects? For later use, of course.
  • What do I need to do to use it? I found this property.
  • What is the purpose of describing a structure? Look for a steed according to the picture.

So, for indexable properties, it is already ordered, why do we have to look through its structure many times in one fell swoop? We don’t have to go through its structure to find it, so we don’t have to describe its structure. In this way, it should be easy to understand why A and B have the same structure, because their structure only describes the case that they both have name and text.

There are exceptions, of course. Let’s add one more line to the code above.

a[1111] = 'aaa'
Copy the code

As you can see, the hidden class changes and the data stored in Element becomes irregular. This is because, when we add a[1111], the array becomes sparse. To save space, the sparse array is converted to a hash store rather than a full array describing the storage of the space. Therefore, these indexable properties can no longer compute the memory offset directly from their index values. As for the hidden class changes, it’s probably to describe a change in the structure of the Element. (This image can be compared to the slow Property image below. You can see that Foo1’s Property does not degrade to a hash store, but that the Element’s degradation to a hash store causes the hidden class to change.)

Different ways to store named attributes

There are three different ways of storing named attributes in V8: in-object, fast, and slow.

  • In-object properties are stored in the object itself, providing the fastest access.
  • A fast property takes one more addressing time than an in-object property.
  • Slow attributes store the full structure of the attribute (the structure of the other two attributes is described in the hidden class, which will be explained below) and are the slowest (slow attributes, attribute dictionaries, and hash stores all say the same thing below or in other related articles).

That’s a little abstract. Don’t worry, let’s do it with an example.

// Experiment 2: Three different types of Property storage modesfunction Foo2() {}

var a = new Foo2()
var b = new Foo2()
var c = new Foo2()

for (var i = 0; i < 10; i ++) {
  a[new Array(i+2).join('a')] = 'aaa'
}

for (var i = 0; i < 12; i ++) {
  b[new Array(i+2).join('b')] = 'bbb'
}

for (var i = 0; i < 30; i ++) {
  c[new Array(i+2).join('c')] = 'ccc'
}
Copy the code

A, B and C have 10, 12 and 30 properties respectively. In the current Chrome 73 version, they are stored in three ways: object property, object property + fast property and slow property respectively. The running snapshot of this piece is a bit long, so let’s take a look at each of them.

In-object properties and fast properties

So first let’s look at a and B. To some extent, in-object properties and fast properties are actually the same. However, the properties within an object are allocated at the time the object is created, and space is limited. In my experimental condition, the number of properties in the object is fixed to ten, and these ten Spaces are the same size (can be understood as ten Pointers). When the properties in the object are full, they are stored as fast properties in the order they were created under properties. Fast properties require one more addressing time for the properties than for the in-object properties, followed by a linear lookup consistent with the in-object properties.

Slow attribute

And then let’s look at C. This is too long, so I’m just taking part of it. As you can see, compared to B (fast property), the index in properties becomes an irregular number, meaning that the object has become a hash access structure.

So, the question is, why do we have these different types of storage? Let me tell you what I understand.

Why are there three ways to store it? (Personal understanding)

This is actually a question that was raised when we shared it internally. I’m sure you’re wondering the same thing when you read this. I couldn’t quite explain why until I saw a hashed image (from the web).

In V8, the fundamental reason for all the seemingly bizarre optimizations is to be faster. – I

It can be seen that the early JS engines used slow attribute storage, the first two are out of the optimization of this storage method and appear.

We know that all data is represented in binary at the bottom. We also know that program logic is fastest if it only involves binary bit operations (and, or, and not). We will compare the three (two) methods in terms of the number of times calculated, regardless of the time spent on addressing, etc.

What the properties and fast properties in the object do is simple, linear lookup of each position to see if it is the specified position. This part of the time can be understood as the time of up to N simple bit operations (N is the total number of properties). The slow attribute needs to go through the hash algorithm first. This is a complex operation, several times the time of a simple bit operation. In addition, the hash table is a two-dimensional space, so once the coordinates of one dimension are calculated by the hash algorithm, the linear search is still needed in the other dimension. So it’s not hard to understand why you don’t use slow properties when there are very few properties.

Attach a string hash algorithm from V8 with 60 left and right shifts alone (60 simple bit operations).

/ / the hash value of the string in the V8 generator uint32_t StringHasher: : GetHashCore (uint32_t running_hash) {running_hash + = (running_hash < < 3); running_hash ^= (running_hash >> 11); running_hash += (running_hash << 15); int32_thash = static_cast<int32_t>(running_hash & String::kHashBitMask);
  int32_t mask = (hash1) > > 31;return running_hash | (kZeroHash & mask);
}
Copy the code

So why not always use in-object properties or fast properties?

This is because when there are too many properties, these two approaches may not be as fast as the slow properties. Assuming that the cost of hashing is 60 simple bit operations, the hashing algorithm performs well. If I only store it as an in-object property or as a fast property, when I need to access the 120th property, it takes 120 simple bit operations. With the slow attribute, we need a hash calculation (60 simple bit operations) + a linear comparison in the second dimension (much less than 60, assuming that the hash algorithm performs well and that the attribute is evenly distributed in the hash table).

“Comics: What is a HashMap?

Hidden classes

The above description of how named attributes are stored, known in V8 as a Map, is better known as a Hidden Class.

In SpiderMonkey (Firefox Engine), a similar design is called Shape.

Why introduce hidden classes?

The first is, of course, faster.

JavaScript is a dynamic programming language that allows developers to define objects in a very flexible way. Objects can change type and add or remove properties at run time. In contrast, in a static language like Java, the type is immutable once created, and the properties can be accessed at fixed offsets.

As mentioned earlier, accessing attributes by means of a hash table requires additional hash calculations. In order to improve the access speed of object properties and realize the fast access of object properties, V8 introduced hidden classes.

Another significance of the introduction of hidden classes is the significant memory savings.

In ECMAScript, an Attribute for an object Attribute is described as the following structure.

  • [[Value]]: the value of the property
  • [[Writable]]: Defines whether an attribute is writable (that is, whether it can be reassigned)
  • [[Enumerable]]: Defines whether an attribute is enumerable
  • [[Configurable]]: Defines whether an attribute is configurable (delete)

The introduction of a hidden class separates the Value of an Attribute from other attributes. In general, the Value of an object changes frequently, and the Attribute changes almost never. So, why do we repeatedly describe attributes that rarely change? This is obviously a waste of memory.

Hide class creation

During object creation, a new hidden class is generated for each named property added. At the bottom of V8, a transformation tree is implemented to connect the hidden classes. If the same attributes are added in the same order, the transformation tree will ensure that the same hidden classes end up.

In the following example, a corresponds to different hidden classes when the object is empty, when the name attribute is added, and when the text attribute is added.

// Experiment 3: Creating a hidden classlet a = {}
a.name = 'thorn1'
a.text = 'thorn2'
Copy the code

The following is a schematic for creating the process (only the process is described; the details may differ slightly from the actual implementation).

Using the memory snapshot, we can also see that Hidden Class 1 and Hidden Class2 are different, and that the latter’s back_pointer points to the former, which confirms the process analysis in the figure above.

Some articles have mentioned that in real storage, every time a property is added, the newly created Hidden Class will actually only describe that property, but not all properties. That is, Hidden Class 2 will actually only describe text, not name. I haven’t yet verified this with memory snapshots (no technical tears), but logically it should be.

There’s another little point here.

// Experiment 4 hides the optimization when creating classeslet a = {};
a.name = 'thorn1'
let b = { name: 'thorn2' }
Copy the code

The difference between a and B is that a first creates an empty object and then adds a named property name to the object. B creates an object with the named property name. As we can see from the memory snapshot, a and B have different hidden classes, and back_pointer is also different. This is mainly because, when creating b’s hidden class, the step of creating a separate hidden class for the empty object is omitted. So, to generate the same hidden class, a more accurate description would be to add attributes of the same structure (with the exception of Value) from the same starting point and in the same order.

If you’re particularly interested in creating hidden classes, I recommend JavaScript Engine Fundamentals: Shapes and Inline Caches.

The magic delete operation

Above we discussed the effect of adding attributes on hidden classes. Now let’s take a look at the effect of deleting a hidden class.

// Experiment 5 effects of delete operationfunction Foo5 () {}
var a = new Foo5()
var b = new Foo5()

for (var i = 1; i < 8; i ++) {
  a[new Array(i+1).join('a')] = 'aaa'
  b[new Array(i+1).join('b')] = 'bbb'
}

delete a.a
Copy the code

As we tried before, both A and B are intrinsic properties of the object. As you can see from the snapshot, after deleting a.a, A becomes a slow property and falls back into the hash store.

However, the situation is different if we reverse delete the properties in the order they were added.

// Experiment 6 deletes attributes in the order they were addedfunction Foo6 () {}
var a = new Foo6()
var b = new Foo6()

a.name = 'aaa'
a.color= 'aaa'
a.text = 'aaa'

b.name = 'bbb'
b.color = 'bbb'

delete a.text
Copy the code

We add the same attribute name and color to a and B, and add an additional attribute text to A, and then remove this attribute. You can see that a and B have the same hidden class at this point, and A does not fall back into the hash store.

Conclusion and Enlightenment

  • Attributes are divided into named attributes and indexable attributes. Named attributes are storedProperties, indexable properties are stored inElementsIn the.
  • Named attributes can be stored in three different ways: in-object attributes, fast attributes, and slow attributes. The first two are accessed through linear lookup, and the slow attributes are accessed through hash storage.
  • By always initializing object members in the same order, you can take full advantage of the same hidden classes, thus improving performance.
  • Adding or removing indexable properties does not change the hidden class, and sparse indexable properties degenerate into hash storage.
  • Delete operation may change the structure of the object, causing the engine to degrade the storage mode of the object to hash table, which is not good for V8 optimization, and should be avoided as much as possible (objects will not degenerate into hash storage when deleting attributes in the opposite direction from attribute addition).

A link to the

The resources

  • V8 Journey: Object representation
  • JavaScript engine base: Shapes and Inline Caches
  • V8 Hidden Class – w3ctech
  • V8 Hidden class – LINE ENGINEERING
  • Hidden classes in JavaScript and Inline Caching
  • Fast properties in V8 · V8