[Python-Dev] GC Proposal

[Adam Olsen]

On Sat, Jun 28, 2008 at 12:47 PM, Antoine Pitrou <solipsis at pitrou.net> wrote:
> Adam Olsen <rhamph <at> gmail.com> writes:
>>
>> We need two counters: one is the total number of traceable objects
>> (those we would inspect if we did a full collection) and a number of
>> "pending" trace operations.  Every time an object is moved into the
>> last generation, we increase "pending" by two - once for itself and
>> once for an older object.  Once pending equals the total number of
>> traceable objects we do a full collection (and reset "pending" to 0).
>
> It sounds rather similar to Martin's proposal, except with different
> coefficients and slightly different definitions (but the "total number
> of traceable objects" should be roughly equal to the number of objects
> in the oldest generation, and the "number of pending trace operations"
> roughly equal to the number of survivor objects after a collection of
> the middle generation).

The effect is similar for the "batch allocation" case, but opposite
for the "long-running program" case.  Which is preferred is
debatable.. If we had an incremental GC mine wouldn't have any bad
cases, just the constant overhead.  However, lacking an incremental
GC, and since refcounting GC is sufficient for most cases, we might
prefer to save overhead and avoid the pauses than to handle the
"long-running program" case.

My proposal can be made equivalent to Martin's proposal by removing
all of its pending traces when an untraced object is deleted.  We
could even change this at runtime, by adding a counter for pending
objects.

Come to think of it, I think Martin's proposal needs to be implemented
as mine.  He wants the middle generation to be 10% larger than the
oldest generation, but to find out the size you need to either iterate
it (reintroducing the original problem), or keep some counters.  With
counters, his middle generation size is my "pending traces".


> Am I missing something?

Actually, I was.  I lost track of Martin's thread when preparing my idea.  Doh!


-- 
Adam Olsen, aka Rhamphoryncus