i'm no gc expert, but here's my comments after discussions with alexandre on #parrot.
On 6/8/05, Alexandre Buisse <[EMAIL PROTECTED]> wrote: > 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. > since threading issues haven't been mentioned here, i thought i'd make sure they get discussed. now, if someone could say something intelligent about threading issues with this gc scheme, we can start the discussion :-) > > 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 "tuned dynamically", as in at run-time? alexandre mentioned this may be possible on #parrot, but there may be trouble with decreasing the generation count. i don't know if run-time tuning of the generation count is necessary, but if so, i imagine that decreasing the count at run-time could be achieved by merging generations. if this gc is tunable at build-time, it should be configurable such that timely destruction can be disabled. after all, most languages just don't need it, so why should they have the overhead? > 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. it's not mentioned specifically how timely destruction will be addressed. i suggest that there be a special type of gc run on scope exit which examines only the special "generation n", ensuring timely destruction without the overhead of a full gc run. > 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 ? > good start! and since the gc is modular, it should be straightforward to implement this without affecting the existing gc--that should make it easier to develop and test. > > Regards > > Alexandre > ~jerry
