PMCs: Now without PMC_EXT or UnionVal

Last night I fixed the last of the test errors that I was seeing and merged the pmc_sans_unionval branch into trunk. This branch made a number of sweeping changes, but the most important two were removing the UnionVal structure from PObjs, and merging the PMC_EXT structure into the PMC structure. The bulk of this work was provided via patch from newcomer jessevdam, I mostly did some cleanups and post-facto changes for consistency and cleanliness. I think it was much more important to get this change merged then to have it be perfectly pretty.

Almost immediately after I merged the branch reports of test failures on various platforms started rolling in. kid51 was seeing consistent failures on PPC. mikehh and GeJ were seeing consistent failures on x86 Linux too. I ran through the tests another two times before I spotted an intermittent failure on x86_64 too. I hadn't seen them when I committed, but they did appear about 1/4 of the time when I ran coretest.

The failures that kid51 was seeing were different from those that GeJ reported. It turns out that I was seeing both these failures on my machine too, about half the time when any failure manifested. A little bit of debugging this morning turned up the culprits: The first was caused by a strange situation where a PMC metadata object wasn't being marked properly by the GC and getting prematurely collected. This error was easy to spot because of a helpful debugging message that had been inserted into the GC code long ago. With this error fixed and the GC structure sufficiently changed, I removed that debugging message.

The second failure was more difficult to nail down. When I took a backtrace, I saw that the failure was happening deep inside the PCC system function call argument processing functions. This system is currently a hideous web of evil code, but luckily it is what Allison is working to refactor right now. I would have thrown up my hands in despair at seeing that, and given up on any hope of a fix but for one thing: I had seen a backtrace like this before when I was doing some early work trying to replace Parrot_PCCINVOKE with the more modern Parrot_pcc_invoke_method family of functions. The error, in a nutshell, is a PCC bug: PMC** arguments passed to a function call in order to receive a return value need to be initialized to point to a valid PMC value before being passed. This despite the fact that they should only be treated as a storage location and overwritten without ever looking at the value originally pointed to. Despite the "should" in that last sentence, somewhere along the PCC pipeline the values are being passed off to the GC which tries dutifully to mark it, and things go down hill.

This fix, unfortunately, means turning this:

PMC *retval;
Parrot_mmd_multi_dispatch_from_c_args(interp, "subtract", "PPP->P", pmc, value, dest, &retval);

into this:

PMC *retval = PMCNULL;
Parrot_mmd_multi_dispatch_from_c_args(interp, "subtract", "PPP->P", pmc, value, dest, &retval);

One line changed and now the test appears to be working perfectly on every system where I can get a report. I sincerely hope Allison can get these issues resolved in the PCC refactors work, because I hate tracking these kinds of issues down. If I hadn't recognized that backtrace and the problem that caused it, I would still not have a fix for this bug.

With this, three of the branches I mentioned before the release have landed: the auto_attrs branch, the Parrot_Sub refactors branch, and now the pmc_sans_unionval branch. Bacek is getting damn close to finishing the Context PMC work too (now in the context_pmc3 branch) too. I don't know where chromatic and cotto are in the pluggable_runcore branch, and I don't know where Allison is in the pcc_arg_unify branch either. But, I still have very high hopes that they will all land soon and Parrot will be a better place.

I'm shooting through some code today making miscellaneous cleanups. There have also been some problems recently involving the fixed-size allocator (especially on Windows) so I am going to have to dig into that issue soon too. Once I get that working perfectly again, I want to run some benchmarks. I bet we're going to see some significant speed improvements over 1.5.0 when all the numbers come in.

Parrot Release Managers

A while back Coke said I could take over the job of herding release managers, and I gleefully took him up on the offer. A few days ago I sent out an email asking for people to fill in for the remaining releases this year. Specifically we're looking for some fresh blood, new people to give the release a shot. Every new person we get doing releases helps to increase our bus number ever higher, and a good bus number is good for us (and bad for buses).

Shortly after the announcement I got a few emails from interested people, including a few from people who have never done a release before. Signed up fo the rest of the year are: particle (1.6), dukeleto (1.7), bernhard (1.8) and gerd (1.9). After that the schedule is wide open.

I've managed a few releases at this point, and I can say with some confidence that it's really not a hard process at all. Actually, there are several steps that I think would be ripe for automation and could become even easier, if an intrepid releaser were interested in doing so. I won't opine about that too much here, just mentioning it off-hand.

Here are the basic steps for making a release.

1. Send out some messages on IRC and on the mailing list for people to update NEWS and PLATFORMS.
2. Update NEWS and PLATFORMS yourself, because everybody ignored your messages to the mailing list.
3. Update the version number in a variety of files, even though we have computer programs and programming languages capable of incrementing digits.
4. Come up with a name that's too clever by half. Don't tell anybody, that would ruin the surprise (Since our release schedule is so regular and predictable, we need to have some surprises!)
   
5. Waste 20 minutes of your life Run fulltest. I like to spend this time watching TV, chatting on IRC, eating junk food, or looking up funny pictures of cats on the interwebs.
6. Make the release. This is the hard part: Type "make release VERSION=a.b.c".
   
7. Unpack the tarball into a new directory. Build it and waste 20 more minutes of your life run make fulltest again.
8. Upload the tarball to the FTP server
9. Send out a bunch of announcement emails telling people that we've made a release even though we could program Google Calendar to do this on the third tuesday of the month, every month, for the next thousand years. Tell everybody it's a big deal regardless of how dependable and boring our release cycle is.
   
10. Rake in the karma on IRC.
    

I am joking about several of these things, obviously. I make light precisely because it's not a big deal by design. We want Parrot releases to be quick, easy, and regular. Unextraordinary (ordinary?). It's easy to do, and we want lots of people to do it. It's easy, it's no big deal, there is no reason why you shouldn't be involved in it.

Branches Come Crashing In

The release wasn't barely out the door before some branches started merging into trunk. Just like I predicted, there were a few changes ripe and waiting to land as soon as the feature freeze was listed, and so they did.

First, NotFound's auto_attrs branch landed, bringing with it a change to almost every PMC type and a major simplification to the way PMC attribute structures are managed. Also, it is the first major user of the fixed-size structure allocator I developed last month, so it's a cool test of that. My hope is that once we've given it a good exercise we can start using the allocator in a variety of other places where we need small, fixed-size structure allocations and we are able to manage the lifetimes of those structures manually. This branch represents a big algorithmic improvement and with a few cleanups, improvements, and optimizations, this could usher in some other big changes in the near future.

Closely thereafter, bacek (who I swear is some sort of magical coding robot) landed his branch to cleanup the Sub PMC and remove the Parrot_Sub structure. This brought with it another huge changeset that swept most of the repo, but provided us with some major improvements to subroutine allocation and management (not to mention some much-needed code aesthetics). Very nice.

That success out of the way, I suggested he take a look at the context_pmc2 branch and see if he could work some similar magic on the Parrot_Context structure and the new Context PMC. Less then 24 hours later he had a gigantic change committed that not only cleaned up the structure but completed the conversion and got Parrot to build! There were some segfaults in miniparrot during initialization though (trying to create the first context before all the PMC types were initialized, and things like that) so it wasn't perfect, but was quite good progress. I just committed a fix to the initialization logic, and bacek claims that he'll be able to get the branch finished by the end of the day. Magical robot indeed!

I talked with Allison last night about the pmc_sans_unionval branch which I had gotten building and passing all tests (including codingstd tests) and was ready to merge in. However, by the time I got the thumbs up and was ready to merge, the above two branches had already landed and I could no longer merge that branch cleanly. Now, the branch segfaults on one particular test (t/pmc/complex.t) because of a bad pointer in a RetContinuation PMC, which I haven't been able to track down yet. As soon as I can get that last test to STFU, I'll merge that branch in as well.

I'm hearing good news about the pluggable runcores branch and the profiling stuff from chromatic and Cotto. Not to mention the long-awaited PCC refactors that Allison has been working on. With any luck we could see both these two branches landed into trunk soon, folloed by a flurry of activity from people wanting to use and improve these new toys.

Yesterday at the #parrotskech meeting, chromatic asked what the weekly development priority should be and I suggested, knowing how many branches were poised to land, that we should focus on basic, raw stability. With a few test failures being reported here and there it seems that might not have been such a bad suggestion. Plus, as I mentioned above, there are at least three branches that could plausibly land soon, which will just increase the short-term instability. Basic program stability is a very good thing to focus on (and it gives us a good excuse to write a bunch more tests for all the fun new things).

So things are moving quickly and I hope that the rest of this release cycle stays as eventful as the first two days were. I'm also looking forward to tomorrow's Rakudo release because I've heard good things about that too.

Parrot 1.5.0 "TEH PARROTZ!" Released!

I released Parrot 1.5.0 a few moments ago. Here's the release announcement:

On behalf of the Parrot team, I'm proud to announce Parrot 1.5.0 "TEH PARROTZ!." Parrot is a virtual machine aimed at running all dynamic languages.

Parrot 1.5.0 is available on Parrot's FTP site, or follow the download instructions. For those who would like to develop on Parrot, or help develop Parrot itself, we recommend using Subversion on our source code repository to get the latest and best Parrot code.

Parrot 1.5.0 News:

- Core
  + Removed several deprecated functions and features
  + Removed bsr, jsr, branch_cs, and ret opcodes
  + Removed global stacks system
  + Changed OPS file format to include explicit preamble
  + Changed all "new 'Iterator'" instructions into 'iter' instructions
  + Removed Configure.pl options for specifying non-working GC cores
  + Removed unexecuting code as found by Coverity
  + Improvements to the Parrot Debugger
  + Added experimental fixed-size structure allocator to the GC
  + Added experimental lazy arena allocation to the GC
  + Removed the defunct PASM1 compiler object
  + Refactored hashes, keys, and iterators
  + Added "corevm" make target to build Parrot without all the supporting libraries
  + Removed Random PMC type and added in a "rand" dynop
  + Optimization and Improvements to the NCI thunk generator
  + New include file libpaths.pasm
- Compilers
  + Multiple .local with same name and different type is now an error on IMCC.
- Platforms
  + Improved support for detecting Fink and Macports
  + Updated search directories for libraries
- Documentation
  + "Parrot Developers Guide: PIR" released to publisher and available to purchase
  + Improved documentation about Parrot Debugger
  + Update PGE Documentation
- Miscellaneous
  + Added tests
  + Fixes to code, documentation, and standards

Thanks to all our contributors for making this possible, and our sponsors
for supporting this project. Our next release is 15 September 2009.

"TEH PARROTZ!" is a name that I've been wanting to use for a while. It pays nice homage to a popular internet meme and shows that we're having fun and that development isn't always SRS BIZNS!!



It can be a lot of fun, especially as more new people are getting involved. And with the release out of the way, we can get back to some serious development.

Ongoing Branchwork

As I mentioned yesterday, I called for a freeze on big changes to trunk before the Parrot release. However, that doesn't mean that development ceases entirely, and some branches are still moving forward at a pretty nice clip. With the 1.5.0 release coming out tomorrow, we could see some of these things land tomorrow.

GC Refactors

A few days ago I was pretty stunned to see a huge patch from newcomer jessevdam that had some major effects on the GC. What he set out to do was remove the UnionVal structure, which was a large and obnoxious union of several data storage types, from the PMC structure. What he ended up doing was far more then that.

What jessevdam did was to remove the UnionVal structure from Parrot completely, fix up several other structures that used it (STRING, Buffer, etc), merged the PMC_EXT structure into the PMC structure, renamed several macros, added some documentation, and made a variety of other cleanups. The patch was huge, and not only that it was invasive, so I applied it (and some subsequent cleanups) to the pmc_sans_unionval branch for testing. Initial test results that I have been seeing are all clean, so if we can get some approval from Allison about it's methodology, I would like to get it merged to trunk shortly after the release.

Context PMC

I created a new branch this morning to tackle the first stage in the process to convert the Parrot_Context structure to a PMC. I had the realization that there are really two separate reasons for making this conversion: First we want to get Contexts to be properly garbage collected, so we can avoid several outstanding memory leaks. The second is purely a refactor, we want to properly encapsulate the Context functionality and cleanup the code that uses it.

So instead of replacing the Parrot_Context structure wholesale, I am taking a path of less resistance: Keeping that structure as-is, and creating a PMC type that acts as a simple wrapper for it. See, for example, a similar strategy used for the Sub PMC (Parrot_Sub struct) and the Continuation PMC (Parrot_Cont struct). This makes the structure garbage-collectible with a minimum amount of effort, but doesn't do anything to make the code cleaner, better encapsulated, or have better performance. I've started this messy process in the context_pmc2 branch, and am having some promising results so far.

After I get that branch building and passing tests, I plan to merge it in and then start another branch to work on performance, encapsulation, and other improvements. Of course, this second branch will probably have to wait for a few other branches to land first so it doesn't get in the way of other ongoing work.

On a related note, for cleaning up the Parrot_Sub stuff that I mentioned above, bacek has started the tt795_kill_parrot_sub_structure branch. That branch will serve as an archetype for the second round of Context cleanups, since I'm purposefully creating the same "situation" with the Context PMC that we are trying to resolve using the Sub PMC. I've heard from him that this branch is complete and ready for merging in right after 1.5.0.

PMC Attributes

NotFound's auto_attrs branch is getting pretty mature and I hope he is able to commit it to trunk shortly after the Tuesday release. We are definitely going to talk about this in the #parrotsketch meeting tomorrow. It's my hope that once this new PMC initialization mechanism is added to trunk, we will be able to start using the fixed-size memory allocator in other parts of Parrot as well for some major speed improvements.

PCC Refactors

Allison is still hard at work on the PCC refactors, having recently started the new pcc_arg_unify branch to get going on it again. If she can successfully unify the way arguments are passed to subroutines, and get rid of some of the older entry points to the PCC system, it will be a huge win for Parrot. Plus, as I've discussed at length before, those kinds of refactors will enable so many other stalled projects to leap ahead quickly. I have high hopes that if this branch lands soon that we will see some major improvements to other areas of Parrot, based on this work, being added as early as 1.6.0.

Pluggable Runcores

chromatic and Cotto have been working on a very cool project in the pluggable_runcore branch. The goal, in grave oversimplicity, is to treat runcores as dynamically-loadable libraries. Also, they're hard at work using the new loading mechanism to add a much-needed profiling core. I don't know what the ETA is for that branch, I don't know if it will make it in to 1.6.0 or not.

Conclusion

1.5.0 is going to be a great release because so much crufty old nonsense has been removed from it. And with all the cool new features waiting in branches to be merged next month, 1.6.0 has the potential to be even better.

Approaching the 1.5.0 Release

I'm dressing up as the release manager for Parrot this month, hoping to push 1.5.0 out the door without any major issues. This is going to be quite an impressive release for our community because 1.4.0 was a deprecation point, and 1.5.0 is going to be the first release where not all features present in 1.0.0 will still be available. And a lot of old "features" have been through the grinder this month.

Because of all the massive changes and removals of features, I sent an email to the list a few days ago asking for a freeze on big changes or branch merges starting today and lasting through Tuesday. I want to make damn certain that trunk is stable when it's time to push it out of the nest. To that end, I am asking everybody who is reading this blog post right now to get the latest version of Parrot trunk from SVN and submit a smolder report on your platform. These reports are very important, and will give us the information we need to be confident about Parrot's stability on Tuesday. It doesn't take much time to put together a smolder report, and it's amazingly helpful to us.

Because of the feature freeze there is active development going on in some branches. I expect some of these to be merged in to trunk shortly after the 1.5.0 release. I'll post some information about a few of these tomorrow.

Lazy GC And Fixed-Size Allocation

So I've mentioned in an off-hand way recently about some of the small projects I've been working on in the Parrot GC. When I do talk about GC it's either on one of the two topics "fix a bug" or "make drastic improvements", but these that I have been working on recently are neither of those: they are small, incremental improvements that will provide only limited improvements.

When we look at performance in GC, we can make a number of simplifying assumptions that help to decrease the complexity of our algorithm. And in GC, algorithmic simplicity is key: no matter what changes you make internally to the GC, the number of data objects being allocated and managed will remain constant (unless other parts of the system severely optimize their own memory usage, which is necessary too). So too is the amount of work required per object: we must visit it at least once to determine if it is alive and to mark it, and visit things again in order to sweep them. So there isn't a whole lot of performance that we are going to eek out of this basic procedure. However, there are four things that we can really do to improve GC performance*:

1. Improve the efficiency of Allocation/Deallocation. We need to decrease the algorithmic complexity of an allocation, because it's a very common operation. Deallocations are (in theory) exactly as common as Allocations.
2. Linearize Allocation/Deallocation. If we can allocate items from a nice, large, fresh stretch of memory we can avoid needing to search for appropriate-sized chunks, or needing to copy/compact existing data.
   
3. Decrease the number of items needing to be marked and swept. We can't control how much junk the program generates, but we can control how often we mark/sweep all of it. This is done through heuristics such as generational GC algorithms which choose to mark/sweep a subset of all objects during a GC run, instead of all objects every time. This can also be done in an incremental core where we sweep a portion on each run.
   
4. Decrease the frequency of GC mark/sweep runs. This basically means means we increase our memory footprint, or increase collector latency. More data available to our program means we need to do less searching for free memory.
   

Parrot uses (in theory anyway) two types of aggregate objects: PMCs and STRINGs. All other types of data items that get allocated are attached in one way or another to these two types. When we allocate a PMC, we also need to allocate and initialize it's Attributes structure, which is a separate memory object. Currently this is done through an additional malloc() call, although in the auto_attrs branch, it is done using the new fixed-size allocator instead, which should be less expensive then normal malloc calls (#1). By allocating these items from our own managed pools and using a lazy technique to do it, we can improve allocator linearization (#2). By realizing that these fixed-size data items are always considered part of the PMC, We can simplify the marking and sweeping algorithm to ignore them completely and treat them as just an extension of the single PMC object (#3). And finally, by using the lazy allocator and increasing the initial size of our pools, we can decrease the number of GC runs that need to occur during startup, maybe eliminating them entirely (#4).

When Parrot allocates a new swath of memory for it's fixed-size allocator, it immediately iterates over the entire block, breaking it up into individual objects and adding them each to the free list. The loops used for this are very tight and efficient in terms of the number of machine instructions needed to operate them. However, we lose a lot of performance because of processor cache faults. Essentially we need to move the entire block, often piecemeal, into the processor's cache for no other purpose then to prove that it's there. What we can do instead is allocate the block and keep a pointer to the beginning of it only. When we need to allocate a new object, we first see if the free list is empty, and if so we allocate the next object from the most recent memory block. We're still iterating over the entire block, but we're only examining objects when we need to allocate and use them, keeping the vast majority out of the processor cache until they are needed.

Allocating a memory arena in Parrot right now, whether we use any of the objects in the arena or not, is O(n) complexity because we need to iterate over the entire arena and add all items to the free list at once. Increasing the size of the memory arena therefore increases allocation time more or less linearly, which offsets the gains we would make from requiring fewer GC runs. By using the lazy allocator instead, allocating a new arena is always O(1) no matter what the size of the arena is, allowing us to increase the size of the startup pools without cost, and decreasing the number of GC runs during startup without penalty.

It's not all roses and unicorns though, having to check both the free list and the pointer to the newly allocated block for every allocation increases complexity slightly, but that should be offset by better efficiency in terms of processor caching, so I think it will be a net win.

chromatic estimates, and I think I agree with it in theory, that we could see about a 10-15% improvement in the runtime of our test suite from these kinds of changes, once we add the necessary features and then tune all the values and sizes. If we could, for instance, increase startup memory pool size to be large enough so that we don't need to run GC at all for Rakudo startup, they would see some significant gains in the performance of their test suite too. Of course, that might turn Parrot into a huge memory hog, so we need to tread lightly and carefully tune our pool sizes. Also, it wouldn't hurt if we could find ways for things like PGE and Rakudo to allocate fewer objects, but that's a different topic altogether.

[* When I talk about "GC performance", I'm talking about a combination of throughput and latency. We want more of the first and less of the second. Basically, we want the GC to cause less of a slowdown for the user, and be able to turn over junk quickly.]