[gclist] Demand driven generational collector

[Ji-Yong D. Chung]

    Hi,

    Thank you, Pekka P. Prinen and Prof. Moss for your 
references to Lisp Machine GC and Appel collector.

    Thank you, Nick Barnes, for pointing out the problem 
with the Piglet in the Snake problem.

    I have given the Piglet in the Snake a bit of
thought, and I get the impression it really should not 
be a problem for "demand-driven" generational collector.

    Essentially, the Piglet comes to life because the  
flux of live objects from the nursery is very large.
Now, there are two possibilities, I see, at 
this point.

=================================

(1) Piglets are born at a constant rate:
   
    As Piglets come to life in the nursery,
the higher generations must empty its contents
to the next generation, to provide space for other
Piglets that will be promoted.  This would be true no matter
how long one tries to age objects in a given generation: 
nursery keeps becoming pregnant with the Piglets.

    The only "solutions," it seems to me, are (1) 
to create additional space at the last generation 
(if there is such a thing as the "last generation"), 
or(2)  to keep adding new generations to accomodate 
additional objects.  And pray that 
object creation will stop before one
eventually runs out of memory.

    I don't think additional aging within a generation 
will reduce the amount of copying.  This is just the 
case of too much influx of objects.

======================================

(2)    In the second scenario Piglets are born once in 
a while.
    
    In this situation, when  a Piglet comes to life, the worry
is that this Piglet will crawl down a single generation 
_at each collection_ until it is at the last generation.
It would seem that the presence of the Piglet will make
what should be a minior collection into a major collection.
I think, according to the traditional
algorithm, one's expectation might be that, at each 
collection, generations of up to the particular generation 
which the Piglet occupies will be collected.
(So, if a Piglet is at generation n, all generations including
n will be collected).

    I don't think that will happen.  Piglet will move
down to a certain generation and will stay there.  The reason
is that its immediately lower generation will be relatively 
empty.  A relatively empty generation acts as a 
"barrier" in determining of up to what generation should
be collected.  

    In other words, the demand driven collection algorithm
would not see the necessity of collecting the Piglet's
current generation, unless the preceding generation were
full.  (So, if generations 1 - m are full and Piglet is 
at generation M, where M >> m, then, only the 
first m generation will be collected, even though generation
M itself is full).

    If the lower generations become full, the Piglet
will move down to the next generation, and it will stay
there again, until all of its younger generations are full.

    So, you can see that the Piglet moves only when
it is necessary.  It will continue its movement once
in a while, until the Piglet is, thankfully, digested.  

    If one had tried to solve this problem by
aging the Piglets in younger generations, one 
would be forced to copy the Piglet from FromSpace to
ToSpace a number of times.  I am not sure whether 
this would result in computational savings.  

    My hunch (perhaps erroneous) is that copying to 
the next generation (promoting), for demand-driven 
generational collector, should be more efficient.