Water Cooler v2 Water Cooler v2 - 3 months ago 8
Javascript Question

What exactly is a dense array?

The explanation for a dense array that I read from a few pages seem to be in contradiction to one another. I'd like some help understanding what it is.

While some links (search result 1, search result 2) suggest that it simply is an array where:


  1. the elements of the array are known to be specific values; and

  2. are assigned to the array at the time of its initialization.



The allusion there is that JavaScript arrays are dense.

It all makes sense up until here.

But this statement taken from the JavaScript Guide on the Mozilla Developer Network (MDN) says:


Since an array's length can change at any time, and data can be stored at non-contiguous locations in the array, JavaScript arrays are
not guaranteed to be dense; this depends on how the programmer chooses
to use them. In general, these are convenient characteristics; but if
these features are not desirable for your particular use, you might
consider using typed arrays.



And this has confused me now. My question is:

What does the statement on the MDN page mean when it says JavaScript arrays are not guaranteed to be dense? If it means that the following is not a dense array because one or more of its elements are
undefined
at the time of initialization, then why do the links I listed above seem to indicate that JavaScript arrays are indeed dense?

var array = new Array(1, , 3, ); // [1, undefined, 3, undefined]

Answer

"Dense" is in opposition to "sparse", and generally is used when talking about storage. For example, this array is dense:

a = [undefined, undefined, 2]

It can be stored in memory exactly like that: a sequence of three locations, the first two being undefined, the third being 2.

This array is sparse:

a = []
a[100000000] = 100000000

It is not stored in memory as a sequence of 100000001 locations, as it would be horribly inefficient. It is definitely not 100000000 places of undefined followed by 100000000. Rather, it just says 100000000th one is 100000000, and there is no space allocated to the first 100000000 elements.

(Actually, try to do this with 2 instead of 100000000, and you'll notice a curious thing: Chrome will display the dense array as [undefined, undefined, 2], but the sparse one as [undefined × 2, 2].)