When is an array, not an array?

TL;DR: Don’t do weird stuff to JavaScript arrays.

*ahem*

What are arrays?

In the standard definition of Array data structures in Computer Science, arrays are a collection of like elements where any member may be accessed by an index. That definition doesn’t sound very different from an Hash Table or it’s ilk, but the key distinctions here are that the elements of the array must take up the same size in memory, and that the array indexes need to be numeric so that the logical address of any individual element can be derived from that number.

Arrays are typically created from contiguous memory. This makes for a simple calculation, like if we know that an Array lives at memory address 1024 and that each element in the array holds a 32-bit reference to an object then we can look up any individual item with a simple computation:

element_address = (1024 + (32 * index))

You want the element at index 14? Here ya go, it’s the 32bits starting at address 1472!

What makes arrays important?

It’s important that indexes be numeric because it means we can compute the memory address of any element in the array in constant time. This makes for the fastest random access of any data structure – even in the worst case scenario. Hash Tables are great and all, but there is overhead associated with their hashing and collision handling.

Check out the Big-O Algorithm Complexity Cheat Sheet for a nice visual comparison.

So, back to our original question…

When is an array, not an array?

JavaScript is notoriously loosey goosey, and it’s array types are no exception.

Sure, we can do all the normal array type operations. But we can also do weird stuff.

Here’s a simple array definition, but how much memory do you think is ultimately allocated by this operation?

var myArray = [0,1,2];

Similar code in a language like C would have allocated an array with 3 x sizeof(int). Trying to set a value outside of that memory block (say at [100000]) would go badly in most languages, but JavaScript doesn’t mind at all. In fact, JavaScript is extremely lenient in what it will take. Let’s continue the example…

myArray[100000] = 100000; // JS is cool with this
myArray[-1] = -1.33333; // and this
myArray['mmm...need more coffee'] = 'go get it, lazy bones!'; // this too

The above examples show several crimes against nature. Exceeding the bounds of original declaration, negative indexes, non-numeric indexes, setting different value types…heinous crimes indeed. These operations are incompatible with the definition above.

Given the information above about the key defining features of array data structures…how can JavaScript Arrays possibly be arrays? The answer, my friend, is ~blowing in the wind~ that there is a difference between array data structures and array types.

JavaScript arrays are always array types, but they aren’t always array data structures.

JavaScript doesn’t have an implementation, it has many. V8, TraceMonkey, and Chakra are all examples of popular JavaScript engines. This makes it hard to really say what “JavaScript does” when it comes to technical implementations. Even if we managed to find the relevant spot(s) in code for a particular engine, it could all change tomorrow. That said, things are pretty stable so a radical re-working of array implementations in V8 (for example) are unlikely. Code diving is difficult given the size of the engines, but lucky for us some really smart people have opted to guide us through the most remarkable bits.

In V8 (and most other implementations) The underlying data structures used to represent your JavaScript array in memory can change based on your usage. If you start out with an array of integers, then V8 will represent that with a dynamic array of integers. If you exceed the bounds of your array, then V8 will either allocate you a new array that is big enough to fit your new indexes or in some cases might even dynamically convert your array to a new data structure that is more efficient for dealing with sparse values. If you add a value to your array that does not match with the data type that V8 started you with then it will allocate you a new array with a more general type. In the code above we started with integers, but the type was changed once we added a decimal, and would have changed again when we added the string except that the index I used was also a string so once again, V8 would have dynamically converted the underlying data structure to accommodate.

The underlying data structures used to represent your JavaScript array in memory can change based on your usage.

How does JavaScript get away with calling their arrays…arrays? Formal definitions don’t always line up cleanly with the “real” world and there is a distinction between Array Data Structures and Array Types. Array types are sometimes implemented with other data structures, like in the cases listed above, and that is okay. JavaScript is not the only language that is loosey goosey, at least it’s indexes start with zero!

So, what have we learned?

Don’t do weird stuff to JavaScript arrays. JS is lenient and complicated, and there are performance implications in addition to the normal readability nightmares caused by the examples shown above. Read this article, and watch the video if you want to learn more.

Thanks for reading, let me know what you think in the comments!

---

Like this post? It was a result of research for this podcast episode on arrays and other similar data structures, so subscribe to Coding Blocks if you are interested in topics like this.

Photo by Andreas Gücklhorn on Unsplash

Comments

[JavaScript Joel]

This Array is not an Array!

const objArray = { 0: 'first', 1: 'second', 2: 'third', length: 3 }
objArray.__proto__ = Object.create(Array.prototype)

objArray.map(x => x.toUpperCase()) //=> ​​​​​[ 'FIRST', 'SECOND', 'THIRD' ]​​​​​
objArray.push('fourth')

objArray //=> Array { [Iterator]  0: 'first', 1: 'second', 2: 'third', 3: 'fourth', length: 4 }​​​​​

Object.prototype.toString(objArray) //=> "[object Object]"

[Joe Zack]

Haha, that is disgusting! I love it!

[Antony Garand]

This weird behavior is caused by arrays, which are actually JavaScript objects!

console.log(typeof [1,2,3]);  
// object  

As they are objects, they can still have properties and other content injected via the bracket notation.

We can confirm this by checking the keys vs the array length:

const x = [1,2,3];  
console.log(x.length);  
// 3  
x[-1] = -1;  
console.log(Object.keys(x));  
// Array(4) [ "0", "1", "2", "-1" ]  
console.log(x.length);  
// 3  

When adding a value at a super high index, it behaves somewhat like a normal array:

const x = [1,2,3];  
x[100000] = `high`;
console.log(x.length);
// 100001
console.log(x);
// Array(100001) [ 0...9999] [10000...19999] ...

Love your podcast btw!

[Joe Zack]

Hey thanks!

Also, did you know that you can set the length property?

Check this out:

var x = [1,2,3,4,5];
x.length = 2;
// end up with [1,2]

[Antony Garand]

Yea, that's a nice way to trim the end of an array!

Interesting but weird behavior, it suits JS

[Russ Hammett]

Ayyy solar panel array! My dude!

[Joe Zack]

Solar FTW!

[Sung M. Kim]

I didn't get the featured image until you mentioned it 😆

[Javid Asgarov]

Just a few days back I was reading about data structures, arrays and linked lists and wondered that I should take a look how arrays in javascript work, data-structure-wise. I mean, with arrays as a data structure, it seems you need to know array size beforehand, and then if it needs to grow you must reallocate memory and all that hideous stuff.

So, yeah, there a lot going on. Well, at least as I understood from this article, it's the array data structure under the hood, it just shifts it's in memory for you. But that data structure can also change to something else.

[Joe Zack]

Yep! Looks like the "normal" use case is generally implemented as a dynamic array underneath. So the engine will pick an array size to start, and if you exceed it then it will create a new bigger array. This is supposed to work really well in practice, since it's not common to individually add so many items to an array. I would love to know the default starting size!

en.wikipedia.org/wiki/Dynamic_array

[Sung M. Kim]

Thanks Joe for the post.

Is an "array data structure" a superset of "array type"?
or are they not related at all?

[Joe Zack]

Types refer to the language implimentations, basically it's whatever looks like an array and
a specific language says is an array.

The data structure definition is more formal: contiguos memory allocation of the same sized element so you can achieve random access (as in, lookup any) in constant time.

In some languages, array types are implimented with array data structures (like C#) but JavaScript is a bit more complicated because it has to support a flexible language specification.

[Sung M. Kim]

Borrowing C# analogy,

Types refer to an interface while data structure is a type of implementation implementing the interface.

Am I getting close to the truthiness? 😆

[Joe Zack]

I like it!