idea: polymorphic IC budget theft

[Seth Brenith]

Hi everyone,

I'd appreciate any feedback on the document linked below. It outlines an idea I've been kicking around for a while, which I hope could reduce the polymorphic->megamorphic performance cliff in some cases.

https://docs.google.com/document/d/1j9uXBT_wudNjM1wobHt2KxxjwwgRcAjsTNs5y_0GwpM/edit?usp=sharing

Thanks!

[Leszek Swirski]

Hi Seth,

Thanks for the doc and the in-depth analysis. I think the approach you're proposing is a clever low-memory-cost extension of the current IC mechanism, but I'm not sure it's more than a patch over a system that needs to be more fundamentally re-thought for things like constructors and a general increase in hierarchic polymorphism.

We've been brainstorming a bit on-and-off over the last few years about more radical solutions to this problem, such as "minimorphic" feedback (storing a set of maps that all share the same handler), storing (something like) descriptor arrays rather than maps, storing feedback along the lines of "I know it's an own property", embedding full v-tables into objects, or even having different feedback for different constructors (with call-site specific feedback or some other similar feedback forking mechanism). bit.ly/v8-investigation-of-class-performance summarises a few of these options, others are scattered around other docs or in people's heads.

- Leszek

--
--
v8-dev mailing list
v8-...@googlegroups.com
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to v8-dev+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/02852c79-6e06-4c4c-aee5-d1327d7521d5%40googlegroups.com.

[Seth Brenith]

Thanks Leszek for the thoughtful response!

I really like the minimorphic idea; it's simple and would provide a lot of benefit. I'd be interested to hear more about the other options you mentioned that aren't in that document, if you ever happen to come across other documents that might be relevant.

A few months ago I tried a prototype that added a new feedback sentinel state I called "single successor", meaning "for all of the maps seen, we've followed the only transition option and added a data property". This is the common case in constructors. It ended up about the same speed as a hit in the megamorphic stub cache, because it still requires several loads (get the successor, check that it's not deprecated, get its instance descriptors, and check that the property at the index we're adding is actually the right property). I guess maybe there's some value in not polluting the megamorphic stub cache, but it seemed to me at the time that the extra complexity wasn't worthwhile. The crucial thing that was lacking compared to the polymorphic case was that in a polymorphic constructor, TurboFan can do a great job of propagating type information around to avoid re-checking things that it already knows. There's just a single polymorphic switch at the beginning of the function, followed by simple straight-line code that sets a bunch of properties in a row. This budget-theft idea is my attempt to get back that simple straight-line code in more cases. A couple of other ideas for constructors that are less fully formed:

• Just inline super-constructor calls much more aggressively than other calls. This would allow TurboFan to propagate the types through and likely turn a lot of those megamorphic stores into monomorphic in the generated code.
• Track whether prototypes have setters (or interceptors, proxies, etc.) with a bit on the map. Then, if a function is only called with "new", we know that "this" didn't escape before function invocation (thanks ES spec for not letting child constructors touch "this" before calling "super"), and setting properties on "this" also doesn't cause it to escape. So until we do something else with "this" (return it, pass it to another function, or fetch a property from it), we can temporarily set this.__proto__ to be the current constructor's prototype, not the most-derived prototype. This would make a simple constructor (even one with many subtypes) act monomorphic. We'd have to reset this.__proto__ to the right thing when deopting, and there are probably a lot of other considerations that I'm not taking into account. Also, this would punish anybody who likes using setters, but if we follow the C++ mantra of "only pay for what you use", then this means folks who don't use setters don't have to pay for the fact that every line of their constructors are essentially virtual method calls.

Thanks,

Seth

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

[Toon Verwaest]

Hi Seth,

I like the clever budgeting approach, and we've indeed seen similar issues as you describe with approaches we've tried: The megamorphic stub cache is pretty damn fast and it's hard to beat it with dynamic structure walks. Performance with stub cache is hard to predict though, since it's non-locally polluted. If we can get close with e.g., an approach that looks for single outgoing transitions (we've thought about the same fwiw), that might be globally beneficial.

The approach of reusing the parent map is definitely clever, but seems pretty hard to guarantee that the object doesn't flow anywhere in unoptimized code. I think we'll pretty quickly end up with performance footguns (or correctness/security issues).

I agree with Leszek though that we should look at more fundamental solutions to especially the subclassing problem. Subclasses will typically have exactly the same shape for the shared superclass part, but still those accesses (also non-transitioning and non-stores) are polymorphic. We should be able to come up with a fundamental change to the object model that solves this.

As Leszek mentioned, we've lately been thinking along the lines of interfaces/vtables to solve this. For each base class we could create an interface that describes all megamorphic properties on the class hierarchy, even properties not supported by the base class itself. Subclasses "implement the interface" with a vtable that describes for each property supported by the interface how to access the property. The interface can also point back to all classes that participate in the interface. That way we have steady (but probably not as fast as stubcache) baseline performance, and have detailed information we can feed into the optimizing compiler. It's still a very early idea though.

Other ideas involve separating receiver shape from prototype (and even native context). We're also thinking of ways to get more static guarantees wrt the shape of class hierarchies.

Do keep the ideas coming though!

cheers,

Toon

To unsubscribe from this group and stop receiving emails from it, send an email to v8-dev+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/caaf2c48-6388-48c1-a69e-68312755609c%40googlegroups.com.