Problem-solving: Provide better interface for dispatchers

[vrurg]

My recent work on dispatchers and its fallout revealed a couple of weak points of the current implementation of dispatching support. Namely: low flexibility and impact on optimization.

The low flexibility is best explained by means of the problem I was solving: dispatchers were isolated from each other, they did not chain. Thus, a multi method didn't invoke a next method from MRO when it's local dispatcher chain is exhausted. I.e. multi and inheritance were mutually exclusive! The fix required a dispatcher activated for the first time by a routine to know if there was upstream dispatcher which invoked the routine. In other words, the dispatcher must know which next dispatcher is must pass control to when its own candidate list is exhausted. Basically, I needed something like nqp::setdispatcherfor but for a different purpose. Unfortunately, there is no generic way to pass such per-call information.

The problem with optimization is even more apparent. We always had $*DISPATCHER installed into lexical space of a routine alongside with nqp::takedispatcher to fill in the variable. This part alone requires additional care from the optimization. Now, to get dispatcher chaining working, I had to install $*NEXT-DISPATCHER with similar semantics and accompanied with nqp::takenextdispatcher. That'd be better to get rid of both altogether.

[vrurg]

My first idea with regard to the issue was expressed in this comment. @niner mentioned on IRC today that use of strings as identifiers are not welcomed. Anyway, I think that some kind of similar API would most definitely be useful not only now for supporting dispatchers, but in the future it might find other uses too. It must fulfill the following requirements:

1. The data exists per single call.
2. Perhaps all or some data is wiped out as soon as it is fetched.
3. Internally the structure holding the data doesn't exists until a write is requested.
4. It must be accessible via a context.

Here how it can help optimization.

For now each routine has to take a couple of steps to make it ready for any of callsame, nextsame, etc. no matter if they're gonna be used or not. But provided the dispatcher information could be obtained from a context, a re-dispatching routine can fetch it on it's own when needed. Say, nqp::p6finddispatcher could do this for a re-dispatcher so we could get rid of extra lexicals per-routine scope and of ops setting them. This alone already can provide certain performance gains. Depending on implementation, it might also be possible to get rid of dynamic symbol lookup too.

The exact details of such API are not really relevant. For example, @niner mentioned on IRC that strings are better be avoided. Ok, nqp::setcalldata could use integer indexes, it's ok as long as it does provide the necessary means of offloading dispatching support to where it really belongs.

[jnthn]

Thus, a multi method didn't invoke a next method from MRO when it's local dispatcher chain is exhausted. I.e. multi and inheritance were mutually exclusive!

I'm glad to see this addressed, though would note it wasn't quite so severe as this sounds: it only comes up in the case you had multiple protos (which isn't so common); in the case of no (really implicit) proto or just one up in a base class, it was cloned into each subclass with the candidates of the parent and those of the subclass, so deferral worked through those. I'm guessing the solution adopted is smart enough to differentiate original vs. cloned protos and not duplicately invoke things?

The problem with optimization is even more apparent. We always had $DISPATCHER installed into lexical space of a routine alongside with nqp::takedispatcher to fill in the variable. This part alone requires additional care from the optimization. Now, to get dispatcher chaining working, I had to install $NEXT-DISPATCHER with similar semantics and accompanied with nqp::takenextdispatcher. That'd be better to get rid of both altogether.

Generally, anything that touches dispatch will need a lot of optimization care, since dispatch-y things are very performance sensitive. Unfortunately, one can't design or modify these things without having performance as one of the key considerations from the start, otherwise the results will be slow (or slow down other things that are fast, which is what we're seeing here).

And this isn't just about the recent changes; the whole takedispatcher/setdispatcher/finddispatcher mechanism is old. It pre-dates our entire specialization infrastructure, and most certainly can't benefit from it. While inlining kinda knows a bit about eliminating unrequired takedispatcher ops, which would otherwise block inlining, the analysis is pretty much boiling down to "did somebody do a setdispatcher in the caller". It doesn't really do anything to make callsame and friends efficient. The mechanism also depends on a p6finddispatcher op, which is a big blob of C code that is also an inlining and analysis blocker.

Ultimately, callsame in the simple inheritance case should be able to specialize into a call to the method in the base class - and then potentially be inlined. Wrappers should be similar. The multi dispatch case is a bit more involved, but ideally we'd be able to do better there too. To do this probably means reconsidering the entire approach rather than tweaking around the edges. Making it effectively free for anything not using dispatchers is certainly a very desirable goal, thus getting rid of the dynamic variables along the way. But if we're going to address this, I'd like to make using callsame about as efficient as doing self.MyParent::bar(), which these days is quite well optimized thanks to a spesh plugin.

I'll spend some time thinking about it and playing with some designs, and see what I can come up with. Ideally, whatever that is might solve some other problems too.

[jnthn]

I discovered that the fix also still has composability issues. This:

class B {
    proto method m1($) {*}
    multi method m1(Int) {
        say "B m1 Int";
        callsame;
    }
    multi method m1(Any) {
        say "B m1 Any";
        callsame;
    }
}
class C is B {
    proto method m1($) {*}
    multi method m1(Int) {
        say "C m1 Int";
        callsame;
    }
    multi method m1(Any) {
        say "C m1 Any";
        callsame;
    }
}

B.^lookup('m1').candidates[0].wrap(-> | { say "m1 wrapepr"; callsame });
C.^lookup('m1').candidates[0].wrap(-> | { say "m1 wrapepr"; callsame });

C.m1(42)

Outputs:

m1 wrapepr
C m1 Int
C m1 Any
m1 wrapepr
B m1 Int

This misses B m1 Any; if you comment out the wrapping of the candidate in B, then this one is run.

[jnthn]

I've spent some time looking at what we have with regards to dispatch in general.

If anything has become clear over the years we've been trying to get Raku running fast - at least so far as JIT-y things go - it's that whatever's doing the optimizing needs to understand what's going on. Further back than that, it's been clearer still that dispatch of any kind is always a key thing to get fast. Moreover, things that we might not immediately think of as dispatch, but that can be made to look like it, can also benefit from such mechanisms (thus the use of spesh plugins for assignment and return value handling).

So far as the topic of this ticket goes, we've never really tried to model the idea that a dispatch might have a life longer than just the initial candidate selection in anything that's understood by the runtime. But as I've pondered what we might add for that, I'm reminded of something that became rather clear as I worked on the derived specializations: in trying to make different kinds of dispatch fast, I've created a monster.

It started out with method calls. Well, there we can just compute a hash of all the methods. In the early days of the current object model implementation, I figured: well, let's just compute the full "cache" up front. That solved some bootstrapping problems too (well, or rather, simplified the problem of finding a find_method to a one-level problem). However, when we have hundreds of exception types that all have a complete table (thankfully, lazily deserialized) with each method in Any/Mu - regardless of if they're called - one starts to wonder just how much space those take in our bytecode files. Also, this kind of thing isn't really optimal for the common fixed-name monomorphic case, which is why spesh adds a sp_findmethod that is good at that. Not very good if the thing turns out to be a bit polymorphic rather than totally monomorphic though...

Then came multiple dispatch. Of course, we need a fast way to figure out which candidate to call. Thus, a multi-dispatch cache. It's a tree structure, keyed on callsite, and then beneath that a graph to traverse to find the correct candidate. That's nice. Made things much faster. At some point it learned something about named args too, I think...

That's all relatively ancient history compared to spesh, which produced specialized bytecode based on the types of arguments that a piece of code is invoked with most commonly. How do we find the specialization? Well, we have an argument guard tree. It's a tree structure, keyed on callsite, and then beneath that a graph to traverse to find the correct candidate. Hm, where'd I hear that before?

Spesh got us a long way, but it turns out that There's More Than One Way To Find It. Sure, method calls could be specialization-linked or, if they were small, inlined, but what about private method calls? Or self.Foo::bar? Those weren't real method lookups, and the method cache only knew about the real ones. Thus spesh plugins were born: a way that we could say things like "well, if this dispatch argument has this type, then the result will be this", have have the runtime cache it, and the specializer know about it, and then look at its type stats and decide to perhaps inline it, etc. The spesh plugins mechanism can also look into objects, which turned out to be really quite useful for optimizing assignment, and since you could return identity, which inlines to approximately nothing, it was a good general mechanism for eliminating type checks that we could prove unrequired too, thus its application to return type check elimination. Did I mention that spesh plugins also have a graph that they traverse to find the correct plugin result? Apparently I really love implementing those...

So we have 3 things that all traverse graphs, and one that kinda wishes it could too, and all four dispatch mechanisms. And not one of them has any idea that a dispatch might involve more than just finding the initial candidate, and instead be something we want to return to later - when in fact methods and multi dispatch both need to, and a third case (wrap) isn't even something the runtime has any idea about.

Ultimately, we don't just need a better interface for dispatchers; if we step back and look at dispatch a bit more broadly, we need an interface. One. To rule them all. And one unified tree lookup thingy too, not three implementations of that that differ in interesting ways, but probably none so strongly that they can't be unified. And as part of that interface, they should cope with resumption, and knowing that resumption results can also sometimes be cached.

Which is a decent bit to do, and thus it may well be that I should look at if I can band-aid the next dispatcher thing somewhat, because I suspect there's more than a month of work in what should be done to solve this properly, and I don't want to have Rakudo releases blocking on me.

[jnthn]

This is now at the point of having detailed design work and also some initial implementation work towards that design. Further, the changes that were release-blocking were reverted. I'm not sure having this issue remain open serves a purpose; if somehow the implementation work on the solution stalls it can be reopened.