[gclist] When to garbage collect

[Hans Boehm]

On Nov 17,  9:52am, Fridtjof Siebert wrote:
> In my approach, the amount of work to be done per allocation is not
> proportional to the amount of live data, but proportional to 1/f, where
> f is the amount of free memory. I measure the the work of the collector
> in with the number of objects being marked black in the mark-phase of
> the collection (I use the number of bytes used by these objects in the
> case of objects with different sizes, but for simplicity, I just refer
> to the number of objects of equal size here).
>
> We want to avoid that we run out of free memory, so we have to complete
> a collection cycle within the next f+1 allocations. For a system that
> can store m=1000 objects, if it is in a state where only f=9 objects are
> free, we will have to finish a gc cycle within the next 10 allocations.
> So on the next allocation, we should check 1/10 of the objects, which is
> s=m/(f+1)=1000/10=100. On the next allocation, the amount of work for
> f'=f+1 will then be s=m/(f'+1)=1000/9=111, unless the previous
> allocation finished a gc cycle and increased f.
>
> Using this rule, s=m/(f+1), for the amount of work to be done has some
> advantages: This now guarantees an upper limit of gc work that is done
> on one allocation, if the number of reachable objects r is limited as
> well. And this upper limit of work can easily be reduced just by
> increasing the total amount of available memory m.
>
I think we're trying to state the same thing from different sides.  The amount
of work you have to do per allocated (fixed size) objects is roughly m/f.  I'm
arguing that you should always make sure that this is < a constant N by
expanding the heap so that f > m/N.

You're discussing the incremental collection case, which raises some more
profound issues.  I'm mainly concerned here about the average (i.e amortized)
cost per allocation.

Hans




-- 
Hans-Juergen Boehm
boehm@mti.sgi.com