Javascript arrays are gapped!

Okay, technically this is talking about “sparse arrays” if you want to look deeper into the topic, but javascript doesn't set unused values to 0. This may be well known in some circles but it was a pleasant surprise when I was looking in the console one day.

By gapped, I mean that if you have an item at index 10 and an item at index 20, rather than assigning 19 undefined values between them JavaScript knows that item 11-19 are a range of empty values. It is aware of the gap.

If you are using an array as a lookup or to store values based on numeric index in a related array, then you can end up with a situation where the length of your array is not what you think it is. How you loop through the array can have speed consequences. If your loop is acting on what it thinks is a long array understanding which array options are gap-aware can help with performance. In a moment I will demonstrate storing two values in an array that shows its length to be 2001.

Follow Along

If you want to do some experimenting and follow along, I recommend bringing up the developer console in your browser for this page or for a tab you are comfortable working in. You can then paste the examples into the console input.

Gapped arrays in action

window.test = [];
window.test[1000] = 'one thousand';
window.test[2000] = 'two thousand';

Then enter:

window.test

What is displayed (I'm using Edge) is:

(2001) [empty × 1000, "one thousand", empty × 999, "two thousand"]

The parenthesis shows that you have an array of 2001 entries. However, what is particularly interesting is the empty x 1000 and empty x 999.
If you are confused why “one thousand” is after 1000 empty values, remember that 0 is a valid array index which is also empty. Otherwise check out off by one error.

Looping

forEach:

window.test.forEach((item,index)=>{console.log(`test[${index}]=${item}`);});

What you are likely expecting is for the array to be looped on and get a log message for all 2001 items right? Well, this is what you get:

test[1000]=one thousand
test[2000]=two thousand

However, if you don't mind generating a couple thousand log entries:

for(const item of window.test){ console.log(item); }

For my browser I have the console set to group repeated log entries:

(1000) undefined
one thousand
(999) undefined
two thousand

So, it wrote out 1000 undefined messages + 999 undefined messages.

For the same result as forEach

Console version:

for(let key in window.test) { if(test.hasOwnProperty(key)){console.log(`test[${key}]=${window.test[key]}`);}}

More readable version:

for(let key in window.test) {
   if(window.test.hasOwnProperty(key)){
      console.log(`test[${key}] = ${window.test[key]}`);
   }
}

I have seen it suggested that for-in is a less performant looping method. And yet, in this instance is more performant in the sense it is gap-aware.

Whether you know how to evaluate code efficiency or not, it is pretty safe to say that processing 2 entries instead of 2001 is a performance enhancement.

The classic for loop

for(var i=0; i < test.length; i++) loop will loop through all 2001 indices because the length is 2001 not 2 and you are explicitly asking for whatever is at each index. All the empty entries will be returned as undefined because empty isn’t actually a javascript data type.

Other looping functions

It should be noted that Array’s map and every functions skip the gaps. The reduce function also appears to respect the gaps.
The shift and push methods work traditionally, so shifting on an a gapped array will get the 0th entry rather than the first non-gap entry. It also moves all your entries down.

A gapped shift-ish function would be something like:

function shiftGappedArray(arry) {
   for( const index in arry) {
      const firstItem = arry[index];
      delete arry[index];
      return firstItem;   
  }
}

Or for TypeScripters:

function shiftGappedArray(arry:Array<any>):any {
   for( const index in arry) {
      const firstItem = arry[index];
      delete arry[index];
      return firstItem;   
  }
}

This function would return and remove the first found option but would not adjust the size of the array.

Technically that is not "shifting". It is more a get and remove first set entry function. That is commonly done with arrays and typically done with shift. But when the indices are more like db indexes you don’t want indices changing on you.

Delete is not the same as setting something to undefined

For removal, delete an index rather than using undefined or null.
Here’s a proof that deleting at an index in the middle of an array won’t affect the indices.

window.test = []
window.test[5] = 'five'
window.test[10]='ten'
delete window.test[5]

The value of window.test:

(11) [empty × 10, 'ten']

If you are maintaining this kind of gapped array. You should know that to take advantage of the empty ranges, the way to remove an item from the list is to delete the item at that index rather than setting it null or undefined. This may be counter-intuitive if you have read that deleting a variable is functionally equivalent to setting it to undefined.

Null is treated as a value:

window.test = []
window.test[1000] = null;

The value of window.test:

empty x 1000,null

Undefined is also a value:

window.test = []
window.test[2000] = "two thousand";
window.test[1000] = undefined;

The value of window.test:

empty x 1000,undefined,empty x 999,"two thousand"

I have also seen incorrect advice given for adding entries to the end of an array by using push(undefined). However, that behaves the same as setting an entry to undefined and does not work with the gapping. To push empty values at the end of the array:

test.length++

or less elegantly:

test.concat([,]);

Either of these will add “empty” entries at the end of the array. I'm not sure why an array with two empty values works but it does.

Browser Support:

I have confirmed all of this is true on the latest versions of Chrome/Edge and Firefox but have not looked into Safari or browsers not on Windows.

Beyond JavaScript

I have not researched whether this is a thing in other languages these days. If this is a topic of interest and something you can comment on for other languages feel free to let readers know in the comments

Takeaways

• Arrays in JavaScript are gapped and not all array functions take advantage of that
• If you have sparse arrays you are looping on you may want to consider whether you might get more performance from a gap-aware alternative function.
The main thing to realize here is that because arrays are gapped or sparse in JavaScript there are mechanisms for getting just the non-empty values. And if you are paying attention you can leverage that knowledge to gain performance for any array that your looping is treating like a full array when it is actually sparse.
• Undefined and null break the gapping; delete is not the same as setting something to undefined.
• Delete array entries to take advantage of gapping.
• Avoid shift, push, splice or other index-modifying functions on a lookup array.
• Although it is the place the errors show up, the console is your friend and sometimes can help you understand what you are getting better than documentation.