Following google SoC and TODO item, https://rt.perl.org/rt3//Ticket/Display.html?id=33922, here is the scheme proposal for a new parrot GC (many thanks to leo for his help).
================================================================= In order to allow more powerful GC schemes, we need to be able to copy objects from a location of memory to another. There are problems with this, though, as C structures can hold pointers to objects we are moving, and we have no way (and don't want to) to make them update this info. So we add a level of indirection: objects consist of a header and the actual data. Headers are allocated once and for all at object creation and do not move. They only hold a pointer to the 'real' object, thus making it possible to move objects anywhere in the memory. Outside functions will see the header address as the object address and some internal macros will handle the extra indirection. The big disadvantage of this approach is that we use one or two words (if objects need to know where their header is, which seems reasonable) per object. We then use a generational, incremental mark-and-sweep algorithm, such as described by http://citeseer.csail.mit.edu/armstrong95one.html We have different generations (in fact queues) of objects, from 1 to n-1 (the value of n could be tuned dynamically). We also have two special generations, n, where objects do not grow old (to take care of timely destruction) and 0, where objects are very constant and long-lived (mainly used during parrot init). Objects in a generation are also sorted according to their age. The idea is to have the following invariant: all pointers go from new objects to old objects. Thus, we can mark all objects in only one pass, starting from the newest objects, generation n (using a Eratosthene-sieve-like method : if an object is not marked, leave it, else mark all of its pointers). When an entire generation has been processed, all non-marked objects are destroyed and the others are compacted. Generation n becomes generation n-1, with the exceptions of generation 0 and n. Comparing the age of two objects then becomes very easy : if they are in different generations, just compare their numbers. If not, the one with the lower address is the youngest. We can of course use a generational approach by limiting the number of non-marked objects. One problem is that our invariant can be broken. The solution is to track down these inter-generational pointers (IGP) and simply add them to the root set. In order to reduce the number of IGP, we allocate an aggregate as being artificially younger than scalars it has pointers to. Keywords: generational, mark-and-sweep, copying ================================================================= What do you think of it ? Regards Alexandre
