Quick object cloning in JavaScript

Cloning objects in JavaScript is quite a frequent operation. Unfortunately, JS does not provide fast native methods for solving this problem.

For example, the popular Node.JS ORM Sequelize, which we use on the backend of our project, significantly loses performance on the prefetch of a large (1000+) number of rows, only on one cloning . If at the same time, for example, in the business logic, use the clone method of the well-known lodash library - the performance drops tenfold.

But, as it turned out, not everything is so bad and modern JS engines, such as, for example, the V8 JavaScript Engine, can successfully cope with this task, if properly used their architectural solutions. Those wishing to learn how to clone 1 million objects in 30 ms - welcome under the cat, everyone else can immediately see the implementation .

I just want to make a reservation that they have already written a little on this topic. A colleague with Habra even made the node-v8-clone native extension, but it is not built for the latest versions of the node, its scope is limited only by the backend, and its speed is lower than the proposed solution.
')
Let's figure out what wasted CPU time during cloning - these are the two main operations memory allocation and writing. In general, their implementation for many JS-engines are similar, but then we will talk about V8, as the main for Node.js. First of all, in order to understand what takes time, you need to understand what JavaScript objects are.

View JavaScript objects

JS is a very flexible programming language and its properties can be added on the fly, most JS engines use hash tables for their presentation - this gives the necessary flexibility, but slows down access to its properties, because requires a dynamic hash search in the dictionary. Therefore, in the pursuit of speed, the V8 optimization compiler can switch between two types of object representation — dictionaries (hash tables) and hidden classes (fast, in-object properties) on the fly.

V8, wherever possible, tries to use hidden classes to quickly access object properties, while hash tables are used to represent "complex" objects. The hidden class in V8 is nothing more than a structure in memory that contains a table of object property descriptors, its size and references to the constructor and the prototype. For example, consider the classic representation of a JS object:

 function Point(x, y) { this.x = x; this.y = y; } 

If you execute new Point(x, y) , a new Point object will be created. When V8 does this for the first time, it creates a base hidden class for Point , let's call it C0 for example. Since no properties have been defined for the object yet, the hidden class C0 empty.


Executing the first expression in Point ( this.x = x; ) creates a new property x in the Point object. With this, V8:

• creates a new hidden class C1 , based on C0 , and adds to C1 information that the object has one property x , the value of which is stored in the 0 (zero) offset of the Point object.
• updates the C0 transition record (a class transition) informing that if the x property is added to the object described by C0 then the hidden class C1 should be used instead of C0 . The hidden class of the Point object is set to C1 .

Executing the second expression in Point ( this.y = y; ) creates a new property y in the Point object. With this, V8:

• creates a new hidden class C2 , based on C1 , and adds to C2 that the object also has a property y , the value of which is stored in the 1 (first) offset of the Point object.
• updates C1 with a transition record informing that if the y property is added to the object described by C1 then the hidden class C2 should be used instead of C1 . The hidden class of the Point object is set to C2 .

Creating a hidden class each time a new property is added may not be effective, but because for new instances of the same object, the hidden classes will be reused - V8 is trying to use them instead of dictionaries. The mechanism of hidden classes helps to avoid dictionary search when accessing properties, and also allows you to use various class-based optimizations, including inline caching .

In this connection, the ideal object for the compiler will be an object - with a constructor in which the set of its properties is clearly defined, which does not change during execution. Therefore, the most important optimization for speeding up access to the properties of objects during cloning is the correct description of its constructor. The second important part is directly optimizing the read-write process itself, which will be discussed further.

Dynamic code generation

V8 compiles JavaScript code directly into machine code during the first execution, without intermediate code or interpreter. Access to the properties of objects is optimized by inline cache, the machine instructions of which V8 can change right at run time.

Consider reading the properties of an object, during the initial execution of the code, V8 determines its current hidden class and optimizes future references to it, predicting that in this section of the code objects will be with the same hidden class. If V8 was able to predict correctly, then the property value is assigned (or obtained) by a single operation. If, however, it was not possible to predict correctly, V8 modifies the code and removes the optimization.

For example, take the JavaScript code that gets the x property of the Point object:

 point.x 

V8 generates the following machine code for reading x :

 # ebx = the point object cmp [ebx,<hidden class offset>],<cached hidden class> jne <inline cache miss> mov eax,[ebx, <cached x offset>] 

If the hidden object class does not correspond to the cached one, the execution proceeds to the V8 code that handles the absence of the inline cache and modifies it. If the classes correspond to what happens in most cases, the value of the x property is simply obtained in one operation.

When processing multiple objects with the same hidden class, the same advantages are achieved as with most static languages. The combination of using hidden classes to access the properties of objects and using the cache significantly increases the performance of JavaScript code. It is these optimizations that we will use to speed up the cloning process.

Cloning

As we found out from the theory above, cloning will be the fastest if two conditions are met:

• All object fields are described in the constructor - hidden classes are used instead of dictionary mode (hash tables)
• all fields for cloning are explicitly listed - assignment takes place in a single operation due to the use of inline cache

In other words, to quickly clone a Point object, we need to create a constructor that accepts an object of this type and creates a new one based on it:

 function Clone(point) { this.x = point.x; this.y = point.y; } var clonedPoint = new Clone(point); 

In principle, and everything, if not one but - to write such constructors for all types of objects in the system is quite expensive, also, objects can have a complex nested structure. In order to simplify the work with these optimizations, I have written a library that creates cloning constructors for the transferred object of any nesting.

The principle of the library is very simple - it receives an object as input, generates a cloning constructor from its structure, which can later be used to clone objects of this type.

 var Clone = FastClone.factory(point); var clonedPoint = new Clone(point); 

The function is generated via eval and the operation is not cheap, so the performance advantage is achieved mainly if you need to re-clone objects with the same structure. The results of the benchmarking benchmark for the Chromium browser 50.0.2661.102 Ubuntu 14.04 (64-bit) with benchmark.js:

library	operations / sec.
FastClone	16,927,673
Object.assign	535 911
lodash	66 313
Jquery	62,164

Test sources - jsfiddle.net/volovikov/thcu7tjv/25
In general, we get the same results on a real system, cloning is accelerated 100 to 200 times on objects with a repeating structure.

Thanks for attention!

Library - github.com/ivolovikov/fastest-clone

Materials on the topic:
jayconrod.com/posts/52/a-tour-of-v8-object-representation
developers.google.com/v8/design