Garbage Collection Idea

[Craig Black]

This is coming from someone who only understands garbage collection at an 
elementary level, so anyone is welcome to correct me if I'm missing 
something.

To mark valid pointers, the stack is scanned for root pointers.  The 
allocation unit that each root pointer references is then scanned for 
pointers, then the allocation units referenced by those pointers are 
scanned, and the algorithm recurses.

IMO, this seems like unecessary memory scanning.  Couldn't we use a more 
direct approach such that no scanning is required, and we just jump to the 
location in memory where each pointer resides?

My first idea is in regard to root pointers, or pointers on the stack.  The 
compiler knows when each pointer goes on the stack, so it could insert code 
to keep track of all the pointers that are currently on the stack.  The 
obvious data structure to use for this would be a stack.  When a pointer is 
pushed on to the stack, the address of that pointer could be pushed on a 
separate "pointer stack".  When that pointer goes out of scope, it's address 
would be popped off of the pointer stack.  Then when the garbage collector 
needs the root pointers, it would simply traverse the pointer stack, which 
would no doubt be significantly smaller than the primary stack.

Then, instead of scanning each allocation unit for pointers, we could use a 
more intelligent approach.  This approach requires preprocessing for each 
class to generate a little reflection information.  Each class would include 
an array of fields that are pointers.  Each element in the array would 
simply be an address that would reference a pointer field that resides in 
the class.  If the class doesn't contain any pointers, then this array will 
be empty.

Once each class has an array of pointer fields as described above, we need 
only determine the type of class for each pertinent allocation unit, and use 
the pointer array for that class, rather than scanning the entire allocation 
unit, which could be completely devoid of pointers.

If my thinking is correct, this approach would make garbage collection 
significantly faster.

Thoughts?

-Craig