When I was looking at code related to Lane(formerly called expirationTime) some time ago, I was attracted by this annotation of v8 engine. It turns out that different forms of array creation are handled differently in V8, so the right way to do it can make a big difference to performance. Here’s a note.
React engine handles arrays internally
preface
This article is translated from Elements Kinds in V8 and can be watched with V8 Internals for JavaScript Developers by Mathias Bynens.
React source code
export function createLaneMap<T> (initial: T) :LaneMap<T> {
// Intentionally pushing one by one.
// https://v8.dev/blog/elements-kinds#avoid-creating-holes
const laneMap = [];
for (let i = 0; i < TotalLanes; i++) {
laneMap.push(initial);
}
return laneMap;
}
Copy the codeA brief introduction to the createLaneMap method, which initializes the eventTimes, Context Times, and Entanglements properties in the FiberRoot object, where TotalLanes is the constant 31, This is because the Lane is represented by the 32-bit binary, remove leading binary 0 b, just length is 31, such as 0 b0000000000000000000000000000000.
The body of the
Attributes of objects in JavaScript can be of any type, which means they can be numeric, Symbol, or even if you use undefined, NULL, Date, and so on as keys. In the case of numeric key, the JavaScript engine makes some optimizations, the most typical of which is array indexing.
In V8, attributes with integer names (most commonly in the form of objects generated by Array constructors, i.e., new Array()) are treated specially. Although in many cases these digitally indexed attributes behave like other attributes, V8 has chosen to store them separately from non-numeric attributes for optimization purposes. Internally, V8 even gives these attributes a special name: elements. Objects have attributes that map to values, and arrays have indexes that map to elements.
While this internal code is never directly exposed to JavaScript developers, it explains why some code patterns are faster than others.
Common element kinds
As the JavaScript code runs, V8 keeps track of each Element Kinds in the array. This trace information allows V8 to make some optimizations to the specified types in the array. For example, when you call Reduce, Map, or forEach, V8 can optimize these operations based on the element Kinds included in the array. For JavaScript, it doesn’t distinguish between integers, floats, or Doubles, but V8 does make a precise distinction.
The array starts with [1, 2, 3] and its Element Kinds (elements kind) are defined as PACKED_SMI_ELEMENTS in v8; When we append a floating point number, Element KINDS becomes PACKED_DOUBLE_ELEMENTS, and when we append a string element, Element Kinds becomes PACKED_ELEMENTS.
const arr = [1.2.3]; // PACKED_SMI_ELEMENTS
arr.push(4.56); // PACKED_DOUBLE_ELEMENTS
arr.push("x"); // PACKED_ELEMENTS
Copy the codeEven if we don’t know the difference between the three elements at this point, we have a sneaking sense that V8 will be doing something to optimize arrays of pure ints. Let’s look at these three markers in detail:
- SMI stands for Small Integers
- If there are double elements, the array is marked as
PACKED_DOUBLE_ELEMENTS - For elements of common type, the array will be marked as
PACKED_ELEMENTS
It is important to note that the conversion of Element Kinds is irreversible and can only go from special to general, which means that PACKED_SMI_ELEMENTS can be converted to PACKED_DOUBLE_ELEMENTS, but not vice versa. Even if you removed 4.56 later, the array would still be PACKED_DOUBLE_ELEMENTS.
To summarize, we can see that V8 does these things for arrays:
- V8 assigns Element Kinds to each array
- Element Kinds is not static and will change at run time as we operate on the array
- The conversion of Element Kinds is irreversible and can only go from special to general
PACKED vs. HOLEY kinds
All of the above tags are for dense arrays. What is a dense array? For example [1, 2, 4.56, ‘x’], its length is 4, and all four positions have elements when initialized.
The opposite is a sparse array, as in this example: Array for PACKED_ELEMENTS originally, but we’re arr [8] set up the position of an element, known as memory allocation space is according to the length of the array, this leads to arr [5] ~ arr [7] nothing, for this kind of array, Its elements kind is marked as HOLEY_ELEMENTS.
// HOLEY_ELEMENTS
const arr = [1.2.4.56."x"];
arr[8] = "hahaha";
Copy the codeV8 makes this distinction because operating a Packed Array gets more optimization than a Holey Array. For The Packed Array, most operations can be performed efficiently, while for the Holey array, it is expensive to check the prototype chain (which will be discussed later).
Elements kind
This is the end of the basic elements Kind conversion relationship. Of course, V8 currently offers a total of 21 different ElementsKind, all in the enumeration type ElementsKind, and each type has its own optimization.
From this diagram, we can see that the transformation relationship is irreversible and can only go from a special type to a universal type. More specific element types support finer-grained optimizations, and the lower to the right of the element type, the slower the operation on the array is likely to be. For best performance, avoid unnecessary conversions to those generic types and stick to the specific type that best suits the situation.
Performance tips
For the most part, we don’t need the subtle type conversion of CARE. However, there are a few things you can do to get maximum performance.
Avoid reading beyond the length of the array
This makes sense, for example, if an array arr is of length 5, but you access arr[42] because the array does not have an attribute called 42, the JavaScript engine must look up the prototype chain until the top of the prototype chain is null. Once the load encounters this, V8 remembers that “this load needs to handle special cases,” and it will never again be as fast as it was before the read was out of bounds.
In this example, after reading all the elements in the array, one more element is read out of the loop. You may look at this code and scoff because we almost 100% don’t write this, but very little code in jQuery uses this pattern.
for (let i = 0, item; (item = items[i]) ! =null; i++) {
doSomething(item);
}
Copy the codeInstead, we’ll just use the simplest for loop.
const n = items.length;
for (let index = 0; index < n; index += 1) {
const item = items[index];
doSomething(item);
}
Copy the codeI <= array.length is 6 times slower than I < array.length.
function Maximum(array) {
let max = 0;
for (let i = 0; i <= array.length; i++) {
// BAD COMPARISON!
if (array[i] > max) max = array[i];
}
return max;
}
Copy the codeFinally, if your collection is iterable, such as NodeList, Map, Set, use for… “Of” is also a good choice. For arrays, you can use built-in prototype methods such as forEach. Nowadays, whether it is for… Of or forEach, both of which perform as well as a traditional for loop.
To expand a bit, Airbnb’s no-restricted-syntax blocks for… The reasons are as follows. But I think for… Of is still normal, for… Note the hasOwnProperty restriction.
iterators/generators require regenerator-runtime, which is too heavyweight for this guide to allow them. Separately, loops should be avoided in favor of array iterations.
Avoid elements kind transitions
Do not use elements Kind conversions because they are irreversible. Here’s a little bit of knowledge, although almost 100% of you can’t do it, but I’ll post it. NaN, Infinity, and -0 all cause arrays of pure Int to become PACKED_DOUBLE_ELEMENTS.
const arr = [1.2.3, +0]; // PACKED_SMI_ELEMENTS
arr.push(NaN.Infinity, -0); // PACKED_DOUBLE_ELEMENTS
Copy the codePrefer arrays over array-like objects
Some objects in JavaScript — especially in the DOM — have a lot of array-like objects, and sometimes you create array-like objects yourself (well, only in interviews).
const arrayLike = {};
arrayLike[0] = "a";
arrayLike[1] = "b";
arrayLike[2] = "c";
arrayLike.length = 3;
Copy the codeThe code above has index and length, but it lacks the prototypical methods of a real array, even though you can use it with the call or apply array syntax.
Array.prototype.forEach.call(arrayLike, (value, index) = > {
console.log(`${index}: ${value}`);
});
// This logs '0: a', then '1: b', and finally '2: c'.
Copy the codeThis code to use do not have what problem, but it’s still slower than the real array to call forEach, so if necessary (for example, to the array of a large number of operations), you can put the class array object into a true array, the subsequent operations to do again, perhaps the sacrifice is worth trading space for time method.
const actualArray = Array.prototype.slice.call(arrayLike, 0); // First convert to a real array
actualArray.forEach((value, index) = > {
console.log(`${index}: ${value}`);
});
// This logs '0: a', then '1: b', and finally '2: c'.
Copy the codeAnother classic array of classes is argument. As in the above example, you can also use the prototype method of an array with call or apply. But with the popularity of ES6, we should use residual arguments, because residual arguments are real arrays.
const logArgs = (. args) = > {
args.forEach((value, index) = > {
console.log(`${index}: ${value}`);
});
};
logArgs("a"."b"."c");
Copy the codeAvoid polymorphism
If you have a method that handles arrays of different element types, it may result in polymorphic operations, which are slower than code that operates on a single element type. For example, if you write an array iterator of your own, the iterator can pass in an array of pure numeric type or any other array of random type, that’s polymorphic. It is important to note, of course, that the prototype methods built into arrays are already optimized within the engine and are out of our consideration.
In the following example, the each method first passes an array of type PACKED_ELEMENTS, so V8 uses inline cache (IC) to remember this particular type. V8 will “optimistically” assume that array.length and array[index] access functions within each are monotonic (i.e. there is only one type of element). So V8 can reuse the previously generated code if the array passed to the method is still PACKED_ELEMENTS.
But passing an array of type PACKED_DOUBLE_ELEMENTS, PACKED_SMI_ELEMENTS, causes array.length and array[index] to be marked polymorphic inside each. V8 needs to check PACKED_ELEMENTS once more each time it calls each, and add a new PACKED_DOUBLE_ELEMENTS, which creates potential performance problems.
const each = (array, callback) = > {
for (let index = 0; index < array.length; ++index) {
constitem = array[index]; callback(item); }};const doSomething = (item) = > console.log(item);
each(["a"."b"."c"], doSomething); // PACKED_ELEMENTS
each([1.1.2.2.3.3], doSomething); // PACKED_DOUBLE_ELEMENTS
each([1.2.3], doSomething); // PACKED_SMI_ELEMENTS
Copy the codeAvoid creating holes
React source code React source code Method one: you create an empty array of length 3, that array is sparse, and the array will be marked as HOLEY_SMI_ELEMENTS. Even if we end up filling up the array, it won’t be packed, it will still be marked as Holey. Method 2, the most elegant, is labeled PACKED_ELEMENTS. Of course, if you don’t know exactly how many elements there are, then method three, pushing elements into an empty array, is the best choice.
// Method 1 (not recommended)
const arr = new Array(3);
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
2 / / way
const arr = ["a"."b"."c"];
3 / / way
const arr = [];
arr.push(0);
arr.push(1);
arr.push(2);
Copy the codeThe last
All in all, this is a cool article aimed at broadening my knowledge. At 90% or more, the array returned from the back end is already of type PACKED_ELEMENTS, so it’s the React framework that really cares about this kernel-level optimization. There is also a case where we can optimize it a little bit. Do you initialize your backpack with new Array(n).fill(false) when you swipe dynamic programming? (Manual dog head.