I took the day off yesterday to unwind from all my Parrot work, and what did I do instead? I worked on Parrot documentation. At least it gave me a lot of good time to think things over. Today, however, was really productive. I even wrote up a blog post about it, although apparently it didn't save.
The current GMS collector uses several doubly-linked lists to denote item status: a white, grey and black list for items in various stages of marking, and two lists to store items which require custom finalization. Items start in the white list, are moved to the grey list while they are being marked, and to the black list once the marking is over. After that, it's back to the white list to start the process over again.
It occurs to me that we don't need all these lists, an item's status will be tracked in the bitmap. Basically, we need two lists: one that holds all the items, and one that works like a queue to hold the grey (currently being marked) items. We start with the root items (and possibly the incoming IGP items) in the queue. At each iteration, we remove an item from the top of the queue, add all it's children to the end of the queue, mark the item as black on the card, and then move the item back into the other list. So we've got three states: the item is white (the flag is white), the item is grey (it's in the queue list, and we don't need to mark the flag grey) and black (the flag is black).
In this scheme, I don't think we need to use a doubly-linked list, because we are traversing the queue in the forward direction only. The "other" list doesnt even need to be a list at all, we can keep track of items that aren't in the queue directly using their positions in the arenas, and we can use those positions as indices into the card-marking bitmap. Using two bits, we can have four flag values: White, Black, Free, and some extra custom value (whose use I haven't decided on yet).
Adding an item to the queue, and removing it again each cost two pointer updates, as opposed to the 6 required for insertion into a double-linked list. We can get away with 2 updates (instead of the expected 3 or 4) because the "other" list is more like an unlinked "other" pile, and we just set all the pointers to NULL and don't need to maintain any kind of order. Retrieving the header from the object as we mark it is as easy as calling the "PObj_to_IT_HDR" macro, and going back requires a call to "IT_HDR_to_PObj". Both of those macros are simple pointer increment/decrement operations, and therefore are very inexpensive.
Using fewer lists means our data structures are smaller as well, and that's good too.
Today I updated these structures in accordance with my new vision, added a few function prototypes, a lot of comments, and a few other changes here and there. When I got tired of the GC, I spent a while working on a doozy of a patch to fix all the deprecation notices in PDD09. This mostly involved a lot of renaming functions and macros, but the changes were pervasive.
With the card marking scheme I'm still wondering about how to deal with PObj_custom_mark_FLAG, PObj_custom_GC_FLAG and PObj_active_destroy_FLAG. Hopefully, those pieces will all fall into place eventually.
I'm not sure what to do with the custom destroy flag, but for efficiency's sake we probably need to keep the custom mark flag in the PMC header itself.
