[gclist] "This Old Space", with apologies to Will Clinger

[Henry G. Baker]

(Read with a fixed-pitch font.)

THIS OLD SPACE (THIS OLD REACTOR? :-)

Henry G. Baker

Copyright (c) December 8, 1996 by Henry G. Baker

Comments on Will Clinger's "Hanford" (in Washington State -- "the most
radioactive place on earth") GC (see References, at end):

Will's paper is elegant, but I still had a difficult time following it,
so I'll try to reformulate it here as a (IMHO) simpler example.

We assume all objects have identical sizes.

Let p be the probability of an object remaining live during 1 time step,
_where time is counted in terms of conses_ -- i.e., if an object is live at
time t, then the probability that it will be live at time t+1 is p.

Consider the age sequences of k conses, which we arrange in right-to-left
order.  Then the probability of their being alive at step k is as follows:

1, p, p^2, p^3, p^4, ..., p^(k-1).

Thus, after k conses, the expected number of live objects is

   k
1-p        1
----  ~=  --- , if p<1 and k is sufficiently large.
1-p       1-p

We now consider a simple Cheney copying GC.  Now k steps after a GC which
finds n live objects, we have the following object probabilities:

1, p, p^2, p^3, p^4, ..., p^(k-1), np^k

At equilibrium, the expected number of live objects is constant, i.e.,

       k
    1-p
n = ---- + np^k, so solving for n, we get
    1-p

     1
n = ---, which is rigorously independent of k, as expected <g>.
    1-p

The mark/cons ratio depends upon how often we garbage collect.  If we
collect after k conses, we will then mark n objects, to get a mark/cons
ratio of

n        1
-  =  -------
k     (1-p) k

Now consider a generational collector which garbage collects the 'youngest'
generation.  But we know that the mark/cons ratio for the newly consed
objects quickly approaches the _constant_ 1/(1-p)=n for relatively small k,
while the expected size np^k quickly goes to zero.  Therefore, a generational
collector which always collected the 'youngest' generation might do _more_ work
than a traditional non-generational collector, not even counting the additional
bookkeeping overheads of a generational collector.

Clinger noticed that if collecting the _youngest_ generation was pessimal
(for the radioactive model), then perhaps collecting the _oldest_ generation
would be optimal.  Indeed, the number np^k goes quickly to zero with increasing
k, so garbage collecting this old region should prove very profitable.

So we now consider a generational collector with 3 groups of objects:

* the newly consed objects B, with probabilities 1, p, p^2, p^3,...
* the group G that was proved live in the last GC, and
* the group N that didn't participate in the last GC.

Clinger suggests that the B and G groups 'sit out' the next GC, so that
we continually swap two older generations back and forth.

We let |B|, |G|, |N| be the total number of cells occupied by the groups
B, G, N, respectively, and let #B, #G, #N be the number of _live_ objects
in the sets B, G, N, respectively.  Note that although |B|, |G|, |N| remain
_constant_ over time, #B, #G, #N depend upon what time it is relative to
a garbage collection.

Suppose that GC's occur every k steps, and that the system is in equilibrium.
Then just before a GC, the total number of cells occupied by the groups B and G
is the same as the total number of cells in N, i.e., |N| = |G| + |B|.

Furthermore, just before a GC, B and G look like:
1, p, p^2, p^3, ..., p^(k-1) and
|G|p^k, respectively.

I claim that in equilibrium, N looks like B union G, but time-shifted by k:
N = p^k(1, p, p^2, ..., p^(k-1), |G|p^k).  This is because N is B union G
from the previous epoch whose GC finished k steps ago.

Thus, the total amount of space allocated is |N|+|B|+|G| = 2(|B|+|G|), and
the number of live objects (just before the GC) is

#N + #B + #G = p^k(#B + #G) + #B + #G
             = (1+p^k)(#B + #G)
             = (1+p^k)((1-p^k)/(1-p) + #G)
             = (1-p^(2k))/(1-p) + (1+p^k) #G

and #G is a free parameter.

We now wish to compare apples with apples.  Suppose that we have
  v live objects and
  s amount of space in which to manage these v live objects.

If we do non-incremental, non-generational collections, we would expect a

                                                        v
mark/cons ratio for non-generational collector to be = ---.
                                                       s-v

Note that we can compute k as k=s-v, and p as p=(v-1)/v.

If we do non-incremental, generational collections of the 'older'
generation, as discussed above, then we must split s evenly into 2 semispaces,
each of size s/2.  Furthermore, s/2=(|B|+|G|).  We know that in one of the
semispaces of size s/2 we have p^k times as many live objects as in the other,
so we have v/(1+p^k) live objects in the 'younger' semispace, and vp^k/(1+p^k)
live objects in the 'older' semispace, for a total of v live objects.  (N.B.,
the 'k' in the generational collector is not the same as the 'k' in the
non-generational collector.)

We can now compute the number of live objects in each of the groups _just
before_ a GC:
#(B) = (1-p^k)/(1-p)
#(G) = p^(2k)/(1-p)/(1+p^k)
#(N) = p^k(1-p^k)/(1-p) + p^(3k)/(1-p)/(1+p^k)

v = #(B) + #(G) + #(N) = 1/(1-p), as required.
#(N) = (#(B) + #(G)) p^k, as required.

|B| = k
|G| = #(N) = p^k(1-p^k)/(1-p) + p^(3k)/(1-p)/(1+p^k)
           = v p^k (1 - p^k + p^(2k)/(1+p^k))

We now plug in some numerical values and compare the generational with the
non-generational collector.  Suppose that s=100, v=50, so that the

non-generational mark/cons ratio = 50/(100-50) = 1.0.

Since v=50,

p = (v-1)/v = (50-1)/50 = 49/50 = 0.98.

We now consider the generational collector with k=33.
|B| = k = 33, |G| = s/2 - k = 17, |N| = 50.
#(B) = (1-p^k)/(1-p) = .4866/.02 = 24.33 ~= 24 live objects just before GC.
#(G) = .264/.0303  = 8.71 ~= 9 live objects just before GC.
#(N) = 16.96 ~= 17 live objects just before GC.

Thus, #(B) + #(G) + #(N) ~= 24+9+17 = 50 live objects, as required.  After
the GC, the 17 objects from N will fit into the space for G, and the 24+9=33
objects from B and G become the new N generation/semispace.

What is the mark/cons ratio for the generational collector?

We performed 33 conses (k=33), but marked only 17 (live objects in N), so the

generational mark/cons ratio = 17/33 = 0.52.

Thus, in this case, Clinger's 'oldest generation' heuristic improves the
mark/cons ratio by almost a factor of two, even though the total amount of
space is still 100, and the total number of live objects is still 50.  He has
indeed improved the mark/cons ratio as a _first-order_ effect, without taking
advantage of cache/paging locality.

How did I find the correct k?  The correct k is the solution to a
transcendental equation, which I solved by approximation/iteration.  In a
real system, we can continue allocating until the semispace is filled.  The
running of the system itself will 'solve' for the correct k.  A real system
would also allow small overflows from the total size constraint, which
statistics tell us will be relatively rare.

By analogy to a 'fractionating tower' in chemical distillation, we should
be able to get additional efficiency by breaking the problem down into larger
numbers of generations, which Will does in his paper.

We note that the "radioactive" model discussed in this note may have no
connection to the "real world", in that "real world" heaps may have statistics
very different from those of the "radioactive model".  It is currently
primarily useful as a Gedanken-experiment.

(Any errors is this note are mine, not Will Clinger's.  Please email me
at hbaker@netcom.com with any corrections and/or comments.)

References
----------

Clinger, William D.  "Generational Garbage Collection and the Radioactive
Decay Model (Extended Abstract)".  Northeaster University CS Dept.,
Boston, MA, Nov. 8, 1996.  (contact will@ccs.neu.edu).

%%EOF