Optimizing Parrot

Let's all face reality here: All the recent refactors of Parrot, including the ongoing PCC refactors, have either a neutral effect or a negative effect on Parrot performance. dukeleto showed me an eye-opening comparison between several versions of Parrot and the most recent rev of pcc_reapply that showed a stunning 400% execution time increase for some benchmarks between the 0.9.0 release and the current branch revision. That's terrible.

The Context refactors added about a 200% execution time increase. The PCC refactors are currently adding about another 200%. The fact that these two systems overlap so closely is certainly only exacerbating the problems. So why are these two refactors responsible for so much slowdown? Let's look at each in detail.

The Context refactor converted the Parrot_Context structure, which was manually memory-managed using bit twiddling reference counts, into a garbage Collectible PMC type. Had the changes stopped there, I have the strong belief that this would have been a neutral change in terms of performance. If anything I would suspect that this change would have been a small win overall. No matter how lousy and inefficient our Garbage Collector is, I have to believe that the tight loops and spacial locality of keeping PMCs together would be a good thing. Also things like the memory allocator in the collector are pretty efficient (although could definitely be improved). However, the refactors did not stop there. bacek also went through and properly encapsulated the Context PMC type so that there were fewer direct accesses of it's internal members. All accesses happen now through API calls, which are significantly more expensive. Plus, every field access adds an additional pointer dereference now too. Together I don't really know how these things could have added a 200% performance penalty, but it's pretty well documented that they did.

The PCC refactor is adding in a new abstraction step in the calling process. This makes the code prettier, along with much more maintainable. The cost is in making some of the operations a lot less efficient. Some of this is the fault of the new CallSignature PMC, which naively integrates several array and hash PMCs, inheriting from the oddly-named Capture PMC in the process. All strings, integers, and numbers are autoboxed into PMCs during the creation of the signature, and all return values get a CPointer PMC to hold the pointer. This is not to mention that several of these values are only accessible through named lookups, and you start to see a major performance problem. We're creating a shittonne of new PMCs for every call, and then using relatively expensive VTABLE accesses to recursively access the data in them.

chromatic has been doing some great work in the past few days rewriting the naive CallSignature implementation into a much more efficient form. Many of the operations can be more specialized for the task at hand, and the number of created PMCs can be reduced dramatically. bacek has also been doing some good work in this area, mostly small bits and pieces around as he finds them. So the situation isn't hopeless, but we are going to have to tighten several things up if we want Parrot to be as screaming fast as it was in 0.9.0 (if not faster).

Now that we have a very well-designed system, there are plenty of places where we will probably want to break encapsulation for a performance win. A few places where we will want to write some ugly code instead of the current prettier code, also for a win. We'll just make sure to mark these places with lots of documentation.

I've been focusing my attentions on fixing bugs. This weekend chromatic and bacek have been looking into them also, and together we're down to 1 remaining failure at the time that I write this. The last few tests were all very tricky, but this last one is turning out to be the worst of the bunch. I think we'll be able to beat it this weekend, however. After that, we're focusing on optimization until we're ready to merge the branch, probably soon after the 1.7 release.

So that's where things stand in terms of performance. Parrot has a lot of ground to recover since 0.9.0, but I am convinced that there are plenty of opportunities to do just that. Some of it will be algorithmic improvements, some will be small intelligent tweaks to individual functions and datastructures, and some will be real low-level bit-twiddly nonsense. However it happens, we really need to make Parrot faster, and I have very high confidence that we will be able to do just that.

Matrixy: Moving Forward

The world of Parrot is an ever-moving target, but my poor compiler project Matrixy has been laying fallow for several months. Matrixy, for those who haven't seen me write about it before, is an implementation of the M language (MATLAB/Octave, not the new, weird, .NET language). MATLAB/Octave is the standard language of choice for many branches of science and engineering. I have never seen another language, except maybe R, which is so catered to the task of design and simulation, and it has some of the best integrated mathematics support I have ever seen.

Matrixy History

I started what is now called Matrixy about two years ago now when I was still in grad school. Part of my thesis involved writing an assembler in MATLAB for a new processor architecture I was designing in the visual programming component Simulink. Since I was just getting involved in Parrot at the time (and was reading the classic Dragon Book cover-to-cover in my leisure time), I decided an M compiler would be a great project to start. I put it on hold during GSOC and immediately thereafter when I was still burried knee-deep in Parrot core internals work. Luckily the idea was rescued by a guy named Blair who set up a project on googlecode and together we made a lot of progress implementing the syntax and semantics of the core language. Part of the standard M package is a huge list of built-in functions, something we didn't even attempt to reproduce.

Blair moved on to other projects, and I haven't turned back to Matrixy in months. It's sat completely dormant for months now, and needs a breath of life pumped into it. I can't think of a better time to do that either: With PCC refactors landing soon (I hope) and Plumage taking off, there is plenty of opportunity to get Matrixy up and running again. Here's a list of things I would like to do with the project, and I am looking for helpers and volunteers who would like to get involved.

Linear Algebra Libraries

Integral to M is comprehensive linear algebra support. This is what makes it such a great tool for engineers to use. Implementing these features, we've written bindings for Parrot to the CLAPACK and CBLAS linear algebra libraries. With Plumage quickly growing into a great ecosystem project, I would like to separate out the CBLAS and CLAPACK libraries into a separate "Linear Algebra Pack" to be dowloaded through Plumage.

This is going to require some work, however. CBLAS and CLAPACK have several functions with very exotic function signatures, and currently we would need to recompile Parrot to include them. Once Parrot has a proper NCI call frame builder, we don't need to worry about that.

Separating our libraries out into separate projects is going to help other languages and projects on Parrot who want to use them. However, it's going to require adding non-local dependencies to Matrixy's makefile. Small price to pay for the greater good.

Proper Matrix Data Types

One thing that M requires is a native matrix data type. We've managed to get along so far with an ad hoc system of nested ResizablePMCArray objects, but that's a terrible (and slow!) solution. Better yet would be to write up a good set of dedicated PMC types that implement a 2-D floating point matrix or vector. Having that PMC type support a sparse mode, or having a separate sparce array type would be fantastic too. If we included these PMC types with the "Linear Algebra Pack" that I talked about above, we would be able to quickly integrate robust linear algebra support in any language or project running on top of Parrot.

Imagine that in a few months time you could be using Perl6 or PHP or TCL to manipulate numerical matrices and performing complex linear algebra on them at blinding native code speeds!

Make Matrixy Installable

Matrixy currently doesn't work with an installable Parrot. In fact, Matrixy isn't really installable by itself either. We need to fix these things.

Matrixy needs to work against an installed Parrot so we can start properly tracking point releases instead of SVN head. Of course I always expect there to be exceptions to the rule, but it's a good policy to get into the swing of.

Matrixy also needs to be able to be packaged up and installed, especially through Plumage.

Move Matrixy to Github

Actually, this is something I think I can do on my own. I don't have any problem with Googlecode, but I feel the sea change pulling us towards Git and I would like to host at least one project through Git so I can start getting good with the tool. Github seems like a great place and I really like the social atmosphere.

Conclusion

Obviously there is a lot of primary development to be done too. We're a long way away from even having the complete syntax working, much less the semantics and the gigantic runtime library. However, with a few small changes Matrixy could be well along it's way to being not only a first class compiler project on Parrot, but a contributing force to other language projects as well.

If you have any knowledge about working with an installed Parrot, or working with Plumage, I would love to hear from you! Once I get things moved up to Github, I'll have plenty of commit bits to hand out to interested contributors.

PCC Hackathon

I'm busy moving today, so I scheduled a blog post ahead of time to help spur the troops on. PCC is a big deal, last weekend we kicked some serious ass as a design team. People were developing, debugging, testing, talking. It was awesome.

This weekend, lets take some advice from one of my favorite internet memes, Courage Wolf:



PCC is a big deal, probably one of the biggest. I can't think of any system that is more central to normal operations in Parrot, except the runcores (and they're much simpler). We've got a big task if we want to completely rewrite PCC from the ground, not only without losing any functionality, but actually adding new features in a sane way. It's big. It's more then we can chew, but we're going to chew it anyway. I have all the faith in the world in our development team.

The big question is whether we can chew it before the release. I sincerely hope so, and I know a lot of other people hope so too.

Hackathon Schedule

This week at the #parrotsketch meeting we decided a few things:

1. We need to keep up momentum on the PCC work. So, we're doing the hackathon thing again this weekend
2. Hackathons are good things, but they need to be used sparingly.

We can't just hackathon all the time, and the fact that we are trying to do it two weekends in a row is more a testament to the extreme necessity of these refactors. We want it and we're going to make an extended push to get it.

Conversely, if every day is a hackathon, no day is. We need to do it infrequently enough that people don't get used to it and tired of it. However, we need to have them frequently enough that we get good focus on big projects and develop good momentum. After this cycle, we're looking to do about one hackathon per month, depending on need and interest. More need means we do it a little more frequently, less interest means we do it a little less frequently. We've got plans penciled in for the next two months, ideas after that would be welcome.

This is the month of PCC. Next month we're looking at PIRC. It's not a huge necessity for us since IMCC still "just works", but then again there is a painfully small bus number for that system and we would like to get knowledge and interest higher.

The month after that I think it's going to be time for JIT. I don't think I am going to wait for a random hackathon in two months to get started, but hopefully we can lay enough groundwork for other developers to really latch onto and get going. Working in a void is hard, working on a pre-made foundation is much easier.

Besides development hackathons, we're also wanting to do testing/debugging hackathons. In the historical notes I think these used to be called "bug days", and tended to be the Saturday before a release. If we could make that a regular occurance again, it would be a great thing for Parrot. A day when we were dedicated to closing tickets, tracking down bugs, submitting smoke reports, and getting Parrot building and passing tests of various platforms would be a huge benefit. It would also get us into a better habit of keeping things clean and stable before the release, which is something we probably should be better with.

I'm moving to a new apartment this weekend, so likely won't be able to participate in most of the hackathoning. I will check in as often as possible.

Closing the Hotmail Account

I haven't used it in months really, but I've been keeping my hotmail account around because I still occasionally got mail sent there from people who haven't updated their contacts. Well, today I finally got a good reason to just go ahead and close the account. So I did that.

PCC Hackathon Day!

It was only decided at the #parrotsketch meeting on Tuesday so there wasn't a lot of advance notice. But we decided that on Saturday we were going to have a proper, focused hackathon on the PCC refactors. It was supposed to be an event that lasted all day on Saturday, but it ended going from Friday night through the entire weekend. The momentum we've built up is huge, and even though we haven't finished with the task yet I have very high hopes that we will be finished quite soon. I personally would like to see this branch land by 1.7, but I don't want to make any promises.

Mission Recap

In current Parrot trunk, argument passing happens in a variety of ways. Predominantely, there were two: calls made from PIR and calls made from C. The calls made from PIR stored hardcoded lists of arguments, register indices, in the compiled opcode stream. When a function filled it's parameter list, it would look through the opcode stream for the indices and use them to lookup register values in the caller's context. These were processed and massaged to fit into the various parameters that the function defined.

The second way to go about a call was from C. In this case, the arguments were passed as a variadic argument list, and passed around as a pointer to that list through the various processing functions. Finally, values were extracted from there and processed into the callee's context parameters.

This means we need six functions (or, six families of functions): Pack arguments into a variadic argument list pointer, pack arguments into an opcode stream, unpack variadic argument lists into C variables, unpack variadic argument lists into a PIR context, unpack an opcode stream into C variables, and unpack an opcode stream into a PIR context. And encapsulation is broken all over the place because callee needed to be aware of how it was called.

And this only covers passing arguments to a function, not the act of returning values from that function (which is similar, but currently distinct). In short, calling conventions were messy and desperately needed a refactor if we want to do any amount of new development on it.

Current Refactors

The goal of this current work is to unify the code paths for both types of invocation. In both cases we extract arguments (from the opcode stream or from the variadic argument list) into a new PMC called a CallSignature. The CallSignature contained information about the call, the list of arguments, etc. By marshalling everything through this new abstraction layer, we can make a method call from anywhere to anywhere without having to be aware of the details. All that needs to be worried about is how to put arguments into the CallSignature, and how to get them back out again.

I've mentioned these refactors several times on my blog in the past. They've been in progress for several months now and needed something like this hackathon to really get moving.

Argument Processing Algorithms

One of the problems we were having over the weekend is that the algorithm for implementing the argument processing mechanism is very complex. Parrot supports a wide variety of argument and parameter options:

1. Normal positional arguments. Positional arguments must be passed in order and all must be accounted for without overflow or underflow.
   
2. Optional arguments, which might or might not be provided without causing an error
3. "opt_flag" arguments, which are coupled with an optional argument and provide a boolean value whether the previous optional was supplied or not.
4. Named arguments, which can come in any order, and which use a string name to identify them.
5. Slurpy arguments, which take a variadic list of positional args and combine them into a single array PMC
6. Named slurpy arguments, which are similar to normal slurpies except they group all extra named parameters into a hash.

And it turns out that supporting all these things in a sane way is not trivial. I've put outlines of potential algorithms on the wiki, so the reader can get an idea about how complex these algorithms really are. The code to implement these is much worse, of course.

Current Status

The branch is currently down to a very managable number of test failures, most of them stemming from a few issues requiring primary development. Specifically, :named and :slurpy return values aren't supported, which produces several failures and prevents PCT from building. Last I checked there were no more segfaults or prematurely aborted test files. The only failure I didn't think I could explain was a failure in the subroutine tests dealing with IMCC. I'll look into those a little more too, if they haven't disappeared by now. Of course once we get all the core test files working, we're going to want to get HLLs building and testing on the branch, which could expose a whole new world of failures.

Parrot has a great team of developers, and when they got motivated to work on a single task we made some awesome progress. Hopefully we can keep the momentum going and get this refactor locked down and merged soon.

libJIT NCI Frame Builder Branch

I alluded to it earlier, but today is the big announcement: Newcomer Peter Lobsinger has developed a patchset to replace Parrot's ad hoc NCI frame builder with a libJIT-based solution instead, and sent it to me as part of my JIT Challenge. Well, today he set up a branch of Parrot on github with the patch for public review. I recommend that all Parrot developers check it out to see what kinds of things are possible in a libJIT-integrated Parrot.