Performance of method lookups via prototypes

[Cris Perdue]

Performance optimization advice from the V8 team emphasizes initializing properties to objects in constructors, and always in the same order (for example http://www.youtube.com/watch?v=UJPdhx5zTaw). The explanation is that this way each instance belongs to the same hidden class.

What if you have fairly computation-intensive code that uses subclassing and polymorphism? In this case method lookups need to go through the prototype object for the instances. Once execution gets to the type-specific method, life should be good again because that code always receives a "this" and arguments of the same type at each invocation. (The type-specific method code is typically fairly short and quick to execute in my software.)

My question is, to what degree should we expect a similar principle to apply, that prototypes for subclasses should have the same members and the members should be added to each subclass in the same order? Will this make the compiler recognize the prototypes as belonging to the same hidden class and make a big contribution to fast method lookup? Will method lookup code tend to be inlined? Is it OK that the prototypes are all directly instances of Object, and not some application-specific class?

Thanks much for any insights here.

-Cris

[Toon Verwaest]

Such optimizations are only true for receivers. If you have different prototypes all over the place, your code is going is not going to stay monomorphic. For every distinct prototype there's at least unique hidden class; given that the prototype link is hardwired in the hidden class.

regards,

Toon

--
--
v8-users mailing list
v8-u...@googlegroups.com
http://groups.google.com/group/v8-users
---
You received this message because you are subscribed to the Google Groups "v8-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to v8-users+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Jakob Kummerow]

As always: when in doubt, measure it! Implement several approaches (in a simplified version of your app if necessary) and see for yourself if any of the options you're considering makes a difference.

Generally I would say that what applies to objects also applies to prototypes (as they're objects too), but your question is too vague to even try to give a precise answer. As Toon said, the key idea that we keep emphasizing is to keep code monomorphic, but you stated that your code relies on polymorphism, so much of the battle is already lost anyway. 

As for inlining,  that's generally at odds with polymorphism -- when you don't know where a call is going, how can you possibly inline it? (Well, you can, but you have to inline all possible targets, which makes it a much tougher tradeoff.) Maybe it doesn't matter if your bottleneck is elsewhere?

[Cris Perdue]

Toon, Jacob,

Thank you both for your interest in the subject and and taking time to respond.

I am  encouraged by some of your comments, in particular Toon's that receiver code can be optimized (presumably when "this" is of the same hidden class in all calls); and Jacob's comment that what applies to objects also applies to prototypes.

For what it's worth, my application uses trees of expressions of different types (classes), with recursive methods that walk over those trees, so the  recursive methods cannot generally be inlined in any case.

To be more specific about my optimization question, I am imagining that object property lookups, including method lookups, may be inlined when a variable always has the same hidden class. (I understand that the method body would not be inlined.) I am further hoping that the good performance of method lookups can extend to situations where the method is a property of the prototype(s), even when receivers can have different prototypes, provided that each prototype is built with the same properties, added in the same order, so hopefully having the same hidden class.

The recommendation to measure of course is always a sound one. I am hoping you all may be able to help me avoid spending my time on experiments that pursue optimizations that do not exist.

Best regards,

Cris

--

--
v8-users mailing list
v8-u...@googlegroups.com
http://groups.google.com/group/v8-users
---

You received this message because you are subscribed to a topic in the Google Groups "v8-users" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/v8-users/Heqrs8ob3n4/unsubscribe.
To unsubscribe from this group and all its topics, send an email to v8-users+u...@googlegroups.com.

[Toon Verwaest]

So exactly in that you will not get speedup with the _current_ system.

Since the prototypes are different objects, the receivers will have different maps. That means you are doing a polymorphic call. In Crankshaft we have an optimization that tries to handle those cases as if they were monomorphic, but only if the prototype object of all maps is exactly the same object. See line src/hydrogen.cc:6054:

6039 bool HOptimizedGraphBuilder::TryCallPolymorphicAsMonomorphic(

...

6051   for (int count = 1; count < types->length(); ++count) {

6052     Handle<Map> test_map(types->at(count));

6053     if (!CanLoadPropertyFromPrototype(test_map, name, &lookup)) return false;

6054     if (test_map->prototype() != *prototype) return false;

6055   }

We could in the future extend this to do exactly what you suggest (probably fairly easily); but it's not there right now.

regards,

Toon

You received this message because you are subscribed to the Google Groups "v8-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to v8-users+u...@googlegroups.com.

[Cris Perdue]

Great information, thanks so much.

It would be super-cool if v8 could use cleanly-structured prototype chains to do fast property lookups. If I understand correctly, the potential would be for the performance of this sort of method lookup to be somewhat comparable to lookup of overridden methods in Java -- something worth looking forward to.

Cheers,

Cris