Under The Hood: Arrays in JS

Posted by

Here are two truths about JavaScript:

  • JavaScript does’t have integers, so you have to use numbers instead.
  • JavaScript arrays are not typed, you can put whatever you want in them.

Sounds reasonable? Well while these are true, and JavaScript’s semantics will honour these, the truth gets a bit more fuzzy as you delve into the details of what happens behind the scenes in the JavaScript engine.

The Google V8 engine is used in the Chrome browser and Node programming environment. This engine will make optimisations based on the runtime behaviour of your program. This means the values in your numbers and arrays actually count for something when it comes to peformace.

V8 knows roughly what kinds of items are in your arrays, and it uses this information to make performance optimisations. It marks arrays stored in memory as a certain ‘type’, because if, for example it knows the array only contains integers (whole numbers), it can work with them more efficiently.

There are 6 types of array that V8 knows about, which are represented in this diagram taken from v8.dev:

V8 Engine Lattice

To make sense of this diagram, you can think of it as 3 types of elements:

  • SMI_ELEMENTS – The array contains only integers, e.g. [1, 2, 3]
  • DOUBLE_ELEMENTS – The array only contains double precision floating point numbers, e.g. [1, 2.1]
  • ELEMENTS – The array could contain anything, e.g. [1, 3, 'x']

And these type of elements are accompanied by the words Holey and Packed. Those mean:

  • HOLEY – The array may have holes. I will explain how this can happen shortly.
  • PACKED – Every element of the array has a value (or undefined), e.g. ['x','y',undefined,'z']

The transition arrows shown in the diagram are one way transitions that can happen to the type of an arrays as elements are removed, inserted or updated.

You can go from integer to double (but not back). You can go from double to anything (but not back). You can go from packed to holey (but not back).

Keep in mind that the type of array is just about V8’s knowledge of what the array might contain, which it uses for performance optimisation. It doesn’t affect the actual behaviour of your program. For example if you add a string value 'X' to a PACKED_SMI_ELEMENTS array, that is OK to do, but it means the V8 Engine will now treate it as though it can contain anything, even if you remove the 'X' later on.

Holey Arrays

A holey array is one where there are values that are not defined. This doesn’t mean that the value is the JavaScript value of undefined, but rather they haven’t been set yet. For this to happen you need to leave a gap when inserting elements, e.g.:

var holey = [1, 2, 3];
holey[9] = 9;
// holey has holes at positions 3, 4, 5, 6, 7 and 8.

Performance

For best performance, you want the type of array to be as far top and left in the diagram as possible. This means you wan’t to avoid holey arrays, and keep your arrays as SMI if possible, otherwise double if possible.

Avoiding holey arrays should be easy enough in most cases, and follows from idiomatic (i.e. common case) JS programming, such as using the map or push functions, which don’t leave holes. Be careful when inserting data by index into an array.

Keeping to SMI or Double arrays is only really applicable if you really are dealing with those types in the first place.

The trick is not to add other types to those arrays like strings or objects. If you are used to mixing types in array for whatever reason then it might be worth thinking about changing that habit if it impacts peformace.

And remember if your application is performaing reasonably it might be best to ignore these optimisations so that you have one less thing to worry about. Use them when you really need to make something go faster because it is impacting the users of your application.

Credits

I learned this stuff attending a talk by Mathias Bynens live in Melbourne JSConf in 2018. Luckily for you (and me!) the talk is available on https://v8.dev/blog/elements-kinds along with an article going into more depth than I have here. Fascinating stuff.

Summary

This article is a quick overview of arrays and performance in the V8 engine. There is more depth to this on the v8.dev website. If you want to know more about arrays, see JavaScript arrays or my website about JavaScript.

Martin Capodici