GSoC Idea: Implement a new GC

Blah Blah Blah Parrot needs a new GC. Blah Blah the current GC is lousy Blah Blah.

I've said it all before. At length. Ad nausea. Hell, I even attempted this same GSoC project myself two years ago.

The garbage collector is one of those systems that absolutely effects almost every aspect of Parrot's operation and performance. A bad GC means a slow, obnoxious VM with pauses and huge memory consumption. Of course, there is no one single "best" GC algorithm to use that provides optimal behavior to all classes of programs. This is why Parrot was designed to have a pluggable GC system where the most pertinent GC from among multiple options can be selected.

At least, that's the theory.

Parrot really only has one GC right now and it's a very simplistic Mark and Sweep collector with some less-than-desirable properties. bacek has been making good progress on porting the Boehm GC to Parrot, but that has it's drawbacks as well (though drawbacks are being mitigated). What we need is more people working on it, more people trying new things, and more eyes on the code.

So what kinds of GC could Parrot use? The projects page on the wiki describes three types that Parrot is specifically interested in:

1. Generational
2. Incremental
3. Concurrent

These adjectives are not orthogonal, you could easily have an incremental-concurrent collector, or a generational-incremental collector, or even a generational-incremental-concurrect collector. But, these three things tend to have nice properties.

Generational collectors tend to have nice throughput because we subdivide the memory space and only take the time to mark and sweep a subset. Incremental collectors break the mark and sweep phases up into smaller increments which in turn decrease pause times. Concurrent collectors utilize multiprocessor systems to operate the GC in parallel with the program code and therefore experience no pauses and high throughput (but lousy performance on single-processor systems, or multiprocessor systems with many other running processes).

The aspiring GSoC student working on GC will benefit from two years of hard cleanup and refactoring work from myself and other contributors. Plus, there is strong community support to get a new GC up and running as quickly as possible to replace our current one. It's a project that will be tough no matter what, but where there are huge gains to be made for the Parrot community and a large amount of available support.

As I mentioned above, the GC system is supposed to be pluggable. So in reality you don't need to implement a great GC that will solve all our problems, you just need to implement any GC to prove that the system is, indeed, pluggable. If the GC you implement has some nice properties that's just a nice bonus.

Boehm in Parrot

It's a project I've talked about before, but not one that I took the time to actually work on: Getting the Boehm-Demers-Weiser GC ("Boehm GC" for short) in Parrot. Recently, prolific Parrot hacker Bacek did just that, creating a new branch to add Boehm as a new GC core in Parrot. It hasn't been merged into trunk just yet, pending some changes to the configuration system.

On one hand it's exciting--very exciting--to have a real production-quality GC core in Parrot. On the other hand, performance is horrible with the Boehm collector. Well, maybe not "horrible", but worse than we have now. Despite the high quality of the Boehm collector and the hard work of Bacek, the new core may prove to be little more than a carnival oddity because of poor performance. The big question to ask first is "Why does Boehm perform so slowly in Parrot?", perhaps followed by "...and is there anything we can do to speed it up?". I won't really tackle the second question here, it's far too big for a single blog post.

I've given a brief overview of GC concepts in the past, but I didn't really cover all aspects of GCs. There isn't enough room in a single blog post to do it (although I am hearing very good reviews about a new book about Garbage Collection that might be able to cover things in more detail). One aspect of GCs that I did not mention in my previous post is conservativeness.

Memory gets broken into regions that we will call "spaces". Spaces can be used for all sorts of things and most programmers will already be familiar with them: stack space, heap space, program space, etc. We know that in our running program all PMCs are allocated in heap space, and are referenced from both heap space (pointers contained in PMCs to other PMCs) and in stack space (PMCs being actively used by C code. If we need to find and follow all pointers to PMCs, as we do in the GC mark phase, we can accomplish this by traversing the stack and heap spaces linearly and following every value that looks like a pointer to heap space.

The problem with a linear memory traversal is that you do it blind: you do not know whether any given value is a valid pointer or not. You can only assume that any value you encounter which--when treated as a pointer--points into heap space, you just assume that it's a pointer. This behavior creates lots of false positives, because values that are not pointers are treated like pointers and followed like pointers. We call this behavior conservative. A Conservative GC, like the Boehm collector, is completely disconnected from the operations of the program, and so must blindly traverse the heap and stack space following all pointer-esque values, whether they are actually pointers or not.

The alternative type is a precise GC, which knows where pointers are beforehand and never has false positives. A precise GC can avoid scanning large regions of memory that are guaranteed to not contain any pointers. It can also avoid scanning numbers that happen to look like pointers into heap space, because it knows which fields are numbers and which are really pointers. Precise GCs are almost always faster than their conservative counterparts, though they require significantly more integration into the rest of the program. This creates both an encapsulation problem and requires ongoing maintenance of the GC's algorithms as program data structure formats change. The GC has access to more information, but the program now has the responsibility to ensure all that information is consistently used and remains accurate.

Parrot's current GC is precise. At least, it attempts to be. Each PMC type defines a "VTABLE_mark()" routine, which can be used to mark the PMC and all the pointers that it contains. Each PMC type knows exactly where it's pointers are, so it can focus it's efforts only marking things that actually need marking. Where Parrot's GC fails to be precise is in the stack-walking code. I've complained about that before and won't really rehash it here. Suffice it to say that if Parrot got cleaned up to avoid unanchored PMCs on the stack and therefore to not need to stackwalk for a GC run, it could provide a nice performance improvement.

But, I digress. The Boehm collector is a stand-alone module that obviously has no intimate knowledge of the internal workings of Parrot. Boehm doesn't know some of the intentional simplifications that Parrot uses to keep track of it's PMCs and to keep them efficient for use in the GC. Let's look at some C code:

int * x = (int *)malloc(sizeof(int) * 32);
int * y = &(x[16]);
int * z = &(x[32]);

In this code snippet we see our aggregate object x, and a pointer y which points to a memory location inside x. When Boehm does a stackwalk here, it sees the value y, determines that it's a pointer into heap space, and then must trace backwards from there to find the start of the aggregate object x. Boehm must then compare the size of x to the distance from there to y to ensure that the pointer y is actually located inside x. Next we find the value of z, which points outside the allocated buffer of x. I don't know why you would intentionally write the code above, but that's hardly the point. Boehm sees that z points into heap space, traces back until it finds x, determines the size of x and then sees that z points outside of it. That's quite a lot of work to mark pointers, but it's necessary when you consider that normal arbitrary C code can create pointers to normal arbitrary locations inside a structure or array. Boehm needs to be very conservative in order to be usable by a wide array of software, much of which won't have the same design for memory objects or access that Parrot has.

So back to the question at hand: Why is Boehm so slow on Parrot? The answer is that the Boehm GC is a high-quality tool that needs to be general enough for adaptation to a wide array of programs. It sacrifices intimate knowledge of Parrot's internals (which it can use to focus and optimize it's behavior) in exchange for improved generality. On the other hand Parrot's current GC, while naive, does have this intimate knowledge that it can use to improve performance. If we know where all the pointers are ahead of time, we can avoid all the effort of having to search for them.

GC Gets Kick Start

Parrot's garbage collector is starting to really get a lions share of developer attention recently, especially after some very interesting benchmark statistics from chromatic went public. For the benchmark of building the new NQP-RX project, a whopping 80% of execution time is spend in the GC mark phase. Actually, the real statistic is that 80% of the execution time was spend only in the Capture PMC's mark routine (and the functions that it calls). That's quite a huge amount of time, even for a naive GC like ours to spend.

Let's take a quick recap about GCs, and what causes them to be so expensive: GC is used to find and automatically reclaim unused data items so that the storage space can be reused. A good GC system means that the system programmer does not need to manually free memory when it is done being used: The GC will detect and automatically deallocate the unused memory. A good GC system, in essence, will completely eliminate memory leaks, and help to make the codebase much more clean and succinct. To do this, GC needs to first find all unused ("dead") objects and then free them, two phases known as mark and sweep.

In a naive implementation of a mark and sweep algorithm, there are two aptly named phases: mark and sweep. The mark phase is charged with finding dead objects to reclaim. We typically do this in a reverse order, by first finding all objects that are in current use ("alive"), and then declaring all other objects to be reclaimable (or already free). Starting from a root set, such as the register sets and interpreter globals in Parrot, we can construct a graph of all objects by following pointers and marking each reached object as alive. It stands to reason that if there is no pointer to a particular object, it cannot be accessed, and anything that we do not access during the mark is presumed unreachable, which is the same as dead.

In the sweep phase, we must iterate over the pool of all objects, finding objects marked dead and freeing them. Freeing an object typically involves calling a custom destructor if one is provided, and making the memory available to the allocator so the memory can be reused the next time an allocation is made.

In every mark and sweep GC collection run for a naive collector, we must first trace the entire memory graph and then iterate over the entire object pool. This is very expensive, and the expense grows large as the memory use of the program grows large. What we need for Parrot is something a little bit less naive.

What we probably can not do is make huge conceptual improvements to the idea of mark and sweep: We will always need to detect alive objects, and we will always need to traverse and free the dead ones. The general idea is sound and that's not something we want to change. What we can do, however, is to impose heuristics on the system to decrease the number of items to mark and decrease the number of objects to sweep. This is where the bulk of GC performance improvements can be made, by being much smarter about how the GC is used.

Allison sent a nice email to the list the other day essentially saying that GC has become an officially-recognized pain point and that we as a team are going to be looking at improvements after 2.0 (if we don't manage to start before that). Very interesting discussion has already started on ways to improve it.

As I mentioned above, the bulk of GC performance improvements are made by applying heuristics to decrease the number of objects to mark and sweep. A secondary set of improvements can then be made, often at the code level, to make the GC's operations run faster. I'll call the first set of improvements "algorithmic", and the second set "implementation". So what we the Parrot developers need to do first is pick the right algorithms to use and then implement and optimize them.

Here is a general list of things we can do to improve GC performance in Parrot:

1. Allocate fewer GCable objects. This is typically the result of user-level code optimization. So, Parrot needs optimizers that are GC-sympathetic. Parrot also allocates a number of STRINGs and PMCs for internal purposes, so we need to minimize that.
2. Mark fewer objects. This comes from a good generational GC system where we segregate items based on how stable they are.
3. Sweep fewer objects. I think chromatic's linked-list idea will help us significantly in this regard.

What I think we are leaning towards in Parrot is a system called a generational GC. A generational system uses the heuristic that items which have lived for a long time without being GC collected will tend to stay alive longer, and items which are recently allocated tend to die quickly. It's an acknowledgement that a lot of garbage is created for very short-term uses, and relatively few things stand the test of time. Here's a quick example using explicitly non-idiomatic Perl 5:

my @array = fill_array(100); # 100 items in the array
foreach my $item (@array) {
my $new_item = mangle($item);
say $new_item;
}

In this loop we create a lot of garbage. Every new instance of $new_item is a new collectible item which can be declared dead at the bottom of the loop and allocated anew at the top. Also, all the local variables used inside the mangle function follow the same life cycle. The only items that survive through the entire snippet are @array and it's contents.

Every time we mark, we have to mark @array and all it's contents, even though they are long-lived and will survive the entire loop. Every time we sweep we need to separate dead items $new_item and all the local variables created inside mangle() from @array and its persistently live set.

Generational GC works by saying that @array is long-lived and putting it into an older generation. Older generations contain objects which are, by definition, older and therefore less likely to die. If we aren't worried about the item dieing, then we don't need to explicitly mark it. At least, we don't need to mark it as often. We also don't need to sweep it, if we can find a good fast way to avoid that.

Fixed-Size Allocator: Now With Extra Working!

A few days ago I toggled the flag to disable the fixed-size allocator. I was receiving too many bug reports that I wasn't able to debug adequately, and I heard that it wasn't working at all on Win32. So we shut it down in hopes that we could find a fix eventually. Well, today I found and committed the fix.

NotFound mentioned out of the blue today that the fixed-size allocator was working on Linux, both 32- and 64-bit flavors. This was news to me, last I had heard it was malfunctioning on those platforms. However this news was quickly confirmed by darbelo too, and then I did it myself. Worked perfectly. So I crossed my fingers and tried on Win32 as well: Nothing. Segfault during miniparrot and the build stopped. I don't have GDB on my windows machine (it's actually my work computer, so it's use is limited). I do have Visual Studio, but I've yet to find a real way to debug a program in VS that I didn't build in VS, especially if it's a native-code executable. In lieu of real debugging tools, I used the "printf" method to try and narrow down where and when the segfault was happening. Here's the function that was causing problems, can you spot the error?

PARROT_CANNOT_RETURN_NULL
PMC_Attribute_Pool *
Parrot_gc_get_attribute_pool(PARROT_INTERP, size_t attrib_size)
{
   ASSERT_ARGS(Parrot_gc_get_attribute_pool)
   Arenas * const arenas = interp->arena_base;
   PMC_Attribute_Pool ** pools = arenas->attrib_pools;
   const size_t size = (attrib_size < sizeof (void *))?(sizeof (void *)):(attrib_size);
   const size_t idx  = size - sizeof (void *);

   if (pools == NULL) {
       const size_t total_length = idx + GC_ATTRIB_POOLS_HEADROOM;
       const size_t total_size   = (total_length + 1) * sizeof (void *);
       /* Allocate more then we strictly need, hoping that we can reduce the
          number of resizes. 8 is just an arbitrary number */
       pools = (PMC_Attribute_Pool **)mem_internal_allocate(total_size);
       memset(pools, 0, total_size);
       arenas->attrib_pools = pools;
       arenas->num_attribs = total_length;
   }
   if (arenas->num_attribs <= idx) {
       const size_t total_length = idx + GC_ATTRIB_POOLS_HEADROOM;
       const size_t total_size   = total_length * sizeof (void *);
       const size_t current_size = arenas->num_attribs;
       const size_t diff         = total_length - current_size;

       pools = (PMC_Attribute_Pool **)mem_internal_realloc(pools, total_size);
       memset(pools + current_size, 0, diff * sizeof (void *));
       arenas->attrib_pools = pools;
       arenas->num_attribs = total_length;
   }
   if (pools[idx] == NULL)
       pools[idx] = Parrot_gc_create_attrib_pool(interp, size);
   return pools[idx];
}

We keep an array of pool structures ("pools"), where each index into that array represents the size of the object managed by that pool. The smallest object we can allocate is a single pointer, because we link objects together into a linked list, so we need at least enough space for one pointer to handle that. We also want indexing for the smallest items (sizeof(void*)) to start at slot zero in the pools array to save space. To get this effect, we first calculate the minimum necessary size of the object, and then we subtract the sizeof(void*) from that to give us the index into the pools array. This part works just swell.

We then have two large logic blocks. The first determines whether we have allocated any pools at all, and if not first allocates space for the pools array. The second block determines if we have too few slots allocated, in which case the array is resized to accommodate our incoming request. We then check to see if the current slot is null, and allocate a new pool in that slot if it is. Finally we return the pool in the given slot.

The problem, I soon found out, was that for some specific sizes we were returning bad pointers. See the problem yet? Let's zoom in a little:

const size_t total_length = idx + GC_ATTRIB_POOLS_HEADROOM;
const size_t total_size   = total_length * sizeof (void *);
/* Allocate more then we strictly need, hoping that we can reduce the
  number of resizes. 8 is just an arbitrary number */
pools = (PMC_Attribute_Pool **)mem_internal_allocate(total_size);
memset(pools, 0, total_size);
arenas->num_attribs = total_length;

This is part of the logic for allocating a fresh pools array. GC_ATTRIB_POOLS_HEADROOM is a buffering factor I added. It's #define'd to be 8, which means that when we do allocate we make space for 8 sizes more then we currently need. This prevents us from needing to resize the array if we need to allocate an object that is only a little bit bigger (and we know that we will almost always need to allocate something that's just a little bigger).

Taking the index (idx) of the slot, we calculate the size of the array, allocate it, then initialize it all to zero. Except we don't. In the first run through if idx is 0 then total_length is 8 and total_size is 64. This means we're allocating enough space for 8 pointers, not one pointer plus a headroom of 8 additional pointers. Because the idx is zero-based, my math here was off by one. To see it better, consider if GC_ATTRIB_POOLS_HEADROOM was omitted entirely. Then idx would be 0, total_length would be 0, and total_size would be 0. Try passing that to malloc and see how well it works for you.

So I changed the calculation for total_size to:

const size_t total_size   = (total_length + 1) * sizeof (void *);

And Parrot magically started building on Win32. A few more small cleanups and I committed r40962.

I still need to do some benchmarking though, I'll try to do that tonight. I hope that this will bring some measurable performance improvements to Parrot.

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.

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.]

ParrotTheory: Garbage Collection

So I've talked a lot about garbage collection on my blog before, and I think now is the time to really go in depth about some of the theory behind them. Garbage Collection is a subset of a larger field of study on Memory Management. In fact, much of the functionality in the Parrot GC system is only concerned with memory management, not the actual detection and collection of garbage.

When we look at a non-garbage-collected program, memory is typically allocated from the operating system with malloc and variants, and is returned to the OS with free. This is fine for tiny little programs, but as complexity increases you can start experiencing memory leak problems, and you end up spending more and more and more effort allocating memory, checking if memory is unused, and returning it to the OS manually. In short, it's not a system that scales well.

Enter Garbage Collection. GC is a system in your program that automatically handles memory allocation and dealloction. It does this by detecting when allocated memory is not being used any more and frees it or recycles it automatically. There are two basic types of Garbage Collection: Cooperative and Non-Cooperative.

Cooperative GC

Cooperative GC, more commonly known as "reference counting" is a form of GC where the entire program needs to participate in the GC algorithm in order for it to work correctly. In a cooperative GC system, every time a pointer to an object is made, the reference count needs to be increased. Every time a pointer is deleted or redirected, the reference count needs to be decreased. When the reference count for a particular object reaches 0, nothing points to it and it can be automatically and immediately freed. Cooperative GC can be done more easily through the use of macros:

#define ADD_REFERENCE(obj, newref) do {\
 obj->refcount++; \
 newref = obj; \
} while(0);

#define REMOVE_REFERECE(obj)  do {\
 obj->refcount--; \
 if(obj->refcount = 0) \
 free_my_object(obj);\
} while(0); 

So that's not such a huge problem and all the code fits into these two little macros. The problem is remembering to faithfully use these macros for every single pointer access throughout the entire program. Notice that, especially for concurrent systems this really needs to be every single access, because another thread could be decreasing the refcount at the same time that you are using it, and free it out from under you.

Non-Cooperative GC

The other form of GC, and the type that Parrot uses, is a non-cooperative GC. In a non-cooperative system, the GC module is completely separate, and the rest of the program does not even need to be aware of it's existence. In the Boehm-Demer-Weiser Collector, for example, the only change that needs to be made to the program is to replace calls to malloc/free with the allocation/deallocation functions, and everything else proceeds like normal with garbage collection happening invisibly in the background. The benefit to this system is that you write a single GC system, and then can write normal code throughout the rest of your program without ever having to remember to reference your data again.

Non-cooperative collectors typically work in two stages: mark and sweep. In the mark phase, the collector walks the stack and the heap looking for pointers to data. Every data item has an associated flag, and when we find a pointer to that item we mark the flag with a special "Alive" value. We then look through that data item for other pointers to follow and mark. The collector starts at a root set of data pointers that we know we can reach (current processor register contents, current stack contents, global variables, etc) and then trace through memory like a large graph. In the sweep phase, we iterate over data items in the heap and look for all data items which have not been marked. Anything that is not marked is not reachable, and can be freed.

I don't want to do a huge compare/contrast of the two GC types, they both have pros and cons. Perl5 uses Cooperative GC, while Parrot (and therefore Rakudo Perl 6) uses Non-Cooperative GC instead. The only real differences are where and when objsects are detected to be dead. For the rest of this post I'll just focus on non-cooperative systems because that's what Parrot uses.

Non-cooperative GC tends to run all at once, such as when a new allocation is requested from the program. The GC will look for some available memory and i none is found it will mark then sweep memory to try and free some up. The mark and sweep algorithm could be expensive and this will cause a system slow-down or even a complete pause while it is running. The basic mark and sweep algorithm is notorous for these pauses. Luckily a number of new algorithms have been developed over the years to help mitigate their effects.

Algorithms

In an Incremental GC, we break GC runs up into pieces. We do a subsection of the entire algorithm each time, with the intention that we still have pauses, but the pauses are each shorter and more spread out. Incremental GCs are typically implemented using a tri-color mark: Instead of a memory object being marked "alive" or "dead", we use three colors: "black", "grey", and "white". White objects are completely not marked ("dead"). Grey objects are marked, but their children are not marked. Children in this case are pointers in one memory object that point to other memory objects. Black objects are completely marked including all their children. By keeping track of the state of objects and the the states of their children we can pause at almost any time and resume by taking the list of all grey objects and continuing the mark from there. Incremental GC helps to spread the pauses out, but doesn't really do anything to fundamentally decrease the amount of time that's needed to pause over long execution runs.

In a Generational GC, we use the heuristic that most memory objects are generated, used, and abandoned very rapidly. Think about temporary variables in a tight loop, for instance. So we only perform GC mark and sweep on certain groups of memory objects, called generations. Memory objects are allocated into the "young" generation, which is processed by the GC very frequently. Objects that survive a sweep can be graduated into an older generation which is swept less frequently. This algorithmic change means less pause time for the GC (because not all memory is being marked and swept). However, dead objects in the older generations won't be found and freed as often, resulting in longer delays for some objects to be destroyed (think closure of a file handle when it's containing scope exits), and more memory footprint needed to hold these dead objects.

Concurrent GC makes use of system-level parallelism to perform aspects of the GC algorithm in separate threads, which negates pauses entirely. Actually this isn't entirely true, in a system where there are more running threads then there are hardware processors to execute them we still have pauses in the form of thread context switches. Concurrent GC has the benefit that we can really run any algorithm we want regardless of execution time or complexity, so long as it runs in another thread, without any additional performance penalty. In a concurrent system, however, there is typically a need for significant synchronization, plus the overhead inherent in executing separate threads (which is more expensive on some systems then in others).

A basic mark and sweep algorithm has another problem of memory fragmentation. We allocate memory linearly in memory, but start to deallocate it randomly, leaving large odd-shaped holes in memory between live data. The allocator runs quickly at first, but as fragmentation increases, it becomes more complicated to find suitable holes in memory for new allocations to be made from. To avoid this problem, we can use a special GC algorithm called a compacting or copying collector. A compacting collector actually moves data in memory to keep fragmentation down. If we think of memory as a long chain, we move objects to the front of the chain, forming a "dense prefix" where live data tends to be, and a sparsely-populated area at the end of the chain where there are few if any live data items and therefore the allocator can execute more quickly. We can then focus our mark and sweep efforts on the dense prefix because that's where all the data items are.

In a region-based memory system, we break memory up into chunks called "regions", and associate each region with an executing context. When the context exits (such as through a subroutine return) we can free the entire region at once. A freed region can then be used by the allocator to quickly allocate memory linearly.

These various algorithms aren't atomic, we can mix and match features from each to suit individual needs. For example, Java's new Garbage First collector uses a compacting region-based collector that focuses it's attentions on sparsely-populated regions to clear garbage out of the way of the allocator. This gives Java good linear allocation performance while also decreasing the number of long pauses the collector needs to run.

Overview

Garbage collection methods and algorithms are a trade off of several components: memory footprint, throughput, and latency. Memory footprint relates to how aggressive the GC is. If it is very aggressive and always frees dead objects quickly, it will use the least amount of memory. Throughput involves the overall speed of the GC in a long-running application. The GC should be able to process a lot of data quickly. Latency is the amount of pause time necessary for a GC run, we want to minimize this. The general rule of thumb is that you can maximize two of these requirements at the expense of the third.

If we are running a GUI application such as a videogame, we want to decrease latency because pauses for a GUI application are unacceptable. We may also want to maximize throughput because those kinds of applications churn through a lot of memory for all it's physics and graphics calculations. If we are running a background service process, we may want to keep memory footprint low, but may not care at all about latency. A web server application may want high throughput and low latency, but will be allowed to hog extra memory.

So that's garbage collection in a nutshell. I can always go more in-depth about any topics that people are more interested in.

Fixed-Size Allocations For Parrot

Parrot has a dirty little secret. Actually, it's not much of a secret because I've mentioned it on my blog here before (although I can't find link right now). The problem is that Parrot, despite the fact that it has an integrated GC mechanism, still relies on malloc/free for most of it's allocations. The only things that aren't allocated this way are the "PObjs": PMC, and STRING structures mostly. However, just about every single PMC allocation involves a malloc anyway to allocate the structure of attribute storage used by that PMC. These structures are typically allocated manually using malloc in the PMC init VTABLE, and manually deallocated in the destroy VTABLE.

In TT #895 NotFound started working on a task that I've been thinking of for a while: Fix the GC so it could automatically allocate and deallocate these attributes structures, to help prevent the myriad of memory leak problems that have arisen from their misuse. Plus, we can get rid of a lot of unnecessary code if we do all the allocations in one place. His idea is to store the necessary size of the attributes structure in the VTABLE structure, and then use that information in the GC to automatically allocate and deallocate these structres. We would allocate the storage directly before the init VTABLE was called, and deallocate the storage directly after the destroy VTABLE was called. Plus, we can flag certain PMC types that use this mechanism, so the transition can be gradual and pain-free. Quite a good plan!

Now I read over that ticket and thought to myself "Self, this would be the perfect opportunity to remove malloc/free from the picture", and so it is! By having all the allocations and deallocations happen in one place, it's painfully easy to abstract that away behind a new GC interface and implement our own fixed-size structure allocator. Last night, this is exactly what I did and Parrot now has an (experimental) fixed-size allocator that's designed to replace many instances of malloc/free not only in the PMC management routines, but also in many other places throughout Parrot. The only requirements that my allocator has that malloc/free doesn't is that you must specify the object size when you free it, and you can't currently resize the buffer once you've allocated it (at least not easily). The new fixed-size allocator isn't currently used anywhere in Parrot, but it's available for testing and should be able to be used in many places on an experimental basis.

The new fixed-size allocator is very simple, and is based in part on our existing PObj allocation routines. We maintain an array of pointers to pools. Each pool contains a linked list of arenas. Each arena contains a large storage space devoted to holding objects of a fixed size. All items in the pool that are free are organized into a linked list called the "free list". When we need a new object of that size, we either take the item on the top of the free list, or else we allocate a new arena, add all the new items to the free list, and then take the item on the top of the free list. On deallocation, we take the deallocated item and simply push it back onto the top of the list.

Using the new allocator is very easy: To allocate a new attributes structure for a PMC, use the new Parrot_gc_allocate_pmc_attributes function. To free it again, use Parrot_gc_free_pmc_attributes instead. Likewise, to allocate a new arbitrary data structure, use Parrot_gc_allocate_fixed_size_storage and Parrot_gc_free_fixed_size_storage. If you're interested to see how Parrot's memory allocation works in general, these functions and the supporting functions that they call are very instructive.

Parrot's interpreter structure maintains an array of pointers to the fixed-sized pools, and the array is resized to support larger allocations. This system works well for small-sized allocations, but does not work well for large allocations. There are some things I think I can do to improve it's efficiency for larger-sized allocations as well, but in general I think it's good right now to limit this mechanism to small structures (as opposed to large buffers).

The GC doesn't do any kind of management for these items, it simply allocates and deallocates them in a very simple manner. It does not compact them, and does not free unused arenas back to the system like it probably should. Of course the primary GC core doesn't do this either with it's PObj storage spaces, so I don't feel so bad. When we finally get Parrot fixed up to support a compacting garbage collector for the PObj stuff, we should also be able to make the fixed-size storage use the same mechanism.

So we've got a new tool to play with in Parrot's memory management toolbox, and I hope that we like it and decide to keep it around for a while. There are plenty of ways to improve this new allocator, make it more efficient, and tune it to behave properly for Parrot's needs. However, I think we're going to see immediate improvements over malloc/free, and I'll start posting benchmark numbers as I get them.

Concurrent Garbage Collection

I mentioned in passing a few posts ago that cotto sent me a link to a paper about a concurrent garbage collector VCGC. eternaleye sent me another paper that proposed improvements to the VCGC algorithm, while following the same general concept. The second one is called MCGC. I read over those two quite enthusiastically, and then moved on to read a paper about G1, the new Java VM garbage collector. There are some similarities between the two approaches, but plenty of differences too. In the end I think a collector somewhere in this family is going to be the GC of choice for Parrot (at least, for birds built on multithreaded systems). Of course, it may be just one of a possibly large stable of collectors, each suited for different needs.

The first paper introduces the "Very Concurrent GC" (VCGC) which is able to use a multithreaded approach without the need for fine-grained thread synchronization. "Balderdash!" I can hear you saying, but have faith: I've read the paper and the algorithm is so beautiful in it's simplicity that I can't believe I didn't think of it first. And it's very plausible. Here's the gist of it: Each memory allocation round has a color. We allocate memory with color x and operate like normal until we hit a synchronization point. At the synchronization point, we increase x++. All memory allocated before the synchronization point now has color x-1, and all memory allocated thereafter will have a color of x. We continue executing again until the next synchronization point, and then we bump x up again. Memory allocated in the first window now have color x-2, Memory allocated in the second window now have color x-1, etc. All memory chunks with color x-2 are swept and reclaimed to the system.

In this system, memory blocks implicitly change color because we change what the color numbers mean at each synchronization point. Without proactive marking, the blocks "fall off" the end of the window and get collected by a collection thread. The collection thread has no other job then to iterate over the allocation space and free all memory with color x-2. We call this thread the "Sweeper". Saving chunks from certain doom is the job of the "Marker", a thread that is the only thread in the system capable of changing the color of a block. The Marker runs a normal GC mark algorithm, starting at the root set and bumping all memory that's reachable to color x. The point when both the Marker thread and the Sweeper thread have completed their current run is called the synchronization point, which is when we increment x (called the "epoch") and restart both threads to run again. It's simple and low-overhead because it doesn't require any moving or compacting, and it only has to twiddle a handful of bits to make everything work. Also, it appears to scale well to multicore systems and multithreaded programs.

G1 is a very interesting collector which I find is conceptually not entirely dissimilar from VCGC, although I'm probably minimizing the differences in my own mind. It seems to be based on more of a lazy approach, picking low-hanging fruit to reduce the need for complete end-to-end GC runs and making allocation more efficient. G1 divides the heap into regions, and focuses on regions where there are the fewest active blocks. In the region, G1 frees any garbage it finds and copies any live items to a "dense prefix" somewhere else. This allows the entire region to be used by the allocator for easy linear allocations.

G1 appears to be very heterogenous in that memory of all sizes is allocated from a single pool. In that sense, a G1-like collector may be suitable for use with our STRING system, which is badly in need of performance tuning. Something like VCGC would probably be more useful for the common case of homogenous header pools, like our PMC pools and our sized pools, which facilitate very rapid array indexing through the pool.

VCGC and variants suffer from a few worst-case scenarios, such as situations where garbage is very long-lived (thus wasting time where the sweeper repeatedly checks things that are not garbage) and situations where garbage is very short-lived (where blocks become garbage quickly, and need to wait for two epochs to be swept, which increases memory consumption). The benefit of course is simplicity in the algorithm. Adding complexity, such as in MCGC, can reduce these problems.

My plan in the near future, probably after the AIO project, is to start prototyping a new concurrent collector core modeled on VCGC. I will use a simple and direct implementation of it initially, no bells or whistles or fancy-schmance optimizations. Once we have a basic concurrent core installed and working properly, it will be easier to add these kinds of optimizations in an incremental fashion.

And I have plenty of potential optimizations in mind, including some simple tweaks to the basic algorithm that I think will add some time-saving generational semantics. If you have some ideas too, I would love to hear them. I may create a planning page on the wiki soon to start putting ideas together for this.

What's really most important at this point, and pmichaud mentioned this several times at YAPC::NA, was just getting a second core working. We don't even care what core it is, we just need a second one to prove that our architecture is pluggable and work out any kinks in the API. Once we have a second core in place, it will be that much easier to add a third and a fourth, etc. With all this in mind, we really don't need to be swinging for the fences right now, just looking to add something quick that maybe offers some small performance benefit over the current system.

GC Next Steps

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.

Parrot GC Refactor work

I spent a lot of time yesterday and this morning working on the GC API refactor for Parrot, and I've made some pretty good progress so far. One cool result from this work is that I am finding all sorts of places where the GC internal data structures were being manipulated throughout the codebase, some instances of which are very likely to have been causing the problems I experienced over the summer.

That aside, I'm pleased to say that this morning I managed to get the GC almost entirely properly encapsulated. All external-facing GC functions are in the API, and all other functions are kept private. In addition, data structures like struct Arenas, struct Small_Object_Pool and struct Small_Object_Arena are now only accessible from within the GC subsystem. This prevents the rest of Parrot from monkeying around in these structures, but also makes it easier for alternate GC cores to redefine them as necessary. The API isn't particularly clean or elegant right now, but it is encapsulated and that's a start. It's certainly more then we've had since I've been a Parroteer.

The downside to this work is that the number of functions in the GC API has increased pretty substantially, both from creating new functions and by moving old functions into it. Many of the new functions are simple accessors for internal datastructures. I've managed not to have all the new functions listed as "PARROT_EXPORT", which is a win for dynamic link time, so thats good at least. Some of the macros that controlled blocking and unblocking the GC are now redefined as API functions, which is something I've wanted to do for a long time now.

In my last GC post I guessed at which functions would be necessary in the API. Now that I've finished encapsulating it, I can tell you what functions are actually in the API now:

1. Function to mark an object as being alive.
   
2. Functions to initialize and deinitialize the GC subsystem.
3. Functions to perform mark/sweep and compact actions
4. Functions to manipulate pools between interpreters, such as merging pools, moving shared objects between pools, etc.
   
5. Header allocation functions for PMCs, STRINGs, and other Buffer-like objects (ListChunks, Stack_Chunks, etc).
6. Header reclamation functions to take unused PMCs, STRINGs, and other Buffer-like objects and add them back to the free list.
7. Functions to add extension objects (pmc_ext and Sync) to existing PMCs, and functions to remove them again.
   
8. Memory block allocation functions for allocating buffers of arbitrary sizes, such as storage for STRINGs. Also, functions to deallocate these memory blocks, and functions to resize them.
9. Functions to determine if a given pointer is in a particular pool
   
10. Functions to block and unblock various GC phases, and functions to determine if they are blocked currently
11. Accessor functions to get information from the Arenas structure.
12. Function to mark PMCs that need timely destruction

So this is a basic list of the things we have in the API right now. I'm sure there are more features we would like to add here eventually, but these are the operations that are currently used by the rest of Parrot from the GC.

I'm still not entirely happy with the encapsulation status as it stands now. There are a few places such as the freeze/thaw subsystem where accesses are made to the memory system internals that I really wish weren't being made. But, that's a relatively small issue because most of those routines happen at interpreter destruction time after the GC has already been blocked/finalized.

I want to get my branch merged back into trunk soon. I've hit a good milestone now and I don't want this branch to live for too long lest new problems arise. Probably some small cleanup and documentation work to do first, but it's not far off now.

Switching Gears: GC

I talked briefly with Allison today via email, and decided that the best idea for me is to switch gears and not focus on the Asynchronous IO system just yet. Though I've been trying to keep it out of my mind for a little while the GC really is the most pressing need we have right now, so I'm going to start working on that instead of the AIO system, for now. Given several projects that I am both willing and able to work on, I will tend to work on the one that's the most needed by the project at large. I say "tend" because this is far from a hard-and-fast rule, but it does explain why I am willing to change focus in this case so readily.

My loyal followers (the null set) will remember back to last summer when I was working on a new GC system for Parrot as part of the Google Summer of Code project. People should also remember that my project was ultimately unsuccessful: I was not able to produce a GC that ran reliably. Part of it was my fault, the GC turns out to have been a bigger problem then I was capable of building successfully at that time. However, we've also learned the lesson that Parrots GC API is particularly messy and needs to be cleaned significantly before we can make another honest attempt at an improved GC core.

My task, should I choose to accept it, is to clean up the GC API so we can eventually have pluggable GC cores. This is going to be a bigger task then most people realize, for a variety of reasons. The current GC is intimately intertwined through the whole codebase. There isn't clear encapsulation between the GC and other parts of the system, and as a consequence it's almost impossible to create a new GC core because we don't even know what all the old core is doing (and where it's doing it at).

What we need to define is:

1. What interface functions (and macros) the GC should provide to do it's work.
2. What functions from the rest of Parrot the GC is permitted to call. This should be a very small subset of all functions Parrot provides.
3. What data structures the GC provides for access by the rest of the system.
   
4. What data structures the GC is allowed access to.
   

Not a small task at all but potentially a very rewarding one if it's done right.

Yesterday I created the "gc_api" branch to start the work, and my first task is to rename of the functions from "foo" to "Parrot_gc_foo" following the naming convention used by the rest of the Parrot subsystems. This isn't going to be a simple prefixing operation, some functions are going to be completely renamed to be more honest about what they do.

Next task is to work out what functions the GC needs to provide and export to the rest of the system. These functions will be located in src/gc/api.c only. Any function not in that file will not be intended for use by the rest of Parrot. Here is a partial list off the top of my head of functions that I think the GC needs to provide:

1. Initialize and Deinitialize the system
   
2. Allocate new STRING and PMC structures from the proper pools
3. Allocate new pmc_ext and sync structures (or, given a PMC, append these structures to it)
   
4. Allocate new raw data items from the fixed-size pools (or from the system, or whatever)
   
5. Mark an object as being "alive"
6. Mark an object as being "dead"
7. Create a new pool
8. Perform a mark phase
9. Perform a sweep phase
10. Perform a combined mark/sweep collection run.

There are probably a few more basic operations that I am forgetting right now, and there are definitely some "wishlist" items that I'm not mentioning here too for brevity. This does seem like a reasonably complete yet concise interface for the GC to implement. I'll post updates as my work progresses.