June 05, 2003

Anatomy of a design decision

Well, I just finally broke down, more or less, and changed one of the major rules for DOD behavior for Parrot, or at least set the groundwork for it. (DOD = Dead Object Detection, the phase of the cleanup procedures that look for objects that are unreferenced and kills them, which is separate from Garbage Collection, the process of reclaiming currently unused memory. More WTHI on those at a later point)

Now, we had originally set it so that Parrot had a tracing DOD system that was usually triggered on resource depletion. User programs could, if they chose, trigger off a DOD run, but that was about it. This, of course, clashes with Perl 5's system a bit. Perl 5 uses a refcounting scheme, which find garbage as soon as it becomes garbage. Most of the time, at least, as it never finds circular garbage, which is a bit of an issue. A refcounting scheme also does destroy things in order, a separate issue that we'll get to later. I wasn't that concerned with this, since for 99.5% of the collectable things a program uses it doesn't matter--there's no active destructor attached to it, so the only issue is the memory that it uses, a matter that's really for Parrot to deal with.

The things that do have active destructors, though, are the troublesome bit. The refcounting scheme that Perl 5 uses means that, if something is found to be dead, it's found close to immediately, usually on block exit when the lexicals are cleaned up. This provides a certain amount of immediacy that can be useful--filehandles get closed when they go out of scope, DBI statement handles that leave scope get destroyed, and so forth. While honestly very rare, they're very visible, and also very useful.

I wasn't, at the start, all that worried about it. The DOD sweep's pretty damn fast, and it happens with some frequency, so nothing lasts long past its death, and with the new features coming in, especially continuations, stuff will live past many folks expectations anyway. Delayed cleanup isn't a problem. If languages want more timely cleanup, they can force a DOD sweep when they clean up and exit from their blocks. The win of tossing refcounts (less code, fewer errors, denser data, less bookkeeping overhead) was far bigger than the loss of some determinism. Resource exhaustion, such as running out of filehandles, triggers a DOD sweep, so you won't die for lack of filehandles or suchlike things. We also have some features in the pipeline, such as being able to push block exit actions onto the stack, that would take care of many of the things people use this for anyway. (Since many of the things that really want timely destruction actually want to be executed on block exit, and use the timely destruction mechanism as a way to do that)

That didn't last, of course. (If it did I wouldn't be writing this) Perl 5 generally does timely destruction, on block boundaries, so code translated from 5 to 6 would need to force a DOD sweep on every block exit. We may be fast, but that's a lot of extra work. I've also been finding myself writing code that uses a fair number of DBI statement handles that I just don't clean up, and while I don't think they truly want lexical cleanup, they ought to get cleaned up faster than they are. And, finally, work's running me across a problem with perl 5, in that things that survive to global destruction don't get destroyed in any order, and that's been causing some headaches. That lack of ordering is what we're guaranteeing all the time, which is bad.

So, the compromise. Parrot now has a lazysweep opcode that triggers a DOD sweep, but only if there are objects that demand timely destruction. To go along with that, there's a "I demand timely destruction!" flag in the PMC structure, a counter in the interpreter structure, and a function to deal with them both. If a PMC is tagged as demanding timely destruction then the lazysweep op will trigger a DOD run (which recalculates the counter, so if they all die it stops) and if there aren't any, it doesn't. Languages that make some guarantees of determinancy can insert these as appropriate and, while not free, they are close to it.

The second part of the compromise is ordered destruction. While we haven't got this implemented yet, if a flag is set we'll build a quick tree of dead PMCs if there's more than one dead PMC with an active destructor, and destroy them in order from outside to inside. If there's only one dead PMC with an active destructor we don't bother building, since a single node tree takes no effort. (And because we clean up unused PMCs after any destructors are called)

Great? No. Adds unavoidable overhead (calculating the timely destruction count on a DOD sweep), which I don't like. It can be reduced to a simple test in simple cases (those with no timely active destructors) but I'm not sure that will happen too often in real life. On the other hand, it does provide some guarantees, which people like, and which do make programming a bit simpler, so, well, there we go. The point is to make this all work right as cheaply as reasonable, so we deal. Guaranteed invariants cost, but there's no real way around that. At least the cost will be trivial for languages that don't need it, which is something at least.

Posted by Dan at June 5, 2003 08:57 AM | TrackBack (0)