Re: incremental garbage collector?

["Thatcher Ulrich" <tu@...>]

On Mar 05, 2002 at 06:31 +0800, paul@theV.net wrote:
> 
> Sorry to raise this overly discussed topic again, but I'd
> believe there has to be some real solution to embed lua in a
> real-time environment, I mean, eventually.

Agreed.

> So my question is, is there anybody currently working on a
> incremental GC patch or something? Just in case somebody is
> already working on it, I don't want to reinvent the wheel :)

I did some work on this, on 4.1-alpha, but never finished.  Basically
I started with lua/src/lgc.c and incrementalized it.  I left some
things atomic (e.g. the elements in a table are marked atomically, but
the number of marks are accounted for to try to keep the gc work
roughly level).  I won't have time to work on this for many months, at
the least, so anybody who wants my work-in-progress to hack on is very
welcome to it.

The incremental marking/sweeping code is written but not tested.  The
missing piece is making sure the new function luaC_writebarrier() is
called every place where Lua writes a pointer to the stack, a table
key, any value slot, or allocates a new node.  I think there are
existing macros in the code to cover all these cases, but I never got
far enough to try it out or be sure.

> Our team is currently pretty tied up, and we aren't in the
> position to volunteer as a lead of this project. I am seeking
> any opinions or suggestions on this issue, and of course, Lua's
> author is best to comment on this.

Likewise, I'd love to hand this off to the Lua authors.  My views on
the incremental vs. generational question are:

* "truly" incremental is tricky to implement, but I think it's
  probably acceptable for the typical game application to mark tables
  atomically, which makes things easier.  Then, at least, the
  worst-case gc delay is determined by your largest table, so at least
  you have some predictable control over it if you're in a bind.

* generational is much more efficient on average, but even a very
  occasional long GC latency is a deal-breaker for some types of
  games.  I think the main complaint of most game developers is not
  overall efficiency (Lua is relatively slow anyway; use C/C++ where
  speed is critical), but long latencies (GC can cause unacceptable
  hiccups in the the visual frame rate).

* hybrid generational/incremental would be ideal, someday.  OCaml has
  such a collector; there are some nice implementation notes on the
  OCaml web site.

-- 
Thatcher Ulrich <tu@tulrich.com>
http://tulrich.com