Re: Generational GC (was Re: A review of changes between 5.1 and 5.2-work3)

[Roberto Ierusalimschy <roberto@...>]

> On May 21, 2010, at 9:30 AM, Mike Pall wrote:
> 
> > About point 14: the experimental generational collector in Lua 5.2
> > is not enabled by default. And it's non-incremental, which means
> > it's less applicable to apps with a need for low-latency GC (games).
> 
> Thinking about generational GC, presumably the goal is to reduce memory consumption, correct?

Not exactly. Most kinds of collectors make a compromise between CPU and
memory consumption. (At one extreme, with enough memory you do not need
to run the collector at all.)

The immediate goal of a generational GC is to reduce CPU work, by reducing
the number of objects to be visited at each collection. Of course, because
of the above balance, we can trade that CPU gain into memory gains, by
running the collector more often or more aggressively.


> I would (naively) think that one could run essentially two incremental
> GC's. The nursery gets collected at a rate based on allocation. The
> older generation gets collected at a rate based on tenuring. There is
> probably a need for an adolescence phase in which an object in the
> nursery has been marked to be tenured because it is now referenced
> from a tenured object but we haven't unthreaded it from the nursery
> object list. This would get cleaned up during the scan of the nursery
> along with tenuring any objects that had survived enough cycles in the
> nursery.

This is more or less how Lua collector works (or should work).

The general idea is simple: black objects (from the incremental
algorithm) are old objects. The main difference between the incremental
collector and the generational one is that the generational collector
does not turn black objects back to white when sweeping. So, any object
that survives one cycle becomes old. The generational collector also
marks black objects with an old bit.

Lua keeps a single list of (mostly) all objects. The sweep phase
traverses this list, freeing unmarked objects. New objects are always
added to the front of the list. In the generational mode, when the sweep
phase finds an object marked with the old bit, it can stop the sweep, as
all objects after this one must be old, too. The nursery is simply the
first part of the list.

Lua has a "grayagain" list, which is used by the incremental collector
to visit objects that were black and turned gray again by a write
barrier. The generational collector uses exactly the same code to
keep its "remembered sets" of old objects that point to new ones.

The control is more or less as you described. Minor collections are
controlled by allocation. Major collections are controlled by the
memory in use after a minor collection (a good proxy for the size
of the old generation). 


> To reduce memory consumption, one then runs the old generation collector
> at a faster multiplier than usual so that it collects faster. But this
> is offset by only running it in response to objects getting tenured.

For that, we need different multipliers for major and minor collectors.

-- Roberto