debuggable

 
Contact Us
 

Understanding hidden classes in v8

Posted on 1/9/10 by Felix Geisendörfer

Update: As pointed out by mraleph from the v8 team in the comments, some of the analysis here is probably flawed. See his post for more details: Understanding hidden classes in v8 - real picture

With JSConf.eu coming closer, I slowly have to start preparing my talk, which mostly means hacking on node-dirty.

I have a few goals for the project. My main interest is challenging a few assumptions people have about the performance and complexity of database systems. Most of that is material for another post and my talk itself, but today I'd like to talk about hidden classes in v8.

One of the things that is really fast in v8 is property lookups. This is due to an optimization that creates hidden classes for an object.

I could go into a lengthy explanation of how that works, but instead I'll invite you to see for yourself.

Consider the following two examples and guess which runs faster, and by how much:

Example 1:

var PROPERTIES = 10000000;
var o = {};

var start = +new Date;

for (var i = 0; i < PROPERTIES; i++) {
  o[i] = i;
}

console.log(+new Date - start);

Example 2:

var PROPERTIES = 10000000;

function O(size) {
  for (var i = 0; i < size; i++) {
    this[i] = null;
  }
}

var o = new O(PROPERTIES);

var start = +new Date;

for (var i = 0; i < PROPERTIES; i++) {
  o[i] = i;
}

console.log(+new Date - start);

If you have guessed example 2, congratulations! Bonus points if you have also guessed that example 2 is a nifty 10x faster than example 1.

For those familiar with v8, you probably already know what is going. For those who don't, let me explain.

In example 1, every time you are setting a property on the o object, v8 is creating a new hidden class that defines the "data structure" of the o object to optimize property lookup performance.

In example 2, we are initializing these "hidden classes" the first time we create our o object. So when we are overwriting these properties later on, it is blazing fast, because v8 already knows how to efficiently lookup those properties.

So if you're writing node.js code, the lesson learned here is that it is much faster to work with existing properties in v8, than to add new ones.

In my next version of dirty I am planning to take advantage of this behavior by pre-allocating properties before they are actually used. This will probably require a little trickery to map user-defined keys to pre-allocated properties, but it should result in an overall 10x performance boost for setting new keys.

Let me know what you think / if you have other clever v8 hacks to speed stuff up : ).

--fg

PS: You can read more about hidden classes in the v8 docs.

 
&nsbp;

You can skip to the end and add a comment.

Aaron said on Sep 01, 2010:

Interesting find!

JTBrinkmann  said on Sep 01, 2010:

This is quite interresting, but it should be noticed, that the benchmark doesn't record the time

initializing these "hidden classes"

because

var start = +new Date;

is run afterwards.
I understand that this still could be a speedup in special cases, but in other ones (i.e. code has to be run right after entering/loading the page) it should run slower, doesn't it?

I didn't test it



Felix Geisendörfer said on Sep 01, 2010:

JTBrinkmann: Of course, but that's a tradeoff. Also, creating new objects with the same hidden classes becomes faster after the first one.

JTBrinkmann  said on Sep 02, 2010:

Ok, thx for your answer, I think this could really improve the speed of teh web :P

Vyacheslav Egorov said on Sep 02, 2010:

You are misunderstanding what is going on here.

Speedup you observe is mostly caused by preallocation itself and has almost nothing to do with lookup implementation/hidden classes transitions.

Adding a properties might require growth of underlying storage, which triggers it's reallocation and eventually causes GC. Modifying existing property does not require that [in most cases].

Felix Geisendörfer said on Sep 02, 2010:

Vyacheslav Egorov: I could be wrong, but I don't think so. V8 pre-allocates memory already, so the pre-allocation isn't the cause of the speed up. You can try executing the same example in Firefox and you'll notice that the speed gain in example #2 is only marginal compared to the order-of-magnitude observed in v8. But again, if you can show a counter-example let me know.

Vyacheslav Egorov said on Sep 02, 2010:

Felix Geisendörfer: What do you mean by "V8 pre-allocates memory already"? It does not.

But again, if you can show a counter-example let me know.

Ok. Here I go... Or not.

I've written a huge comment but I was unable to post it because it contained "illegal tags". I separated all code and listings and putted them on my server --- and was unable to post it again because "This comment appears to be spam."... Ok. I am doing my last attempt. I am putting an entry with detailed analysis into my blog: http://mr-aleph.livejournal.com/288023.html

This post is too old. We do not allow comments here anymore in order to fight spam. If you have real feedback or questions for the post, please contact us.