[ruby-talk:5570] Notes about GC

I wrote the following notes in a msg to Aleksi some weeks ago. They are
about Ruby's GC.  I thought I'd integrate them to gc.c, but I'm changing
some things I didn't think I'd change originally. So I'm posting the notes
here, because they can be useful without necessarily being relevant to the
GC's source code, plus, a lot less people would give feedback to source
code comments :-).

[the following notes have been slightly edited since the original ones]

---

In Ruby, garbage collection is done in two occasions: when the allocation
size counter goes over a given threshold; and when all the active object
pools are used (apart from a "minimum free memory"). In the latter case,
after GC, inactive object pools are activated, and if there are no more
inactive object pools, then a bunch of them are created at once. 

There are four values of interest that affect GC frequency:

	* allocation size counter threshold
	* activation of object pools
	* creation of object pools
	* free memory is below minimum

The problem with Ruby 1.6 (and former versions) is that those four values
are compile-time constants. If we separate ruby execution in two parts (1:
evaluation, 2:GC) this means that garbage collection is done at constant
intervals in evaluation time (on average). However, the amount of time
spent in each GC phase is (on average) proportional to the amount of
allocated objects.

By making the above four values proportional to the amount of currently
allocated cells, you decrease the GC frequency, so total fraction of time
spent on GC should remain constant.

Since allocation of new object pools is done only when the memory is
(nearly) full, there is no risk that a process will make its process size
skyrocket if it is just keeping a small average amount of live objects
with frequent creation/deletion.

The process size should always be a relatively small percentage above the
maximum number of allocated objects at once. 

But strict proportionality does not work: it crashes if some of the base
values are too small. By lowering them as much as possible, Ruby could be
downscaled so that it could run in smaller systems, or most probably, on a
regular system with a large number of small Ruby processes. I did not
experiment in that direction. 

> In any case this is good news, and I can't wait to see how well generative
> GC with your allocation policy will work. As far as I understand all new
> objects will be placed to "new-objects" pool, and if they survive few GCing
> they got a promotion to "old-objects" pool, which is GCed more seldom. 

The performance of a generational GC without my patch would depend on the
policies for sizing the different age categories. Possibly that a
generational GC would remove some of the need for my patch; OTOH, applying
and expanding the proportionality policy (in age category sizes) might
result in even better performance (BUT: I don't have a clue).

> My example program should be quite fast with [generational gc]

* many small programs will see good or tremendous performance increases;

* many other small programs will see no increase or worse;

* Most complex enough programs contain lots of different programs, which
is like an average of a lot of various small programs together. The
emerging pattern should be that the lifetime of an object is 1/rand on
average.  (?) 

Note that I don't know GC very much, I'm mostly applying general knowledge
:-)


matju