Programming, Software and Code

GC Next Steps

15 May 2009
legacy  —  GC  —  Parrot
The GC is properly encapsulated now, at least for the most part, and now it's time to move on to the next steps in the process. Encapsulation of an interface is one thing, having the interface be usable and even elegant is something else entirely. Parrot's current GC API isn't really either of those things: It is specifically tailored to the current stop-the-world GC and is far from being an elegant solution. Before we can know what we want the interface to look like ideally, we need to know where we intend to go with the GC in the long term. I've already talked about a few things, but I think it's worthwhile now to recapitulate on a few of them:
  1. Incremental Behavior. The GC as it is right now does the whole shibang at once. It marks everything, from the most global root down to the most insignificant property, and then it sweeps everything. This can cause distinct pauses in Parrot's execution that the user might become aware of. Instead of doing everything at once, we can try to break it up. Do small bits here and there until the whole job is done. In this case, we're still blocking for the same amount of total time, but it's spread out and therefore less noticable. Being able to stop and restart the sweep is going to require a tricolor marking scheme (in the most simple case).
  2. Asynchronous sweep. Once we have the set of all PMCs marked and clearly demarcated as being either alive or dead, there is no reason why we should have to wait for the sweep to run synchronously. The sweep could be contained in a separate thread (OS thread, not Parrot thread) and run asynchronously. After all, once something has been marked as "dead" we don't need to worry that it would suddenly come back to life while we are sweeping. We do need to worry that newly-created objects are created as being alive so they don't get swept as soon as they are created, but that's a small issue.
  3. Generational Behavior. By separating out PMCs into multiple generations based on longevity, we can intelligently choose to avoid sweeping PMCs that are not likely to be dead. This helps the GC sweep to take less total time because we are sweeping fewer things. The downside is that there are false positives with this method, a PMC that is not alive may not be swept in a timely manner. We would likely need to use some form of hackery to make sure PMCs that needed timely destruction did not end up in an older generation.
  4. Copying/Compacting Behavior. We want to be able to keep our memory tidy, and be able to return unused resources to the OS in an organized and timely way. The method for doing this is to use copying/compacting collector. Objects that are marked as being alive can be moved to a single location, freeing up space elsewhere in the pool.
  5. Ordered Destruction. With ordered destruction we make sure that a PMC is only freed after all the PMCs that it relies on are freed. We would need a way to specify these kinds of reliance relationships, and then we need to be able to adhere to them.

It's worth pointing out here that not all of these features are going to be implemented in every core. Some cores are going to be incremental. Some are going to be generational. Some are going to be copying/compacting. Some are going to combine two or more of these attributes. It's also worth noting that once we make a guarantee of ordered destruction, all cores are going to have to subscribe to that. It's a feature where once we have it things are going to start relying on it.

These ideas on the table, we need to think about some ways that the GC API is going to need to change to support them in the future. Here are some ideas that I have:

  1. We have a function Parrot_gc_mark_and_sweep that performs a stop-the-world run. We should probably break this up into Parrot_gc_do_mark() and Parrot_gc_do_sweep. This will enable us to support collectors that do things like asynchronous sweeping where the mark and the sweep are handled in very different ways at different times. It will also help to streamline and consolidate places where we need to check the mark and sweep block levels.
  2. The function Parrot_gc_mark_and_sweep (or the separate Parrot_gc_do_mark and Parrot_gc_do_sweep) are not really well-suited for incremental usage. They get called from places that expect results, such as in the PMC allocator when there are no more headers available so we run the gc to try and free some up. If the GC is incremental, we will only run an increment when we are in need of new headers, and we will end up allocating lots of new arenas by the time we finally get around to sweeping all our accumulated dead. If we have an incremental version of this function (which non-incremental cores can simply choose not to implement), we can call that from places like inside the concurrency scheduler that happen more frequently.
  3. I'm thinking about an interface where we can "store" PMCs that aren't really being used currently. So we would call Parrot_gc_checkin_header(), which will store the header internally, possibly allowing it to be moved/copied/compacted, and will return an integer receipt. Later, we could pass that integer receipt to a function like Parrot_gc_checkout_header() to return a pointer to the PMC where it is now. Another idea would be to use a single function like Parrot_gc_relocate_header() that would take a pointer to a PMC and return a new pointer to the same structure that may have been moved in memory. This could be used to explicitly compact a PMC when we know that there is only one reference to it in existance (so a PMC could call it on its internal members on VTABLE_mark for instance, or we could extend Parrot_gc_mark_PObj_alive to take an extra boolean flag that says whether the PMC is known safe to move or not. Lots of possibilities here, but it would provide us a way to smoothly transition Parrot to a copying/compacting GC scheme.


There are lots more ideas that I have (and will talk about at length) concerning the GC, and I'd love to hear any other opinions or ideas that other people have about it as well. Maybe, if I can find the time I will try to get started working on it some more soon.

This entry was originally posted on Blogger and was automatically converted. There may be some broken links and other errors due to the conversion. Please let me know about any serious problems.