What is the performance of Objects/Arrays in JavaScript? (specifically for Google V8)

Question

Performance associated with Arrays and Objects in JavaScript (especially Google V8) would be very interesting to document. I find no comprehensive article on this topic anywhere on the Internet.

I understand that some Objects use classes as their underlying data structure. If there are a lot of properties, it is sometimes treated as a hash table?

I also understand that Arrays are sometimes treated like C++ Arrays (i.e. fast random indexing, slow deletion and resizing). And, other times, they are treated more like Objects (fast indexing, fast insertion/removal, more memory). And, maybe sometimes they are stored as linked lists (i.e. slow random indexing, fast removal/insertion at the beginning/end)

What is the precise performance of Array/Object retrievals and manipulations in JavaScript? (specifically for Google V8)

More specifically, what it the performance impact of:

• Adding a property to an Object
• Removing a property from an Object
• Indexing a property in an Object
• Adding an item to an Array
• Removing an item from an Array
• Indexing an item in an Array
• Calling Array.pop()
• Calling Array.push()
• Calling Array.shift()
• Calling Array.unshift()
• Calling Array.slice()

Any articles or links for more details would be appreciated, as well. :)

EDIT: I am really wondering how JavaScript arrays and objects work under the hood. Also, in what context does the V8 engine "know" to "switch-over" to another data structure?

For example, suppose I create an array with...

var arr = [];
arr[10000000] = 20;
arr.push(21);

What's really going on here?

Or... what about this...???

var arr = [];
//Add lots of items
for(var i = 0; i < 1000000; i++)
    arr[i] = Math.random();
//Now I use it like a queue...
for(var i = 0; i < arr.length; i++)
{
    var item = arr[i].shift();
    //Do something with item...
}

For conventional arrays, the performance would be terrible; whereas, if a LinkedList was used... not so bad.

Blueberry

Visit jsperf.com, and create test cases. – Antisyphilitic

@RobW There's more at play here than simple tests can account for which requires knowledge of how the JIT compilers work, and what is being done with the data. If I find some time I'll add an answer, but hopefully someone else will have time to get into the nitty gritty. Also I'd like to just leave this link here – Biyearly

JIT things I'm talking about are things like "shape" of an object, or arrays with undefined values between defined elements, as well as the more recently experimented with type-specializing features... array-specific methods may depend on use as well as if the prototype has been manipulated or not. There is no such thing as "knowing to" switch to another data type AFAIK. – Biyearly

There are Google representatives discussing, how the various optimizer and internal system works. And how to optimize for them. (for games!) youtube.com/watch?v=XAqIpGU8ZZk – Strobila

Answer 1

I created a test suite, precisely to explore these issues (and more) (archived copy).

And in that sense, you can see the performance issues in this 50+ test case tester (it will take a long time).

Also as its name suggest, it explores the usage of using the native linked list nature of the DOM structure.

(Currently down, rebuilt in progress) More details on my blog regarding this.

The summary is as followed

• V8 Array is Fast, VERY FAST
• Array push / pop / shift is ~approx 20x+ faster than any object equivalent.
• Surprisingly Array.shift() is fast ~approx 6x slower than an array pop, but is ~approx 100x faster than an object attribute deletion.
• Amusingly, Array.push( data ); is faster than Array[nextIndex] = data by almost 20 (dynamic array) to 10 (fixed array) times over.
• Array.unshift(data) is slower as expected, and is ~approx 5x slower than a new property adding.
• Nulling the value array[index] = null is faster than deleting it delete array[index] (undefined) in an array by ~approx 4x++ faster.
• Surprisingly Nulling a value in an object is obj[attr] = null ~approx 2x slower than just deleting the attribute delete obj[attr]
• Unsurprisingly, mid array Array.splice(index,0,data) is slow, very slow.
• Surprisingly, Array.splice(index,1,data) has been optimized (no length change) and is 100x faster than just splice Array.splice(index,0,data)
• unsurprisingly, the divLinkedList is inferior to an array on all sectors, except dll.splice(index,1) removal (Where it broke the test system).
• BIGGEST SURPRISE of it all [as jjrv pointed out], V8 array writes are slightly faster than V8 reads =O

Note: These metrics applies only to large array/objects which v8 does not "entirely optimise out". There can be very isolated optimised performance cases for array/object size less then an arbitrary size (24?). More details can be seen extensively across several google IO videos.

Note 2: These wonderful performance results are not shared across browsers, especially *cough* IE. Also the test is huge, hence I yet to fully analyze and evaluate the results : please edit it in =)

Updated Note (dec 2012): Google representatives have videos on youtubes describing the inner workings of chrome itself (like when it switches from a linkedlist array to a fixed array, etc), and how to optimize them. See GDC 2012: From Console to Chrome for more.

Strobila

Some of those results look very strange. For example in Chrome array writes are roughly 10x faster than reads, while in Firefox it's the opposite. Are you sure the browser JIT isn't optimizing away your entire test in some cases? – Parthenon

@Parthenon good gosh =O you are right... I even updated the each write case to be incrementally unique, to prevent JIT... And honestly, unless the JIT optimization is that good (which I find it hard to believe), it could just be a case of poorly optimized read, or heavily optimized writes (write to immediate buffer?)... which is worth investigating : lol – Strobila

@pico.creator Try the Closure Compiler with your tests, Chrome's JIT might do similar things. This: var a=[];for(i=0;i<100;i++) a[i]=Math.random(); gets optimized away entirely. If it notices you don't use the array contents afterwards, it won't write to it either. – Parthenon

@Parthenon Hmm cdnt use closure compiler with my test as I do not have jspref source code... however i used it before, and i know how to beat it... I added an intentional memory leak at the end of the test that has a 1% chance of leaking [via Math.random()], this flags the variable as "read", and hence not optimized out. And you were right =O The write speeds went down, however it surprisingly still faster by a very small margin... >.< seriously, just how optimized is the v8 engine inside chrome? [google is scary]... – Strobila

just wanted to add the exact point in the video discussion on arrays: youtube.com/… – Peipus

@Peipus : thanks for the link, I have updated the answer to reflect this =) – Strobila

Are you sure as a delete object's property approach, nulling a value is slower than just delete it? I read a test about set value to null or undefined is faster than delete it – Fatima

@Fatima It could be test case specific. In my test deleting an array is faster, however deleting from an object is slower. Additionally the test case i provided uses a very large object as a testing point (1000 vars). As oppose to a very small data object in the test you provided (1 var). From what i do (somewhat) rmber from Google IO talks. They have very specific optimization features for small object types (<100 vars). In some cases optimizing the object out entirely. That would explain the more efficent Nulling in the test case you provided – Strobila

The JsPerf site doesn't exist anymore :( – Interdisciplinary

@JustGoscha.... nooo... and i dun have backups... google cache save me please (rushes to check now) – Strobila

@JustGoscha ok, thx for the info: I fixed it back up by recreating it from google cache. – Strobila

jsPerf is temporarily unavailable. Please try again later. – Audryaudrye

@Audryaudrye : Just gotta wait it out sadly (see github.com/jsperf/jsperf.com/issues/18#issuecomment-113569132) as an emergency measure i have archived the test case. So once a successor to JSPref is up. I can update the answer. – Strobila

Array shift/unshift from the front might require all the data to be shift back one, resulting in slower performance when compared to push/pop. It would be interesting to see how an object-wrapped linked link shift/unshift compare. – Bette

"Amusingly, Array.push( data ) is faster than Array[nextIndex] = data by almost 20 times over." Be careful: This only applies if your array size cannot be predetermined. Resizing arrays costs a lot of runtime! See this fiddle. – Verein

@Verein : This is still somewhat consistent. You have to compare .push against [nextIndex] of fixed array, against fixed array. And vice visa for dynamic. See: jsfiddle.net/g1md8xhs/2. However it seems the 20x is now 10x for fixed arrays. Updated the answer as such. – Strobila

Just took a glance at the V8 source code (was interested in run-time of push/pop). This comment suggests that an array is essentially a hash table if it is not initialized with a fixed size, otherwise, it's essentially a vector. As such, we'd expect average O(1) time for push/pop using the hash table implementation, and amortized O(1) time using the vector implementation. github.com/v8/v8/blob/8ba517e194d6e71ba46278ea1d7e801c784cb2ef/… – Leopoldine

Answer 2

At a basic level that stays within the realms of JavaScript, properties on objects are much more complex entities. You can create properties with setters/getters, with differing enumerability, writability, and configurability. An item in an array isn't able to be customized in this way: it either exists or it doesn't. At the underlying engine level this allows for a lot more optimization in terms of organizing the memory that represents the structure.

In terms of identifying an array from an object (dictionary), JS engines have always made explicit lines between the two. That's why there's a multitude of articles on methods of trying to make a semi-fake Array-like object that behaves like one but allows other functionality. The reason this separation even exists is because the JS engines themselves store the two differently.

Properties can be stored on an array object but this simply demonstrates how JavaScript insists on making everything an object. The indexed values in an array are stored differently from any properties you decide to set on the array object that represents the underlying array data.

Whenever you're using a legit array object and using one of the standard methods of manipulating that array you're going to be hitting the underlying array data. In V8 specifically, these are essentially the same as a C++ array so those rules will apply. If for some reason you're working with an array that the engine isn't able to determine with confidence is an array, then you're on much shakier ground. With recent versions of V8 there's more room to work though. For example, it's possible to create a class that has Array.prototype as its prototype and still gain efficient access to the various native array manipulation methods. But this is a recent change.

Specific links to recent changes to array manipulation may come in handy here:

• http://code.google.com/p/v8/source/detail?r=10024
• http://code.google.com/p/v8/source/detail?r=9849
• http://code.google.com/p/v8/source/detail?r=9747

As a bit of extra, here's Array Pop and Array Push directly from V8's source, both implemented in JS itself:

function ArrayPop() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.pop"]);
  }

  var n = TO_UINT32(this.length);
  if (n == 0) {
    this.length = n;
    return;
  }
  n--;
  var value = this[n];
  this.length = n;
  delete this[n];
  return value;
}


function ArrayPush() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.push"]);
  }

  var n = TO_UINT32(this.length);
  var m = %_ArgumentsLength();
  for (var i = 0; i < m; i++) {
    this[i+n] = %_Arguments(i);
  }
  this.length = n + m;
  return this.length;
}

Braise

Answer 3

I'd like to complement existing answers with an investigation to the question of how implementations behave regarding growing arrays: If they implement them the "usual" way, one would see many quick pushes with rare, interspersed slow pushes at which point the implementation copies the internal representation of the array from one buffer to a larger one.

You can see this effect very nicely, this is from Chrome:

16: 4ms
40: 8ms 2.5
76: 20ms 1.9
130: 31ms 1.7105263157894737
211: 14ms 1.623076923076923
332: 55ms 1.5734597156398105
514: 44ms 1.5481927710843373
787: 61ms 1.5311284046692606
1196: 138ms 1.5196950444726811
1810: 139ms 1.5133779264214047
2731: 299ms 1.5088397790055248
4112: 341ms 1.5056755767118273
6184: 681ms 1.5038910505836576
9292: 1324ms 1.5025873221216042

Even though each push is profiled, the output contains only those that take time above a certain threshold. For each test I customized the threshold to exclude all the pushes that appear to be representing the fast pushes.

So the first number represents which element has been inserted (the first line is for the 17th element), the second is how long it took (for many arrays the benchmark is done for in parallel), and the last value is the division of the first number by that of the one in the former line.

All lines that have less than 2ms execution time are excluded for Chrome.

You can see that Chrome increases array size in powers of 1.5, plus some offset to account for small arrays.

For Firefox, it's a power of two:

126: 284ms
254: 65ms 2.015873015873016
510: 28ms 2.0078740157480315
1022: 58ms 2.003921568627451
2046: 89ms 2.0019569471624266
4094: 191ms 2.0009775171065494
8190: 364ms 2.0004885197850513

I had to put the threshold up quite a bit in Firefox, that's why we start at #126.

With IE, we get a mix:

256: 11ms 256
512: 26ms 2
1024: 77ms 2
1708: 113ms 1.66796875
2848: 154ms 1.6674473067915691
4748: 423ms 1.6671348314606742
7916: 944ms 1.6672283066554338

It's a power of two at first and then it moves to powers of five thirds.

So all common implementations use the "normal" way for arrays (instead of going crazy with ropes, for example).

Here's the benchmark code and here's the fiddle it's in.

var arrayCount = 10000;

var dynamicArrays = [];

for(var j=0;j<arrayCount;j++)
    dynamicArrays[j] = [];

var lastLongI = 1;

for(var i=0;i<10000;i++)
{
    var before = Date.now();
    for(var j=0;j<arrayCount;j++)
        dynamicArrays[j][i] = i;
    var span = Date.now() - before;
    if (span > 10)
    {
      console.log(i + ": " + span + "ms" + " " + (i / lastLongI));
      lastLongI = i;
    }
}

Guth

Answer 4

While running under node.js 0.10 (built on v8) I was seeing CPU usage that seemed excessive for the workload. I traced one performance problem to a function that was checking for the existence of a string in an array. So I ran some tests.

• loaded 90,822 hosts
• loading config took 0.087 seconds (array)
• loading config took 0.152 seconds (object)

Loading 91k entries into an array (with validate & push) is faster than setting obj[key]=value.

In the next test, I looked up every hostname in the list one time (91k iterations, to average the lookup time):

• searching config took 87.56 seconds (array)
• searching config took 0.21 seconds (object)

The application here is Haraka (a SMTP server) and it loads the host_list once at startup (and after changes) and subsequently performs this lookup millions of times during operation. Switching to an object was a huge performance win.

Barony