Creating and filling Arrays of arbitrary lengths in JavaScript

[2018-12-23] dev, javascript
(Ad, please don’t block)

Update 2019-01-02: Rewrote the section on performance. Switched from Array.from(new Array(LEN)) to Array.from({length: LEN}) (because the former argument can get large). New sections: “Recommended patterns”, “Acknowledgements”.

The best way of creating an Array, is via a literal:

const arr = [0,0,0];

Alas, that isn’t always an option, e.g. when creating large Arrays. This blog post examines what to do in those cases.

Arrays without holes tend to perform better  

In most programming languages, an array is a contiguous sequence of values. In JavaScript, an Array is a dictionary that maps indices to elements. It can have holes – indices between zero and the length, that are not mapped to elements (“missing indices”). For example, the following Array has a hole at index 1:

> Object.keys(['a',, 'c'])
[ '0', '2' ]

Arrays without holes are also called dense or packed. Dense Arrays tend to perform better, because they can be stored contiguously (internally). Once there is at least one hole, the internal representation has to change. Two options are:

  • A dictionary. Then lookup takes more time and storage overhead is greater.
  • A contiguous data structure, with sentinel values for holes. Then checking if a value is a hole or not, takes extra time.

In either case, if an engine encounters a hole, it can’t just return undefined, it must traverse the prototype chain and search for a property whose name is the index of the hole. That costs even more time.

In some engines, such as V8, the switch to a less performant data structure is permanent. They won’t switch back, even if all holes are plugged.

For more on how V8 represents Arrays, consult “Elements kinds in V8” by Mathias Bynens.

Creating Arrays  

Array constructor  

One common way of creating an Array with a given length, is to use the Array constructor:

const LEN = 3;
const arr = new Array(LEN);
assert.equal(arr.length, LEN);
// arr only has holes in it
assert.deepEqual(Object.keys(arr), []);

This approach is convenient, but it has two downsides:

  • The holes make this Array slightly slower, even if you completely fill it with values later on.
  • Holes are rarely good initial “values” for elements. E.g., zeros are much more common.

Array constructor plus .fill() method  

The .fill() method changes an existing Array and fills it with a specified value. That helps with initializing an Array after creating it via new Array():

const LEN = 3;
const arr = new Array(LEN).fill(0);
assert.deepEqual(arr, [0, 0, 0]);

Caveat: If you .fill() an Array with an object, all elements refer to the same instance (i.e., the object isn’t cloned):

const LEN = 3;
const obj = {};

const arr = new Array(LEN).fill(obj);
assert.deepEqual(arr, [{}, {}, {}]);

obj.prop = true;
assert.deepEqual(arr,
  [ {prop:true}, {prop:true}, {prop:true} ]);

We’ll later encounter a way of filling (via Array.from()) that doesn’t have this issue.

.push() method  

const LEN = 3;
const arr = [];
for (let i=0; i < LEN; i++) {
  arr.push(0);
}
assert.deepEqual(arr, [0, 0, 0]);

This time, we have created and filled an Array without putting holes in it. Therefore, using the Array after its creation should be faster than with the Array constructor. Alas, creating the Array is slower, because engines may have to reallocate the contiguous internal representation several times – as it grows.

Filling Arrays with undefined  

Array.from() converts iterables and Array-like values to Arrays. It treats holes as if they were undefined elements. We can use that to convert each hole to an undefined:

> Array.from({length: 3})
[ undefined, undefined, undefined ]

The parameter {length: 3} is an Array-like object with length 3 that contains only holes. It is also possible to instead use new Array(3), but that usually creates larger objects.

Spreading into Arrays only works for iterable values and has a similar effect to Array.from():

> [...new Array(3)]
[ undefined, undefined, undefined ]

Alas, Array.from() creates its result via new Array(), so you still end up with a sparse Array.

Mapping with Array.from()  

You can use Array.from() to map, if you provide a mapping function as its second parameter.

Filling an Array with values  

  • Creating an Array with small integers:
    > Array.from({length: 3}, () => 0)
[ 0, 0, 0 ]
  • Creating an Array with unique (unshared) objects:
    > Array.from({length: 3}, () => ({}))
[ {}, {}, {} ]

Creating ranges of integer values  

  • Creating an Array with ascending integers:
    > Array.from({length: 3}, (x, i) => i)
[ 0, 1, 2 ]
  • Creating an arbitrary range of integers:
    > const START=2, END=5;
> Array.from({length: END-START}, (x, i) => i+START)
[ 2, 3, 4 ]

Another way of creating an Array with ascending integers is via .keys(), which also treats holes as if they were undefined elements:

> [...new Array(3).keys()]
[ 0, 1, 2 ]

.keys() returns an iterable. We use spreading to convert it to an Array.

Cheat sheet: creating Arrays  

Filled with holes or undefined:

  • new Array(3)
    → [ , , ,]
  • Array.from({length: 2})
    → [undefined, undefined]
  • [...new Array(2)]
    → [undefined, undefined]

Filled with arbitrary values:

  • const a=[]; for (let i=0; i<3; i++) a.push(0);
    → [0, 0, 0]
  • new Array(3).fill(0)
    → [0, 0, 0]
  • Array.from({length: 3}, () => ({}))
    → [{}, {}, {}] (unique objects)

Ranges of integers:

  • Array.from({length: 3}, (x, i) => i)
    → [0, 1, 2]
  • const START=2, END=5; Array.from({length: END-START}, (x, i) => i+START)
    → [2, 3, 4]
  • [...new Array(3).keys()]
    → [0, 1, 2]

I prefer the following approaches. My focus is on readability, not on performance.

  • Do you need to create an empty Array that you’ll fill completely, later on?
    new Array(LEN)
  • Do you need to create an Array initialized with a primitive value?
    new Array(LEN).fill(0)
  • Do you need to create an Array initialized with objects?
    Array.from({length: LEN}, () => ({}))
  • Do you need to create a range of integers?
    Array.from({length: END-START}, (x, i) => i+START)

If you are dealing with Arrays of integers or floats, consider Typed Arrays – which were created for this purpose. They can’t have holes and are always initialized with zeros.

Tip: Array performance usually doesn’t matter that much  

  • For most situations, I wouldn’t worry too much about performance. Even Arrays with holes are quite fast. It makes more sense to worry about your code being easy to understand.

  • Additionally, how and where engines optimize, changes. So what is fastest today, may not be tomorrow.

Acknowledgements  

  • Thanks to Mathias Bynens and Benedikt Meurer for helping me get the V8 details right.

Further reading