How JavaScript Array Works Internally?

Introduction#

All JavaScript engine have their own implementation of the functions and methods but in this article, we'll consider the implementation of Google's V8 engine which is one of the most famous JavaScript engines.

Objects in JavaScript#

Objects in JavaScript are responsible for holding the mapping between key-value pairs. These keys could be any random string. Even if we pass a number as a key, JavaScript will first coerce it to string.

1const foo = {
2  12e2: 'bar',
3}
4
5console.log(foo[12e2]); // bar
6console.log(foo['12e2']); // undefined
7console.log(foo['1200']); // bar
8

Here, key 12e4 is first coerced to string and becomes 1200 then bar value is linked to it. Same thing happens while accessing the value also. 12e2 will first be coerced to string and then foo will lookup for key 1200 and return bar value. But in the case of string literal 12e2, no coercion occurs as a result it was not able to find any value with such key and therefore returns undefined.

Arrays in JavaScript#

Arrays are also a type of object in JavaScript but with only numeric keys. JavaScript engine can optimize these special objects with purely numeric keys Google's V8 javascript engine is entirely written in C++ but C++ arrays can only store a similar type of data.

Element Kind in JavaScript#

There is no concept of int, float and double in JavaScript. JavaScript categorizes them as number type but the underneath implementation cares a lot about type of elements being stored in the array. V8 engine tries its best to optimize the array. The operations that are performant for int data type can't be as much performed for string or double data type. To keep the track of stored elements in a array and apply specific optimizations, V8 assigns a element kind to each array. V8 uses these element kind just to internally distinguish between the different type of arrays

There are around 22 different element kind that V8 can assign to an array. Each of them comes with a different performance optimizations. In this article we will consider these main element kind and later will look at some of the performance mistakes that we can avoid when it comes to arrays in JavaScript.

1. PACKED_SMI_ELEMENTS
2. PACKED_DOUBLE_ELEMENTS
3. PACKED_ELEMENTS
4. HOLEY_SMI_ELEMENTS
5. HOLEY_DOUBLE_ELEMENTS
6. HOLEY_ELEMENTS

Packed Elements#

Packed elements means that there are no holes (which we'll see later) in the array. It is the most performant kind of array in V8. It is also the default kind when we initialize an empty array.

1const foo = [1, 2, 3];
2// Packed Element
3

Holey Elements#

Holey elements means that there are gaps in the array. It represents the sparse array. These type of array will not be as performant as the packed array.

1const foo = [1, 2, 3];
2foo[100] = 4;
3// Holey Element
4

Packed/Holey SMI Elements#

SMI means that the array is of type Smi which is a signed 32-bit integer.

1const foo = [1, 2, 3]; // element kind: PACKED_SMI_ELEMENTS
2
3const bar = [];
4bar[100] = 4; // element kind: HOLEY_SMI_ELEMENTS
5

Packed/Holey Double Elements#

Double means that there are one or more elements of type Double in the array.

1const foo = [1, 2.5, 3]; // element kind: PACKED_DOUBLE_ELEMENTS
2
3const bar = [];
4bar[100] = 7.4; // element kind: HOLEY_DOUBLE_ELEMENTS
5

Packed/Holey Elements#

The elements that are not of type Smi or Double are considered regular elements.

1const foo = [1, 2.5, 3, 'bar']; // element kind: PACKED_ELEMENTS
2
3const bar = [1, 2, 2.5];
4bar[100] = 'foo'; // element kind: HOLEY_ELEMENTS
5

The element kind could also change dynamically as we add or remove elements from the array. Let's look at the below example for better understanding.

1const foo = []; // element kind: PACKED_SMI_ELEMENTS
2
3foo.push(1); // element kind: PACKED_SMI_ELEMENTS
4foo[100] = 2; // element kind: HOLEY_SMI_ELEMENTS
5foo.push(5.2); // element kind: PACKED_DOUBLE_ELEMENTS
6foo.pop(); // element kind: PACKED_DOUBLE_ELEMENTS
7foo.push('bar'); // element kind: HOLEY_ELEMENTS
8

At the starting PACKED_SMI_ELEMENTS is the default element kind. When we push 1 to the array it still remains PACKED_SMI_ELEMENTS. After adding holes in the array, it changes element kind to HOLEY_SMI_ELEMENTS. In the same way, pushing 5.2 makes the element kind move to the HOLEY_DOUBLE_ELEMENTS.

One thing to notice here is that once the element kind is downgraded to PACKED_DOUBLE_ELEMENTS it stays there. Even after removing the only double element 5.2 from the array, element kind is still PACKED_DOUBLE_ELEMENTS At the end, adding bar to the array makes the element kind move to HOLEY_ELEMENTS.

Here is the diagram of the element kind transitions for better understanding.

JavaScript internally uses C++ vectors to store the packed arrays. It will grow dynamically. Once the holes are introduced, the underneath implementation will be upgraded to the hashmap. Once the underneath implementation is upgraded it cannot be degraded even if you remove that element. So time and complexity can vary a lot by just your usage of the array.

General Performance Tips#

Never access the array with out of bounds index#

1const foo = [1, 2, 3];
2
3console.log(foo[100] ?? 'some placeholder'); // 'some placeholder'
4

The above example is such a common practice followed by many JS developers, here we are accessing 100 index of the array.However, the length of array is 3 so the index is out of bounds. In this case, the V8 engine has to perform the expensive prototype chain lookup. This will affect the performance of V8 engine as V8 will be cautious about this situation and it will not remain as performant it was before accessing the out of bound key.

Avoid giving the initial capacity to the array#

1const foo = new Array(3); // element kind: HOLEY_SMI_ELEMENTS
2
3foo[0] = 1;
4foo[1] = 2;
5foo[2] = 3;
6

This will create a HOLEY_SMI_ELEMENTS array with the initial capacity of 3. However, we are only storing PACKED_SMI_ELEMENTS elements. Why should we lose the optimizations of PACKED_SMI_ELEMENTS?

1const foo = []; // element kind: HOLEY_SMI_ELEMENTS
2
3foo.push(1);
4foo.push(2);
5foo.push(3); // element kind: PACKED_SMI_ELEMENTS
6

Instead of giving the initial capacity to the array we can just create a empty array and push the elements to it. This will ensure the element kind is the same

Conclusion#

So this was the quick deep dive into how V8 engine internally handles arrays. At the end we also discuss some of the tips to make your array performant. If you like this article, please share it with your friends.