21

The difference between a JavaScript Array, and Object is not very big. In fact it seems Array mainly adds the length field, so you can use both Arrays and Objects as numeric arrays:

var ar = new Array();
ar[0] = "foo";
ar["bar"] = "foo";

var ob = new Object();
ob[0] = "foo";
ob["bar"] = "foo";

assert(ar[0] == ob[0] == ar["0"] == ob["0"] == ar.bar == ob.bar); // Should be true.

So my questions is, in popular JavaScript engines (V8, JavaScriptCore, SpiderMonkey, etc.), how is this handled? Obviously we do not want our arrays to be actually stored as hash maps with key values! How can we be reasonably sure our data is stored as an actual array?

As far as I can see there are a few approaches engines could take:

  1. Array is implemented exactly the same way as Object - as an associative array with string keys.
  2. Array is a special case, with a std::vector-like array backing the numeric keys, and some density heuristic to prevent insane memory use if you do ar[100000000] = 0;
  3. Array is the same as Object, and all objects get a heuristic to see if using an array would make more sense.
  4. Something insanely complicated that I haven't thought of.

Really this would be simpler if there were a proper array type (cough WebGL typed arrays cough).

6
  • 2
    This article is a little old, and it doesn't explicitly explain implementation. However, it does detailed performance measurements, and infers the likely implementations. Feb 10, 2012 at 19:57
  • 2
    Array isn't just a map with a length property tacked on. If it were, then shifting or unshifting would break the indexing (i.e. shift a value off an array, and it still starts at index 0, not 1). So there's at least a little more going on. (Not that this necessarily says anything about the implementation, of course)
    – Flambino
    Feb 10, 2012 at 20:00
  • 1
    Why would you expect r[0] == ob[0] == ar["0"] == ob["0"] == ar.bar == ob.bar to be true? 'a' == 'a' == 'a' is false because it evaluates to true == 'a' which evaluates to false. Feb 10, 2012 at 20:15
  • 4
    @Flambino, that is not true. shift is implemented as a generic method, not array specific. It will work perfectly well with a regular object. Shifting works because it grabs the first value, then loops over all values assigning left and finally deletes the last element and sets length. Feb 10, 2012 at 20:17
  • 1
    @Flambino, try running var a = { 0: 0, 1: 1, length: 2 }; Array.prototype.shift.apply(a); alert(JSON.stringify(a)). You should reliably get {"0":1,"length":1}. Feb 10, 2012 at 20:19

2 Answers 2

15

In SpiderMonkey, arrays are implemented basically as C arrays of jsvals. These are referred to as "dense arrays". However, if you start doing un-array-like things to them -- like treating them like objects -- their implementation is changed to something which very much resembles objects.

Moral of the story: when you want an array, use an array. When you want an object, use an object.

Oh, a jsval is a sort of variadic type which can represent any possible JavaScript value in a 64 bit C type.

8

In V8 and Carakan (and presumably Chakra), all (non-host) objects (both those that are arrays and those that aren't) with properties whose names are array indexes (as defined in ES5) are stored as either a dense array (a C array containing some value wrapper) or a sparse array (which is implemented as a binary search tree).

The unified object representation shows through in that it affects enumeration order: with an object, SpiderMonkey and SquirrelFish both give all properties in insertion order; and with an array, they in general (there are special cases in SM at least!) array indexes first then all other properties in insertion order. V8, Carakan, and Chakra always give array indexes first then all other properties in insertion order, regardless of object type.

1
  • 2
    Thanks for the info, but what is the source?
    – Klesun
    Feb 2, 2021 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.