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 let’s discuss.

Based on occupancy of indices, V8 engine internally classifies arrays in two categories.

Packed Array

A packed array is an array that has a value for every index. Packed arrays are the most optimized arrays. 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 is a costly task.

Accessing elements in an array is highly efficient and only costs O(1) for packed paths. As soon as an array becomes holey, access efficiency can degrade in practical scenarios.

How V8 Engine Stores Arrays

A packed array is an array that has some value for every index. JavaScript engines try 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 that has no value for some of the index or at least one 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: Discrete (map/dictionary-like structure)

Why JavaScript Engines Do This

One question might come to mind: why does the JS engine store arrays in different patterns?

The answer is memory optimization. Engines do not know whether you will access every element, but they do know you are reserving memory while assigning indices.

How V8 Accesses Array Elements

Now that we’ve learned how engines store arrays, let’s understand how they access elements.

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

Step 1: Bound Check

Engine first checks the starting position of array in memory (base address). Then it checks array length and compares it with requested index. If index is out of range, it returns undefined.

const packedElement = packedArray[3]
const holeyElement = holeyArray[3]
// Bound check passed here

Step 2: Property Check (After Bound Check)

For packed array, engine returns the value directly.

const packedElement = packedArray[3] // 4

For holey array, engine checks index and may find nothing.

const holeyElement = holeyArray[3]
// Engine may not find any direct value here

Then engine may check prototype chain and object property behavior because arrays in JavaScript are also objects.

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

Now Let’s Verify in Code

Enough theory. Let’s implement and check behavior with large arrays.

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 pattern: in most runs, packed array traversal is faster.

┌─────────┬───────────────────────┬────────────────────────┬────────────────┐
│ (index) │ Holey Array Time (ms) │ Packed Array Time (ms) │ Difference(ms) │
├─────────┼───────────────────────┼────────────────────────┼────────────────┤
│    0    │        '1.229'        │        '1.187'         │    '0.042'     │
│    1    │        '1.355'        │        '0.655'         │    '0.700'     │
│    2    │        '0.657'        │        '0.655'         │    '0.002'     │
│    3    │        '0.661'        │        '0.664'         │   '-0.003'     │
│   ...   │          ...          │          ...           │      ...       │
└─────────┴───────────────────────┴────────────────────────┴────────────────┘

Analysis of Output

In this code, we access elements of two really large arrays. We run this cycle 10 times. In your observed output, packed array performed better in 9 out of 10 runs.

Cause of Holey Array and How to Avoid It

What Causes Holey Arrays

A holey array can never be converted to packed array once again.
Initializing with new Array(length) causes holey array behavior.

How to Avoid Holey Arrays

Initiate with zero length: arr = [].
Assign undefined value to indices you are not sure about.
Prefer existing array methods instead of manual sparse assignment.

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 arrays are made to optimize space used by application/software. To avoid holey arrays, don’t forget why engine developers introduced these approaches to saving arrays.

The final optimized code should not only have fast execution time, but also low memory usage.

V8 Arrays Deep Dive: Packed vs Holey