Continue to share the theme of the last time, again to talk about some details of the V8 engine optimization processing, interested in the first phase of the students can see: Google V8 engine analysis

Writing in the front

Objects play a very important role in JavaScript. In this share, we hope to explore the performance optimization of V8 engine in object handling from the perspective of the underlying mechanism, and what interesting enlightenment or advice can be brought to our daily work?

Object attribute optimization

Fast properties in V8 · V8

From a language perspective, objects in JavaScript are like dictionaries, with strings as key names and arbitrary objects as key values that can be read and written from. The scope of this discussion of fast and slow attributes is limited to the internal attribute lookup of a single object, and does not cover the scenario of searching up the chain from the prototype.

V8 does not fully use the dictionary structure to store data, because we know that nonlinear structures are less efficient than linear structures (continuous memory allocation is significantly better than non-continuous space lookup), but uses a more complex set of strategies to improve storage and lookup performance.

Let’s start with a code example:

function testV8() { // Define any combination of keys and values, such as integers, decimals, and strings

    this[1] = 'test-1'

    this["B"] = 'foo-B'

    this[50] = 'test-50'

    this[8] = 'test-8'

    this[3] = 'test-3'

    this[5] = 'test-5'

    this["4"] = 'test-4'

    this["A"] = 'foo-A'

    this["C"] = 'foo-C'

    this[4.5] = "Foo - 4.5" 

}

const testObj = new testV8();

for (let key in testObj) {

  console.log(`${key}:${testObj[key]}`);

}
Copy the code

The result of key-value output by the console:

After several prints, we found that the output order was consistent, without randomness, but also did not output in the order we defined. Based on this phenomenon, we will explore the design idea of object attributes in V8 engine.

In V8, two linear data structures are used to store and access these properties to improve performance.

If the array attributes (sort attributes) and named attributes (general attributes) are both present and the array attributes are prioritized for sorting. In the above example, “4” is converted to a numeric integer and the floating point “4.5” is converted to a string. V8 first reads all elements sequentially from the Elements attribute. All elements are then read in the properties property to complete an index operation. Let’s use the Chrome debugging tool Snapshot for example:

But why doesn’t the object in the above snapshot show the properties property? This relates to another optimization strategy of V8: In-object Properties.

In-object property(In-object Properties)

When the two linear structures are used for storage, there will be an obvious extra step in the query of Properties. It is necessary to first query the object corresponding to Properties (one more addressing process), and then check the value of a corresponding key from the Properties object. V8 in order to improve the efficiency of this process, The idea of attributes in the object is proposed: when the number of attributes of the object is less than 10, the attribute key is directly stored in the attributes in the object. If the value of a key needs to be queried, the corresponding key value can be directly obtained from the object.

Let’s verify again:

function testV8(properties, elements) {
  // Add indexable attributes

  for (let i = 0; i < elements; i++) {
    this[i] = `element${i}`;
  }

  // Add general attributes

  for (let i = 0; i < properties; i++) {
    const prop = `property${i}`;

    this[prop] = prop; }}const testobj = new testV8(15.10);

for (let key in testobj) {
  console.log(`${key}:${testobj[key]}`);
}

Copy the code

Fast properties

Attributes stored in linear data structures can be accessed through indexes, but there is a disadvantage that deletion is not efficient.

Slow attribute

V8 uses “slow attributes” when there are too many attributes, with independent nonlinear data structures (dictionaries) inside the attributes’ objects.

When the number of Properties is not too high, the index of Properties is ordered (fast Properties), but when the number of Properties is too high, it becomes unordered dictionary-type storage (slow Properties).

const testobj = new testV8(10.10);

%DebugPrint(testobj); 
Copy the code

const testobj1 = new testV8(150, 100);

%DebugPrint(testobj1); 
Copy the code

Why do we use the slow property instead of the fast property of all linear structures?

To put it simply: when the number of attributes is large, fast attributes are not necessarily accessed faster than slow attributes.

We can calculate it roughly once: suppose that the cost of a hash operation is equal to the time of n simple bit operations. An object has M attribute values. If all fast attributes are used, the query speed is equal to the sum of M simple bit operations. If the slow attribute is used, only one hash operation (the cost of n bits operation) + two-dimensional linear comparison (the value of the corresponding key is obtained after comparing the key value) is required, and the cost of linear comparison is far lower than the cost of one hash operation. Under such estimation, when M > 2n, Slow attributes are queried faster than fast attributes.

In another scenario, when attributes are frequently inserted or deleted for an object, if fast attributes are used all the time, the query efficiency of linear structure is O(1), but the efficiency of insertion or deletion becomes O(n), at which point V8 will degrade to slow attributes.

Hidden Classes

Static languages, when create a type, can’t change again, properties can access through the fixed offset, but not in js, the information such as the type, the value attribute of an object can change at any time, that is to say, running to get the final attribute memory offsets, V8 attributes of the object in order to improve retrieval performance, The concept of Hidden Class is designed. Each object has a corresponding Hidden Class. V8 dynamically updates the corresponding memory offset to the Hidden Class every time the property of the object changes.

  • Each object has its own hidden class: the corresponding Map attribute in the above example is the hidden class object.
  • The hidden class records the descriptors for each attribute in the object. It holds the attribute key and Pointers to the array of descriptors. The descriptor array contains information about named attributes, such as the name itself and where the value is stored, but only named attributes are stored, not integer class attributes

  • When an object creates a new property, or an old property is deleted, V8 creates a new hidden class and points to the old hidden class via the back_pointer pointer. The new hidden class records only the changed property information, and the object’s pointer to the hidden class points to the new hidden class.
const testobj1 = new testV8(2.3);

const testobj2 = new testV8(2.3);

testobj2.new = "new";
Copy the code

  • When an object creates a new property, it checks the transition information of the object’s hidden class. If the transformation information contains the same conditions as the current property change, the object changes its hidden class to the class recorded in the transformation information, rather than creating a new hidden class.
const testobj1 = new testV8(2.3);

const testobj2 = new testV8(2.3);

const testobj3 = new testV8(2.3);

testobj2.new = "new"; // 

testobj3.new = "new"; // Testobj2 3 uses a hidden class instead of creating a new one
Copy the code

At the bottom of the engine, V8 creates a transiton tree that links the hidden classes together, adding attributes in the same order ensures that the references to the hidden classes are the same.

An array with holes

When we went to the query in an array of elements, if the array itself does not exist, according to the principle of prototype chain, will go up query, thus increasing the “redundant” overhead, in V8 added to all full of (the packed) determine whether an array, if the array is under the condition of the packed, check less than the value of the corresponding Instead of following the chain of archetypes in the array, you query directly in the current scope.

const a = [1.2.3];

delete a[1];

a.__proto__ = {1:2};

console.log(a[1]); / / 2
Copy the code

A started out as a fully filled Array, but line 2 removed the second element. V8 also added a _hole to mark the missing element, indicating that A was no longer a full Array, and that it would then be queried in accordance with the prototype chain principle. This strategy is critical for querying arrays.

const a = new Array(10); // HOLEY_SMI_ELEMENTS

const b = [1.2.3.4] // PACKED_SMI_ELEMENTS

%DebugPrint(a);

%DebugPrint(b);
Copy the code

Why are arrays also of object type?

const c = [1."hello".true.function () { // Use key-value inside the array

  return 1;

}];

%DebugPrint(c);// PACKED_ELEMENTS
Copy the code

How fast the array

const a = [];

a[9999] = "9999";
Copy the code

If V8 had to follow normal logic, it would have opened 10,000 new lengths, which would have wasted space. V8 would have degraded slow arrays by using the Object.defineProperty(Object, key, descriptor) Api.

So what exactly are fast and slow arrays? We look at the V8 underlying definition of array: source.chromium.org/chromium/ch…

  • The storage structure of Fast mode is FixedArray, and the length is less than or equal to elements. Length. The array can be expanded and reduced by push and POP
  • The storage structure of slow mode is a HashTable (HashTable) with numeric keys, which saves memory by not creating contiguous memory space

Array capacity

The empty array is preallocated to size 4

    // v8/src/objects/js-objects.h 551 
  static const uint32_t kMinAddedElementsCapacity = 16;


  // Computes the new capacity when expanding the elements of a JSObject.
  static uint32_t NewElementsCapacity(uint32_t old_capacity) {
    // (old_capacity + 50%) + kMinAddedElementsCapacity
    // Expansion formula: Original memory capacity (1.5 times) + 16
    return old_capacity + (old_capacity >> 1) + kMinAddedElementsCapacity;
  }
Copy the code
template <typename TIndex>

// Try to expand the element space
TNode<FixedArrayBase> CodeStubAssembler::TryGrowElementsCapacity( TNode
       
         object, TNode
        
          elements, ElementsKind kind, TNode
         
           key, TNode
          
            capacity, Label* bailout)
          
         
        
        {
  static_assert(
      std::is_same<TIndex, Smi>::value || std::is_same<TIndex, IntPtrT>::value,
      "Only Smi or IntPtrT key and capacity nodes are allowed");
  Comment("TryGrowElementsCapacity");
  CSA_SLOW_DCHECK(this.IsFixedArrayWithKindOrEmpty(elements, kind));


  // If the gap growth is too big, fall back to the runtime.

  TNode<TIndex> max_gap = IntPtrOrSmiConstant<TIndex>(JSObject::kMaxGap);

  TNode<TIndex> max_capacity = IntPtrOrSmiAdd(capacity, max_gap);

  GotoIf(UintPtrOrSmiGreaterThanOrEqual(key, max_capacity), bailout);



  // Calculate the capacity of the new backing store. Calculate the new storage space

  TNode<TIndex> new_capacity = CalculateNewElementsCapacity(

      IntPtrOrSmiAdd(key, IntPtrOrSmiConstant<TIndex>(1)));

  // Perform capacity expansion

  return GrowElementsCapacity(object, elements, kind, kind, capacity,
                              new_capacity, bailout);
}
Copy the code

Copy the array to the new memory space after expansion

Array shrinkage capacity

Source.chromium.org/chromium/ch…

The PopImpl method triggers the PopImpl method, which in turn calls the RemoveElement method, which finally calls the SetLengthImpl method to determine whether or not to shrink. If the length of the array is greater than or equal to the length*2 + 16 of the actual content, Otherwise, uninitialized positions are filled with the _hole flag mentioned above. Elements_to_trim is used to calculate the size to trim, and length + 1 and old_length are used to determine whether to trim all or half of the space.

Fast conversion

  • Fast > slow
static const uint32_t kMaxGap = 1024;


static const uint32_t kPreferFastElementsSizeFactor = 3;


class NumberDictionaryShape : public NumberDictionaryBaseShape { 

  public: 

    static const int kPrefixSize = 1; 

    static const int kEntrySize = 3; 

};
Copy the code

  1. If the new capacity of the fast array is >= 3 * the expanded capacity * 2, meaning that it takes up more memory than the HashTable format, the fast array is converted to the slow array.
  2. If the difference between the new index and the original maximum index is greater than or equal to 1024, the fast array will be converted to the slow array.
const a  = [1]

a[1025] = 3;

%DebugPrint(a); 
Copy the code

  • > slow fast

Elements can be stored in fast arrays that are not in the smI range (64 bits -2^31 to 2^32-1) and are converted to fast arrays if the current slow array space savings is less than or equal to 50%.

const a  = [1]

a[1025] = 3;

for (let i = 300; i < 1025; i++) {

    a[i] = i;

}

%DebugPrint(a); 
Copy the code

  • Fast array is the way of space for time, the application of large contiguous memory, improve the execution efficiency.
  • Slow array in time for space, do not need to apply for continuous space, saving memory, but need to pay the cost of efficiency.

Conclusion:

Js array seems to be different, but in fact V8 has made a layer of encapsulation on the bottom implementation, using two data structures to achieve the array, and through the choice of time and space two latitude, optimize the performance of the array.

Inline cache policy(Inline Cache)

Although hidden classes can speed up the search for objects, there is still the search for hidden classes of objects and the search for object attribute values according to hidden classes in V8’s search for object attribute values.

function getXProps(o) {

    return o.x;

}

const o1 = {x:1.y:2.z:3};

const o2 = {x:3.y:100.m:10.n: -3};

for(let i = 0; i < 10000; i++) {

    getXProps(o1);

    getXProps(o2);

}
Copy the code

In this code, the getXProps method is executed repeatedly, looking for the hidden class of the object, looking for the offset of the x property, and finally getting the value of the property from the offset.

Inline Cache, also known as ****IC, is an ancient technique used in Smalltalk virtual machines. It collects key data during code execution and caches it. This information is directly used when executing again, which effectively saves the consumption of retrieving the information again and improves performance.

V8 uses the IC mechanism to maintain a FeedBack Vector for each function. In fact, it uses a table structure to store key information:

Slot (Slot index) Type (Slot type) State of affairs Map (Hidden class address) Offset (attribute offset)
0 Load (Load object properties) Mono (single) xxxxxxxx 8
1 Store (Attribute assignment) Poly real (polymorphism) xxxxxxxx 13
n . Maga (state) . .
  • Singleton: a slot containing only 1 hidden class
  • Polymorphism: A slot that contains 2-4 hidden classes
  • Superstate: A slot containing more than 4 hidden classes

function setProps(o) {

    o.y = 4;

    return o.x;

}

setProps({x:1.z:5});

setProps({x:100.z:20});
Copy the code

Analysis of execution process:

  1. V8 identifies two call points, O.Y and return O.x
  2. At execution time, each call point inserts a cache of data into the FeedBack Vector table
  3. When the setProps method is invoked again, V8 can directly look for the offset of the corresponding attribute in the corresponding slot, and then directly obtain the corresponding attribute value from memory, greatly improving the execution efficiency of V8
  4. The {x:1,z:5} and {x:100,z:20} attributes above have the same name and order, so the hidden class is the same and belongs to a singlet. In the original example, there were two hidden classes, so they correspond to polymorphisms. In polymorphic cases, multiple hidden classes in the map are checked and compared one by one
let data = [1.2.3.4];

let data1 = ['1'.2.'3'.4];

data.forEach((item) = > console.log(item.toString());

data1.forEach((item) = > console.log(item.toString());

// Which is more efficient?
Copy the code

conclusion

  • Try to keep it singly. For example, if you define a public method loadX(obj), try to keep the shape of one of the parameters the same.
  • Try not to add or delete a large number of objects to avoid the degradation of named attributes into slow attributes.
  • Try to keep objects of the same type consistent in their attributes, order, and number. Avoid creating too many hidden classes.
  • Try not to initialize an excessively long array at once without assigning
  • In a real project, it’s important not to worry too much about breaking V8’s underlying optimization mechanisms, but to identify issues that directly affect performance bottlenecks

Next up

V8 garbage collector & Memory Management

Message queue & asynchronous programming

Coroutines and processes

reference

JavaScript engine basics: Shapes and Inline Caches

V8 Hidden class – LINE ENGINEERING

Fast properties in V8 · V8

Explaining JavaScript VMs in JavaScript –