Re: Thinking about Lua memory management

[Thatcher Ulrich <tu@...>]

On Mon, 24 Sep 2001, Nick Barnes wrote:

> At 2001-09-21 05:55:14+0000, Thatcher Ulrich writes:
>
> [on adding a better (incremental/generational/etc) GC to Lua]
>
> > 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.
>
> A friend recommended that I join this list because of all the GC
> discussion going on here.  At Ravenbrook we specialize in flexible,
> robust, high performance memory managers, including garbage
> collectors.  <http://www.ravenbrook.com/services/mm/>.

Cool, sounds like you're a good resource for this :)

>  Happily, mutator cooperation may be available from Lua
> by modifying the Lua system, but presumably not from other software
> linked with the Lua code.

I don't think that's a problem, because the host C/C++ program can only
affect the Lua state via the Lua API.

> Incidentally, I'd like to discourage the use of the rather bogus term
> "soft real-time".  There's not really any such thing as "soft
> real-time".  "Real-time" means that a late answer is a wrong answer,
> whether it's 10 milliseconds late or 10 years late.  If this isn't
> true of your system, it's not "real-time" (although it may be
> "interactive" or some other such term, for instance if it meets some
> statistical criterion such as "90% of delays less than 20ms").

The distinction that seems important to me is whether something is
provably real-time.  If you can *prove* the thing is really real-time then
you can use it in an airplane control system or nuclear plant or whatever;
this is what I think of as "hard real-time".  On the other hand, if it's
not feasible prove the system is real-time, but it's been observed to meet
its deadlines under strenuous testing, then that's something else.  I'm
not sure what the correct terminology is.  This is the kind of system that
I want for a game engine.

> Games are often real-time: there's some maximum GC delay, maybe 30ms,
> beyond which the game is broken.  Within that maximum, of course,
> there are more detailed constraints: maybe the GC could take a maximum
> of 10% of total CPU time in any given second, maybe no more than 2
> delays longer than 10ms in any given minute, etc.  I don't know the
> constraints, and they almost certainly vary from application to
> application.  If users could give typical real-time constraints for
> the GC, together with heap size numbers, that would be useful to me.

OK, here's roughly what I want (maybe some other game developers can chime
in as well):

1. No unpredictable latencies from Lua totalling more than maybe 2ms per
frame (preferably less).  *Predictable* latencies are not desirable, but
they're managable.  Lua is an interpreted scripting language after all, so
substantial overhead is to be expected.

2. A frame always lasts for 16.7ms, 33.3ms, 20ms or 40ms (60Hz, 30Hz,
50Hz, 25Hz), depending on the game and the type of TV it's hooked up to.
PC games are a little different than consoles because they can run at many
different refresh rates, but generally the requirement against
unpredictable latencies remains.

3. No problem with having the GC work done all at one time during a frame.
It's perfectly OK to have the game engine call a "do_some_gc()" function
once per frame, which does an increment of GC work; there's no need to
interleave the GC work with the Lua VM work.  In fact, I would prefer this
kind of interface for various reasons.

4. Constraints on Lua code as far as total heap usage and allocation rate
are completely negotiable; obviously I'd prefer zero time and memory
overhead, but for a scripting language I'm willing to tolerate quite a bit
of overhead in order to get the other benefits.  Anyone have some numbers
on heap size for real games (Josh)?  I use Lua in Soul Ride for
configuration, but barely run any scripts during gameplay.  The allocation
rate is ~0, and the total Lua heap is small, so GC issues didn't come up
at all during development.

> In such a situation, you may be best advised to use a Baker treadmill
> collector, with a write barrier provided by the Lua system.
> Treadmills can keep delays down to a few dozen instructions (at
> considerable overall cost).  Alternatively, some variant of Lins'
> cyclic reference counting, such as the Java collector by Bacon et al
> recently discussed on the gclist, may meet these real-time
> constraints.  Or a Nettles-style replicating GC.

Have you looked at the existing Lua GC?  (lua/src/lgc.c)  It's a very
simple mark-and-sweep.  I've been looking at it and thinking about it, and
it seems like it can be made into an incremental tri-color mark-and-sweep
without much change.  I'm quite confident that such a collector could meet
the four requirements above (especially given #4 :)

I don't think a treadmill is the right thing for Lua since Lua doesn't
manage its own free store (it calls external realloc/free functions).

I don't know much about the other collectors you mention.  Can you point
me to the gclist?

> At Ravenbrook we would certainly be able to write a GC for Lua, using
> our Memory Pool System (a flexible memory management framework).  From
> my first impressions of Lua, it would be very easy for us to make a
> non-incremental generational collector for it, somewhat harder to make
> an incremental collector, and really quite hard to make a real-time
> collector.  Would there be commercial interest in such a GC?

Personally I want to see a real-time collector available under the Lua
license.  I doubt there would be commercial interest from my employer; the
process of causing money to be allocated for such things is far more
arduous and less fun than writing code :) but I can't speak for anyone
else.

-Thatcher