Re: Thinking about Lua memory management

[Nick Barnes <Nick.Barnes@...>]

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/>.

As a new list member and new Lua user, I welcome corrections of my
first impressions.

A large number of Lua users appear to be writing interactive games and
therefore have real-time constraints: even worst-case GC pauses must
be small (~10ms, say).

Many Lua users, including some of these games writers, are also
writing for embedded platforms (e.g. games consoles) on which memory
protection is either unavailable or grossly unwieldly.  It is
therefore impossible to use memory barrier techniques without mutator
cooperation.  Happily, mutator cooperation may be available from Lua
by modifying the Lua system, but presumably not from other software
linked with the Lua code.

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").
Real-time is difficult; real-time GC is very difficult.  You usually
need quite a bit of excess CPU power to guarantee real-time
constraints.

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.

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.

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?

Nick Barnes
Ravenbrook Limited