Understanding Packed vs Holey Arrays

Packed Array and Holey Array

So, I guess you are here after watching Hitesh Sir, tutorial on javascript, If you are at beginner or intermediate level you must do that. Also I’m embedding his video below. Now lets discuss.

https://youtu.be/ZRS485LxX0s?feature=shared

Based on occupancy of indices, v8 engine internally classifies arrays in two category.

Packed Array: A packed array is an array that has a value for every index. Packed array are the most optimised array. It is like bread and butter for javascript engines
Holey Array: A holey array is an array that has no value for some of the indices or at least one index. Performing operations on these arrays are costly task.

eg. Accessing elements in array highly efficient and only cost O(1). But this cost effective accessing of elements happens until array is holey. As Soon as array becomes holey its efficiency of accessing array changes to O(n)

How V8 engine stores array?

A packed array is an array which have some value for every index. Javascript engines tries to keep arrays packed as long as possible.

  packedArray = [11,65,23,73,97,24,90,24]

  How v8 engine internally represents this: 
  | 11 | 65 | 23 | 73 | 97 | 24 | 90 | 24 |

  Memory: Continuous

A Holey array is an array which has no value for some of the index or atleast one of the index.

  holeyArray = [11,65, ,73, ,24,90,24]
  How v8 engine internally represents this:
  {
      0: 11,
      1: 65,
      3: 73,
      5: 24,
      6: 90,
      7: 24
  }
  Memory: Discreate(Map/dictionary like structure)

Why Javascript engines do this?
- So one question might have been raised in your brain why is it that js engine stores array in different pattern? The answer is simple memory optimisation, Engines doesn’t know you are going to access these elements or not but one thing is sure you are going to save this in memory and by passing values to indices we do it everytime.

How v8 engine access the elements of array?

Since, now we have learned engines stores array. Lets understand how it access elements of array? Let us consider two array

const packedArray = [1, 2, 3, 4, 5]
const holleyArray = [1, , 3, , 5]

Step-1: The bound check
- Engine first check the the starting position of array in memory also known as base address. Then checks the length of array and compare this with requested index. If index is out of the range then it returns the undefined value
```
  const packedElement = packedArray[3]
  const holeyElement = holeyArray[3]
  // Bound check passed here
```
Step-2: Property check (If array passed the bound check)
- For packed Array, engine returns the value array.
```
  const packedElement = packedArray[3] // 4
  // Here value of packedElement we will get as 4
```
- For holey Array, It will try to check the index and will find nothing.
```
  const holeyElement = holeyArray[3]
  // Engine will not be able to find any value her
```
  - Now, It might be possible that this property exist in the prototype of array and if fails in here. It will go further and check for Object.hasOwnProperty as array in javascript are also object. If this also fails then it will return undefined.

        const holeyElement = holeyArray[3]
        //Object.hasOwnProperty(3)

Now, lets see in code

Okay Enough of the talking, now lets implement the code and check whatever I’m saying is correct or not.

const LENGTH = 2 ** 20;
const CYCLES = 10;

const createPackedArray = (length) => {
  const arr = [];
  for (let i = 0; i < length; i++) {
    arr.push(Math.floor(Math.random() * 1000 + 100));
  }
  return arr;
};

const createHoleyArray = (length) => {
  const arr = [];
  for (let i = 0; i < length; i++) {
    if (i > Math.floor(Math.random() * length)) {
      arr[i] = Math.floor(Math.random() * 900 + 100);
    }
  }
  return arr;
};

const measureExecutionTime = (array) => {
  const start = performance.now();
  for (let i = 0; i < array.length; i++) {
    let temp = array[i];
  }
  return performance.now() - start;
};

const output = (cycles, length) => {
  let results = [];
  for (let i = 1; i <= cycles; i++) {
    const holeyArray = [...createHoleyArray(length)];
    const packedArray = [...createPackedArray(length)];

    const holeyTime = measureExecutionTime(holeyArray);
    const packedTime = measureExecutionTime(packedArray);

    results.push({
      "Holey Array Time (ms)": holeyTime.toFixed(3),
      "Packed Array Time (ms)": packedTime.toFixed(3),
      "Difference (ms)": (holeyTime - packedTime).toFixed(3),
    });
  }
  return results;
};

console.table(output(CYCLES, LENGTH));

Expected Output of the code

Analysis of output

In the above code we try to access elements of two really large array. We ran this cycle for 10 time and 9 out of 10 time packed array performed better and got accessed quicker.

Cause of Holey Array and How to Avoid It

What causes holey array

A holey array can never be converted to packed array once again.
Initialising the array using new Array(length) cause holey array.

How to avoid holey array

Initiate an array with 0 length arr=[];
Assign undefined value to every index you are not sure about. This way you will not get holey array.
Try using existing array methods rather than defining and using your own.

const optimisedInitialisation = []; 

const unoptimsedInitialisation = new Array(5)
console.log(unoptimsedInitialisation) // [ <5 empty items> ]

const array = [undefined, undefined, undefined]
console.log(array) // [undefined, undefined, undefined]
// No empty items in variable array

Conclusion

Holey array are made to optimise the space used by application/software. In order to avoid holey array don’t forget the reason why developers of this engine have added this different approaches of saving arrays. The final optimised version of code should not only have fast execution time but also low memory usage.

Diving dipper into arrays, Packed vs Holey

Table of contents