What don't kill you will make you more strong
Broken, Beat & Scarred - Metallica
The largest, trickiest part of my current Hague Grant has been an extensive refactor of method dispatch. It's the second major refactor of method dispatch that I have done in the course of Rakudo's development, and while I know there's going to be some tweaks from here to address some more subtle aspects of the semantics, I'm very hopeful that this will have been the last major refactor needed on the path to a Rakudo 1.0.
The last time I refactored method dispatch, it was to allow us to get a bunch of new features implemented, and to allow fast prototyping of many of the things we'd need. In that sense, it was a very successful refactor, and the ease with which I've been able to get all kinds of things in place - role punning, the handles stuff and junction dispatch from the last grant, correct multi-method dispatch semantics and more - has been very helpful for Rakudo's development. However, as we've come further along, a few things made it clear that this approach wasn't going to sustain us through to 1.0.
Firstly, it just didn't perform well enough. Method dispatch was running notably slower than sub dispatch. However, the real killer was multi-method dispatch. The previous refactor had opened the door to getting the semantics correct, but while multi sub dispatch was running nice and fast, there just wasn't a nice way to get the level of interplay between the method and multi dispatchers that I felt we really needed to have a shot at acceptable performance.
Secondly, my original thoughts on how we might implement deference - a more exception based model - turned out not to be the way we really needed to go. I will write in more detail about this in a future post with some examples, but in a nutshell deference is the idea that a method can defer to the next one in a superclass. However, if it's a multi then we defer to the next best multi candidate if there is one instead. Deference can keep the original arguments or use a new set, and can either fully defer (like a tailcall) or do something more akin to a call and get the results back to do further processing. Larry also felt much more strongly than I had expected that .wrap functionality on routines should operate through the same mechanism (I agreed that we really should unify the mechanism after pondering it for a while). Again, this issue involves the interplay between multi dispatch and method dispatch - there wasn't just a performance issue to worry about, but also a big semantic one.
Thirdly, the previous dispatch refactor had hurt our language interoperability a bit. Up until recently, the promised land of high level language interoperability in Parrot had been more promise than reality, but that picture has changed of late, with Tene++ posting concrete examples of calling between Cardinal (an early Ruby on Parrot compiler) and Rakudo. There's really not much point implementing Perl 6 on Parrot if we're not going to be able to interoperate decently with other high level languages on Parrot.
The performance and interop problems were partly the same issue: the previous dispatcher wasn't really built on top of the Parrot model for doing such things (which is, subclass Parrot's Object PMC override find_method). So one of the principals for the refactor was to build Perl 6 method dispatch semantics on the Parrot find_method/invoke model.
Figuring out how to build a method dispatcher as complex as the one needed for Perl 6, which would fit neatly into the Parrot model, have a good chance of working well when invoked from other high level languages, solve the deference problem, get the interplay with multiple dispatch right and on top of that lot actually have a chance of performing well, was non-trivial. I got us a bit of the way in small steps, but eventually I hit the point where it was time to do the big switch. It goes without saying that I was especially glad of the test suite at this point. The fact that I was able to do a complete switch in the way how something so fundamental worked and hear of almost no regressions to people's real world Perl 6 code when I committed it is a testament to the hard work that many have put into Perl 6 testing. So, a big thank you goes out to all involved!
So how does method dispatch look now in Rakudo? First, let me note the steps in invoking a method in Parrot. First, the find_method vtable method is called on the PMC representing the object. This hands back another PMC, which we call the invoke vtable method on to invoke it. Normally in Parrot, when you do a find_method, Parrot goes off and finds the PMC representing the chunk of code we need to execute (a Sub object or some subclass of that) and returns it. In my overridden find_method, we instead hand back a P6invocation PMC. This contains the method we will dispatch to. However, it also contains something else: the information needed to continue looking for more things to dispatch to in the event we later are asked to defer. That is, it doesn't find all of the things we might have to dispatch to. It just makes sure we have the information to do so at some future point. This lazy approach means that ordinary dispatch-and-we're-done calls aren't paying the cost of deference. However, in the event we need to find more methods, it can act like an iterator and provide them. This, conveniently, is exactly what we need to implement .can, which in Perl 6 returns a lazy iterator of all of the possible methods rather than just a boolean value (though I didn't implement this just yet - I'll get to it). One final thing: I think I can keep the initial P6invocation immutable, so we'd be able to cache it in a method cache at some future point and have even less work to do.
So anyway, that's what our find_method does. P6invocation's invoke, then, just knows the first result and goes and invokes it. But it has to do one little thing more than that: it needs to store itself in a place accessible to things like callsame/nextsame and friends which defer. It turns out that fudging it into the lexpad during the invoke is a very neat way to do this. For one because it means if people start doing evil things like returning a closure from within a method that defers, we'll probably do something sensible. It also means its lifetime is neatly managed for us, since it's tied to the "activation record".
So how far along is all of this? Well, the refactor is done, pushed and if you're using the last release of Rakudo or the latest git head then you're already using it now. I'm not yet done with building all of the bits of deference on top of it yet, so don't expect all of that to work at the moment. It's coming soon (I'm happy that the dispatcher fundamentals are correct, the issues are actually now in callsame and other such routines). Furthermore, I already refactored method wrapping to work in terms of candidate lists and P6invocation too. So that bit of my grant can be ticked off. (This refactor also meant that we started passing some more wrap tests too. In fact, until somebody - I forget who - recently discovered an odd bug in interaction between wrappers and lexical scopes, I really thought wrap was, uh, all wrapped up. Well, such is software development...
So, that's another installment in my Hauge Grant progress blog posts, and another significant step forward for Rakudo. Next time, I'll probably look at traits or deference. And yes, there'll be more code and less discussion of bird guts. :-)
