background

When using the array of JS, it is found that the array of JS can hold different types of elements, and the array length is variable. What?? That’s not the same array I was dealing with before. An array defined in a data structure is a fixed-length, consistent data type storage structure. Arrays in JS are surprisingly special, which is why the word “array” is added to the title. With a face of meng force, open the search engine, find out.

Directory:

  • What is an array
  • Arrays in JavaScript
  • Get to the bottom of it: look at the array implementation from V8 source code
  • Conversion between fast arrays and slow arrays
  • Extension: ArrayBuffer
  • conclusion

What is an array

First, let’s take a look at what an array is. Here’s a wikipedia definition of an array:

There are two key points in the diagram, the same type of contiguous memory.

These two key points are not to be delved into, but to be explained below.

Having looked at the data structure definition, let’s look at the implementation of arrays in a specific language:

Arrays in C, C++, Java, Scala and other languages are realized by dividing a series of continuous, fixed-length space in memory to store a set of limited data structures of the same data type. There are several important concepts involved: continuity, fixed length, same data type, similar to the definition in data structures.

Let’s explain each of these concepts:

continuous

Continuous storage is the characteristic of arrays. The following figure shows the storage diagram of arrays in memory.

It is obvious that each element is adjacent in memory, which is a linear storage structure.

Fixed length

Because the array is contiguous, that means there’s a whole block of memory to hold the array. If it’s not a fixed size, then there’s no way to allocate the area after the array. Memory doesn’t know whether to keep the array or how much space to use. The fixed length limits the amount of memory an array can use, and the space outside the array can be allocated to someone else.

Same data type

Because the length of the array is fixed, if the data type is not the same, it can store an int and a String respectively. Therefore, it is necessary to store the same data type.

And when you look at that, most of you are probably thinking, well, that almost matches what I know about arrays.

So let’s get a little bit more exciting and get into the main dish, arrays in JavaScript.

Arrays in JavaScript

Let’s start with this code:

letArr = [100, 12.3,"red"."blue"."green"];
arr[arr.length] = "black";
console.log(arr.length);    // 6
console.log(arr[arr.length-1]);  //black
Copy the code

These few lines of code show you what’s unusual about the JS array. The first line of code contains three data types in the array. The second line adds a value to the array. The third and fourth lines verify that the array length has changed and the added value has taken effect.

In addition to these, JS arrays have a number of special features, such as:

The JS array can hold more than the above three data types. It can hold arrays, objects, functions, Number, Undefined, Null, String, Boolean, etc.

JS arrays can behave like stacks, providing push() and pop() methods for arrays. You can also behave like a queue, using shift() and push() methods, and you can use arrays like queues.

See here, should be able to see a little hint, bold guess, JS array is not the basic data structure to achieve, should be in the foundation above do some encapsulation. Light guess can’t ah, the technical people have to be realistic, let’s start racing, step by step to verify our guess.

Get to the bottom of it: look at the array implementation from V8 source code

Talk is cheap, show me the code.

The following figure is the source of array in V8:

First, we see that JSArray inherits from JSObject, that is, an array is a special object.

This explains why a JS array can hold different data types. It is an object, and inside it is a key-value.

Let’s use this code to verify:

let a = [1, "hello".true.function () {
  return 1;
}];
Copy the code

Let’s take a look at the underlying implementation using JSVU:

As you can see, the bottom layer is a Map, with keys like 0,1,2,3, and values as elements of the array.

The index of an array is actually a string.

Verify this problem, we continue to look at the V8 source, ready to see the big move! As you can see from the comment, the JS array has two representations, fast and slow. What? Can’t read English? I’ll ask Google to translate it for us!

Fast:

The quick backup storage structure is FixedArray, and the array length <= elements. Length ();

FixedArray is an array-like class implemented by V8 that represents a fixed length of contiguous memory.

Missile:

The slow backup storage structure is a HashTable with numeric keys.

HashTable, as wikipedia explains very well:

A Hash table is a data structure that accesses data stored in memory based on a Key. That is, it accesses records by computing a function on key values that maps the data for the desired query to a location in the table, which speeds up lookups. This mapping function is called a hash function, and the array of records is called a hash table.

Source code notes in the fast and slow, just a simple explanation, corresponding to the fast array and slow array, let’s take a look at how the two forms are implemented.

Fast Elements

Fast arrays are linear storage. Newly created empty array, the default storage is fast array, fast array length is variable, according to the element increase and delete to dynamically adjust the size of storage space, internal is through expansion and contraction mechanism, that look at the source code is how to expand and shrink.

Source code expansion implementation method (C++) :

Calculation of new capacity:

new_capacity = old_capacity /2 + old_capacity + 16

That is, the new capacity after expansion = 1.5 times the old capacity + 16

After expansion, the array will be copied to the new memory space, source code:

After expanding, let’s see how to shrink an array space when it becomes redundant.

Implementation of contraction in source code (C++) :

If the size of the array is >= 2 times the length of the array + 16, then the size of the array is adjusted, otherwise the size of the object is adjusted. Fills uninitialized positions.

And if so, how much?

Take a look at this code in the figure above:

Elements_to_trim is the size that needs to be shrunk, depending on length + 1 and old_length, to shrink all or only half of the space.

Having explained enlargement and reduction, let’s look at the objects I just mentioned.

Holes are objects that have space allocated in an array, but no place to store elements. For holes, there’s a special mode in Fast arrays, and there’s an extension in Fast Elements mode called Fast Holey Elements mode.

The Fast Holey Elements pattern works well with holes in an array, where only some indexes hold data and none of the others are assigned.

So when will it be Fast Holey Elements?

When an array has a void, an index that does not have an assigned value will store a special value so that it can be accessed with undefined. In this case it is Fast Holey Elements mode.

The Fast Holey Elements mode dynamically allocates contiguous storage space, which is determined by the maximum index value.

When creating an array, V8 defaults to using Fast Elements mode if the capacity is not set.

Let a = new Array(10); let a = new Array(10); In this case, there is a void inside the array, which is implemented in Fast Holey Elements mode.

Verify this by calling the underlying implementation of the V8-Debug version using JSVU:

HOLEY_SMI_ELEMENTS is a Fast Holey Elements mode.

If an Array is initialized, for example let a = new Array(1,2,3); In this case, there is no void, which is implemented in Fast Elements mode.

Validation:

This PACKED_SMI_ELEMENTS is the Fast Elements mode.

Let’s take a look at the slow array:

Slow Array (Dictionary Elements)

A slow array is an in-memory form of hash table. You save memory by not having to carve out large chunks of contiguous storage, but because you need to maintain such a HashTable, it’s less efficient than fast arrays.

The structure of a Dictionary in the source code

As you can see, there is a HashTable inside, which then defines some operations similar to Java’s HashMap.

So if we have fast and slow arrays, we can’t store the same structure. We should also have fast and slow array conversions in specific cases. Let’s see what happens when the conversions happen.

Conversion between fast arrays and slow arrays

Fast – > slow

V8 to determine whether fast array should be converted to slow array source:

Key code:

1. New capacity >= 3 * Expanded capacity * 2, will be converted to a slow array. 2, Add index- current capacity >= kMaxGap (1024) (at least 1024 voids) to slow array.

Let’s focus on the second case of critical code.

KMaxGap is a constant in the source code with a value of 1024.

That is, when the array is assigned to a value that is much larger than the current array’s capacity + 1024 (there are more than or equal to 1024 voids), allocating a large amount of space to the array will likely result in a waste of storage space, which will be converted to a slow array for space optimization.

Code real hammer:

let a = [1, 2]
a[1030] = 1;
Copy the code

An array with only three elements and a value at position 1030 has more than 1024 holes in the middle, making it a slow array.

To verify this:

As you can see, the array is indeed a dictionary. Success!

Okay, so once we’ve seen the fast array to the slow array, we can see the slow array to the fast array.

– > slow fast

For an array in a hash table implementation, V8’s heuristic checks its space usage each time it grows and converts it to fast array mode if its empty elements are reduced enough.

V8 should be converted to fast array judge source:

Key code: A slow array is converted to a fast array when the elements of the slow array can be stored in a fast array with a length between SMI and only 50% space savings

Let’s write code to verify this:

letA = [1, 2]; a[1030] = 1;for (let i = 200; i < 1030; i++) {
    a[i] = i;
}
Copy the code

As we said above, adding a value above position 1030 will result in more than 1024 voids, and the array will be implemented in Dictionary mode.

So now we add a few more values to this array to fill in the holes, assign values between 200 and 1029, so that the slow array no longer takes 50% less space than the fast array, and what magic happens?

As you can see, the array is in Fast Holey Elements mode.

Is fast array storage space continuous, efficient, must be better? It’s not.

Each have advantages and disadvantages

Fast array is in the way of space for time, the application of large contiguous memory, improve 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.

Extension: ArrayBuffer

In ES6, JS also introduced arrays that can allocate contiguous memory as needed. This is called an ArrayBuffer.

ArrayBuffer requests a specified binary size from memory, but cannot manipulate it directly. You need to build a view using ArrayBuffer to manipulate the memory.

var bf = new ArrayBuffer(1024); 
Copy the code

This line of code requests 1KB of memory. But the arrayBuffer cannot be manipulated directly; it needs to be assigned to a view to manipulate memory.

var b = new Int32Array(bf);
Copy the code

This line of code creates an array of signed 32-bit integers, each of which is 4 bytes long, i.e. 1024/4 = 256 bytes.

Code verification:

conclusion

Is your brain buzzing when you see this? Let’s take a breath and review. Here are a few things we talked about in this post:

1. What does an array look like in the traditional sense

2. What makes arrays special in JavaScript

3. Study the underlying implementation of JS array from V8 source code

4, How to convert the two modes of JS array

5, ArrayBuffer

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

Understanding the underlying implementation of arrays can help you write more efficient code.