Discuss the efficiency of JS array in memory

“This is the 18th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Discuss the efficiency of JS array in memory

JS array

The structure of the JS array we are familiar with is similar to that of other languages, that is, the physical memory is continuous, so this leads to the lower the number of moves of the array members, the more efficient it is. Generally, the array will be allocated to a contiguous segment of memory, like this

You might wonder why you’re drawing a border, but our array is defined by default, so when we want to add elements to an array, we need to change its length.

Efficiency is

JS provides several apis that make it easy to add elements to arrays, such as push and unshift

Push () adds an element to the end of the array. We don’t need to manipulate any other elements, just this,length+=1
Unshift () adds an element to the head of the array. What we see is that as soon as we add an element to the head of the array, all the members of the underlying array need to be moved backwards, from end to end, as shown below, which highlights the poor performance.

For example, 🌰

To make a clear comparison, our unshift takes 0.24ms and push takes 0.8ms, but the time is exponentially increased by the number of elements moved.

function _shift() {
    var arr = []
    console.time('_shift')
    for (let i = 0; i < 1000; i++) {
      arr.unshift(1)
    }
    console.timeEnd('_shift')
  }
  _shift()
function _push() {
    var arr = []
    console.time('_push')
    for (let i = 0; i < 1000; i++) {
      arr.push(1)
    }
    console.timeEnd('_push')
  }
  _push()
Copy the code

Discontinuous memory problem

In addition, we all know JS array can be stored in the same array of different data types of data, so it caused the JS array is allocated for memory, is to look at our array member type, when the array members for the same class, is continuous memory, in the presence of members of the array array, a string, then allocates the contiguous memory, Multiple discontiguous memory will form a linked list, which can cause inefficiency when storing large orders of data. Now let’s do a time comparison between the same array members and the different array members. I’ve increased the number to the seventh power of 10 for effect

  function _diff() {
    var arr = new Array(10000000)
    arr.push({ name: "cxy" })
    console.time('_diff')
    for (let i = 0; i < 10000000; i++) {
      arr[i] = i
    }
    console.timeEnd('_diff')
  }
  _diff()
  function _same() {
    var arr = new Array(10000000)
    console.time('_same')
    for (let i = 0; i < 10000000; i++) {
      arr[i] = i
    }
    console.timeEnd('_same')
  }
  _same()
Copy the code

In the end, the difference is clear: an array with non-contiguous memory takes several times as long to operate as an array with contiguous memory.

Discuss the efficiency of JS array in memory