Re: Thinking about Lua memory management

[Thatcher Ulrich <tu@...>]

On Wed, 19 Sep 2001, Roberto Ierusalimschy wrote:

> Currently we are considering a change in the garbage collection algorithm
> of Lua. But we do not want to slow down the interpreter, so the two schemes
> discussed here (reference count and incremental collectors) do not seem very
> atractive to us.
>
> Instead, we are thinking about a generational collector, with a
> write-barrier on tables. With a generational collector, we may be able to
> have much shorter stops for most collecting cicles, and this savings may
> compensate the overhead for the write barrier. So, maybe we could get not
> only shorter gc cicles, but also an overall performance improvement.

I'm glad to see this discussion happening; I've been looking into this as
well.

>From a game programming perspective, an incremental collector is more
crucial than lower overall overhead using a generational collector.
Basically in a game engine, you *never* want GC to take more than 1 or 2
ms per frame.  However, it can be acceptable for the GC to take 1 or 2 ms
*every* frame, even if that represents a high average overhead.

An incremental generational collector might be the best of both worlds,
but incremental takes precedence for games, I think.  Personally I'm not
too excited about reference counting or anything that's not safe or
depends too much on constrained usage.

I think a simple incremental collector can be written for Lua based on
Dijsktra et al's parallel GC algorithm [1], that doesn't have much
overhead compared to the existing collector.  I think the only real
significant overhead would be the write-barrier -- this is a bit of code
that gets executed every time a pointer to a Lua object is written to, and
adds something to the list of objects to be scanned if necessary.  I don't
know how often that type of operation happens in Lua programs, or what the
practical overhead would be (but I'm guessing it's pretty small).

Dijkstra's paper goes into all kinds of tricky details that aren't
relevant to an incremental Lua collector for use in a game engine, because
they were trying for a really fine-grained parallel collector, but the
basic approach is the same.  Basically in a game engine there's no need
for a truly parallel GC thread; instead you could just explicitly call
something like lua_gcincrement(n) every frame, where n represents some
parameter that controls how much work is done (perhaps the number of
objects to scan), and thus how long the call takes.

I took a quick read-through of the current Lua collector source, and it
looks like an incremental collector would be pretty similar.  The "marked"
lists would perhaps become "gray" lists, with an additional mark bit (or
code) to "blacken" an object.  Mark Johnstone's thesis explains all this
really well: paper #10 at http://www.cs.utexas.edu/users/oops/papers.html
(there's that URL again).

Anyway, I'm very interested in seeing this happening.  I'm happy to offer
encouragement and assistance to anybody who tackles this, or take a stab
at it myself if nobody is planning to work on it.

-Thatcher

[1] Dijkstra et al, CACM November 1978; if you have ACM Digital Library,
search for "On-the-Fly Garbage Collection: An Excercise in Cooperation".