How does V8 speed up access to object properties?

The general contents of this article include:

• What language is JS?
• What are general and sorted properties?
• What are fast properties and slow properties?
• What are the properties inside the object? Why do you want it?
• Why is property access in JS slower than in static languages? How do static languages access properties quickly? How does V8 speed up access to object properties?
• What’s the difference between linear storage and nonlinear storage? When do you reuse nonlinear storage?

This is quite long, here to sort out their own ideas, but also convenient for you to see:

1. What are properties and elements?
2. Then introduce what are fast attributes, slow attributes, in-object attributes, and introduce the difference between them;
3. How are objects laid out in memory
4. At the same time, other attributes found through examples are also illustrated
5. Set a few interview questions and answer them yourself
6. Thirdly, give a summary
7. Finally, I still have a blind spot to ask Daniel, hoping to give a reply

An object in JavaScript is a collection of properties and values. From the point of view of the JavaScript language, a JavaScript object is like a dictionary, with strings as key names. Any object can be used as key values, and key values can be read and written by key names. However, V8’s implementation of object storage does not fully use dictionary storage, mainly for performance reasons. Because dictionaries are non-linear data structures, query efficiency is lower than linear data structures. V8 uses a complex storage strategy to improve storage and search efficiency.

Before we begin, let’s take a look at the phenomenon

function testV8() {
  this['A'] = 'A'
  this[0] = '2'
  this['B'] = 'B'
  this[4.5] = '4.5'
  this['haha'] = 5
  this[1.2] = 1.2
  this[Awesome!] = '6'
  this['B'] = 'B'
  this[3] = 3
  this['4'] = '4'
}
const testObj = new testV8()
for (let key in testObj) {
  console.log(`${key}:${testObj[key]}`)}Copy the code

0:2
3:3
4:4
Awesome!:6
A:A
B:B
4.5:4.5
haha:5
1.2:1.2
Copy the code

Obviously the results are not in the order that we set them. Why is that?

In the example above, objects include integer integers, integer strings, floating point numbers, strings,

In fact, the reason for this result is that V8 has certain rules for storing object attributes. Here’s what the rules are.

Sorting properties (Elements) and general properties (Properties)

There are two types of properties in V8’s objects, sorting properties and general properties.

Call numeric attributes in an object sort attributes, which in V8 are called Elements. Numeric attributes should be sorted in ascending order of index value size.

String properties are called general properties, or properties in V8, and are listed in ascending order according to the order in which they were created.

Both attributes have elements before properties.

In V8, two linear data structures are used to store the sorted and general attributes separately in order to improve the performance of storing and accessing these two attributes. After splitting the two linear data structures, if an index is performed, V8 completes an index by reading all elements sequentially from the Elements property and then from the properties property.

Analyze the memory for the above instance as follows

Look at the diagram, why there are no properties within the object, because there are no more than 10 properties. Don’t worry, this will be shown in the following example.

In-object properties, fast properties, and slow properties

In-object properties: Stores some general properties directly into the object itself.

Storing different attributes in elements and properties simplifies the program, but it adds an extra step to finding elements, such as testobj. B, to find the value of B’s attributes. In V8, the object properties pointed to by the properties property will be found first, and then the property B will be found in the properties object. This method adds an extra step in the search process, thus affecting the efficiency of the element search. For this reason, V8 adopts a tradeoff strategy to speed up the efficiency of finding properties by storing some general properties directly into the object itself, which we call in-object properties.

After using in-object attributes, the regular attributes are stored in the testObj object itself, so that V8 can retrieve the value directly from testObj when using testobj.b to find the value of the B attribute. This method reduces the number of steps required to find the value of the attribute and increases the efficiency of the search.

However, the number of attributes in an object is fixed, 10 by default, and if you add attributes that exceed the space allocated by the object, they are stored in the regular property store. Although the property store has an additional layer of indirection, it can be expanded freely.

Normally, we will be saved in the properties of linear data structure called “fast properties 】 【”, because only need by index in linear data structure that can access to the property, although the access speed of linear structure, but if you add or remove from the linear structure when a large number of attributes, the execution efficiency is very low, this is mainly because will produce a lot of time and memory overhead.

Therefore, if an object has too many attributes, V8 adopts another storage strategy, the “[slow attributes]” strategy, but the slow attributes of the object will have a separate nonlinear data structure (dictionary) as the attribute storage container. All attribute meta-information is no longer stored linearly, but is stored directly in the attribute dictionary.

Regular properties in properties require an additional properties addressing time than in-object properties, followed by a linear lookup consistent with in-object properties (properties are regularly stored like arrays, linked lists)

Sort attributes, in-object attributes and some general attributes all belong to linear data structures, so they are all called fast attributes.

Nonlinear data structures are slow properties

Having seen how V8 stores objects, let’s take a look at how objects are allocated in memory using Chrome’s memory snapshot.

How are instance analysis objects laid out in memory

A maximum of 10

function testObj() {}

var test10 = new testObj()

for (var i = 0; i < 10; i++) {
  test10[i+'x'] = 'xxx'
}
Copy the code

The memory layout of this attribute:10Properties are stored directly in testObj objects;Copy the code

In order to reduce the search process of finding these properties, the mapping is generated directly in the object. It is quick to find, but up to 10.

More than ten

function testObj() {}

var test20 = new testObj()

for (var i = 0; i < 20; i++) {
  test20[i+'x'] = 'xxx'
}
Copy the code

The memory layout of this attribute:10Properties are stored directly in testObj objects; Other general properties are stored in the properties property as a linear data structure;Copy the code

As shown above, when the object is full of properties (more than 10 properties), it will be stored in the creation order under Properties as fast properties (0, 1… 9), note that since there are only 10 properties, the data structure is still linear, and we can see that it is arranged in the order in which it was created.

Fast properties require one more property address time than in-object properties, followed by a linear lookup consistent with in-object properties (properties are regularly stored like arrays, linked lists)

More than 20

function testObj() {}

var test50 = new testObj()

for (var i = 0; i < 50; i++) {
  test50[i+'x'] = 'xxx'
}
Copy the code

The memory layout of this attribute:10Properties are stored directly in testObj objects; Other general properties are stored in the properties property as a data structure for a nonlinear dictionary;Copy the code

Combining the above figure, we can see that when the data volume is large, the properties in the properties are no longer linear (119, 120), but are stored in the form of a nonlinear hash table (dictionary) (hash – split link).

Note: Split link is a hash key+ linked list value structure

Why does testObj not have elements? Because key is not a numeric property

Other attributes (map attributes andprotoAttributes)

Now we know how V8 stores objects, but look at the following image:

In addition to the Elements and properties properties, V8 also implements map and PROto properties for each object. The __proto__ attribute is the prototype used to implement JavaScript inheritance; A Map is a hidden class, which will be discussed in the next article.

Set a few interview questions

Why use in-object properties?

Properties within an object require one less properties addressing time than regular properties in Properties.

Why do we need the slow property instead of just using the fast property?

If you’re looking for more than 100 attributes and it takes more than 100 operations, it’s not as fast as a hash (say 50 simple operations)+ link search (less than 50 operations).

Why is property access in JS slower than in static languages?

Because js is a dynamic language, it is the object’s properties can be changed, so when you want to use some of the properties, the V8 engines need to know this attribute relative to the offset can be read from the corresponding object properties, and this process takes time, so the V8 engines have provides a quick properties to improve speed, slow but other properties, There will still be slow execution issues.

How do static languages access properties quickly?

Static languages are more efficient in reading object attributes than dynamic languages. The main reason is that static languages such as Java need to define the structure, or shape, of an object in advance when they declare it. During compilation, the engine can use this data to calculate the offset value of the attribute relative to the address of the object in advance. When it needs the attribute of the object later, it can directly read the content according to the offset value. Therefore, the execution efficiency is higher.

How does V8 optimize object attribute access speed?

By drawing on static features, V8 introduced hidden class technology for JS objects. By creating a hidden class for each object, the hidden class of the object records some basic layout information of the object, including all the attributes of the object, and the offset of each type relative to the object. With these two features, the V8 engine can quickly find the properties of an object. V8 works with multiple objects, and if the same shape is used, it will reuse the hidden classes corresponding to that shape.

In V8, two linear data structures are used to store the sorted and general attributes separately in order to improve the performance of storing and accessing these two attributes.

Comparison of linear and nonlinear (hash table) storage patterns

structure	The data type
Linear structure	Arrays, linked lists	fast
Nonlinear deconstruction	Hash Map (Split link)	slow

1. Linear storage is mainly time complexity is relatively small, and the code readability is better, nonlinear structure is often implemented in recursive implementation, so it is best not to use linear storage data nonlinear structure.

2. Nonlinear structure is the storage of complex data, which generally have a large correlation between the data, linear linked list is not possible.

conclusion

conclusion

• Sort order Numbers are sorted by size, and strings are sorted by order of execution
• In V8, two linear data structures are used to store the sorted and general attributes separately in order to improve the performance of storing and accessing these two attributes. After splitting the two linear data structures, if you perform an index operation, V8 completes an index operation by reading all elements sequentially from the Elements property and then from the properties property.
• The number of attributes in the object is fixed. The default value is 10 (that is, if the number of attributes is less than or equal to 10, internal attributes will be generated). If the added attributes exceed the space allocated by the object, They will be stored in the regular properties store (more than 10 will be stored linearly in the Properties store, and more will be stored in a hash table).
• If there are too many attributes in an object (without a definite number), or if there are repeated operations to add or remove attributes, V8 demots the linear storage mode to the nonlinear dictionary storage mode, which slows down the look-up but speeds up the modification of the object’s attributes.

Inspiration for everyday application development?

Take care to minimize refactoring of hidden classes that the V8 engine triggers when it rebuilds: If the shape of an object changes, it will trigger a rebuild. Shape changes are usually caused by adding or deleting attributes to an object, or changing the data type and order of attributes. Therefore, avoid these situations in daily development:

1. Try to use literals to initialize full object properties at once

2. Try to avoid using the delete method

3. When initializing objects multiple times with literals, ensure that the order of attributes is consistent

doubt

var line = {}
for (var i = 0; i < 10; i++) {
  line[i+'x'] = 'xxx'
}
Copy the code

Why can’t this be a snapshot? Does it have to be a function?