In this paper, starting from vivo Internet technology WeChat public links: mp.weixin.qq.com/s/np9Yoo02p… Author: Li Chao

The array in JavaScript has many features: store different types of elements, array length variable and so on, which is not quite the same as the array structure defined in the data structure or C++, Java and other languages in the array, so the JS array of these features is how to achieve it, we open the V8 engine source, from which to find the answer. V8 on the array to do a layer of encapsulation, so that it has two ways of implementation: fast array and slow array, fast array is continuous memory, through the index of direct location, slow array is the bottom of the hash table, through the calculation of hash value to location. The two implementation methods have their own characteristics, have their own use, will be converted to each other.

The 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. 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 V8 source, find out.

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:

1. 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.

2. 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.

3. Same data type

Since the length of the array is fixed, if the data type is not the same, the two types of data can be stored in int and String respectively. Therefore, the data type must be the same.

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]);  //blackCopy the code


These few lines of code show you what’s unusual about the JS array.

  • First line of code, there are three data types in the array, right?

  • The second line of code 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:

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

  2. The size of the JS array can change dynamically, expanding and shrinking according to the number of elements.

  3. 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.

  4. JS arrays can be traversed using for-each, sorted, or inverted.

  5. JS provides many methods for manipulating arrays, such as array.concat (), array.join (), and array.slice ().

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.

Let’s go and test our hypothesis step by step.

Four, get to the bottom: from V8 source to see the implementation of the array

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.

    Where the index of the 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 ();

    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 notes in the fast and slow, just a simple explanation, its corresponding is fast array and slow array, let’s see how the two forms are implemented.

    1, FAST array (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 of length + 16, then the size of the array is adjusted. Otherwise, the size of the array is adjusted by holes. 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 a dictionary. 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, and then some operations are defined, just like Java’s HashMap, but nothing special about it.

    Now that we know how to implement arrays in two ways, let’s summarize the differences.

    3, fast array, slow array difference

    1. Storage: the fast array is contiguous in memory, while the slow array is scattered in memory.

    2. Memory usage: Since fast array memory is continuous, you may need to carve out a large chunk for it to use, which may also have a lot of empty space, which is relatively expensive memory. Slow arrays do not have empty situations, and are scattered memory, relatively save memory space.

    3. Traversal efficiency: because the fast array is spatial continuous, traversal speed is fast, while the slow array has to find the location of the key every time, traversal efficiency is worse.

    Since there are fast and slow arrays, both have their own characteristics. The storage structure of each array is not invariable. There will be fast and slow array conversions in specific cases.

    Conversion between fast array and slow array

    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. If the added index- current capacity >= kMaxGap (1024) (i.e., there are at least 1024 holes), the array will be converted to a 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.

    2, 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 a space savings of only 50%



    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.

    3. Each has its own advantages

    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.

    let buffer = 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.

    let intArray = 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:



    Seven,

    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’s special about arrays in JavaScript

    3. From V8 source code to study the underlying implementation of JS array

    4. How are the two modes of the JS array converted

    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.

    For more content, please pay attention to vivo Internet technology wechat public account

    Note: To reprint the article, please contact our wechat account: LABs2020.