[psoc-2008] [report] Week of June 9th

[Andrew Whitworth]

This last week was a very busy one for the GC project, because much of
the design details have been finalized, the necessary scaffolding has
all be erected, and a lot of code was able to be written. Several
major ideas were implemented this week, and I will try to mention them
all.

* All the major data structures are laid out and mostly complete.
There is always going to be some tweaking, but the major details are
set now. GC Header structures, as a prime example, are the same size
as those for other GC implementations but now contain more information
and lend themselves to more efficient algorithms. The structure of the
GC is complete and mostly coded. The GC is set up now as a state
machine, which allows for quick returns and resumes into the
algorithm.

* The GC has always been intended to be incremental. The goal is to be
able to spread out GC work into small batches so that the world
doesn't have to stop completely for long pauses when the GC performs a
complete run from top-to-bottom. I had planned to use a generational
scheme, where objects were classed into "old" and "young" categories,
and younger objects are scanned more frequently. Instead, we're
starting to look at a scheme where objects are scanned by trees and
not by generations. In tree-mode, we start with a single root object
and scan all it's children, then return. At each GC iteration, we scan
one tree completely. Once all trees have been scanned, we run the
sweep phase and clean up all the garbage. At the moment, much of the
iterative mark logic is implemented. The sweep logic is falling into
place, and should be mostly done in the coming week.

* In addition to regular incremental operation, I've been preparing
for a "Parallel mode" which uses a separate GC thread to run the
collector without having to pause the program explicitly. This feature
is a long way off, but the basics have been laid out for later
development.

* Instead of using the GC-related flags that come with most PObjs,
object marking is being done on separate bitmaps called "cards". Each
arena gets a card array, where flags on the cards correspond directly
to items in the arena. Functions to allocate, manipulate, and read the
cards are all written. Functions to manipulate cards can be slightly
less efficient then comparable functions to manipulate flags directly
on the PMC. However, this inefficiency made up for in huge efficiency
gains in the sweep phase. Keeping all the flags in one place are also
going to reap the "hidden" benefits of better spacial locality and
caching efficiency.

This past week has been my most productive so far in terms of raw code
written. I'm hoping to ride the wave through this week as well, and
get some of the last details implemented. Within two or three weeks I
want to start system integration and initial testing. If things go
smoothly, I can progress to implementing some more advanced features
like the threading mode, caching of entire long-lived trees (an analog
of a generational scheme) and other tweaks and improvements.

--Andrew Whitworth