[gclist] Demand driven generational collector
Ji-Yong D. Chung
Fri, 5 Oct 2001 15:58:30 -0400
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
(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
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
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.