[plt-scheme] Some thoughts about GC and realtime aplications

From: Joe Marshall (jmarshall at alum.mit.edu)
Date: Fri May 19 13:24:51 EDT 2006

On 5/18/06, Ivan Boulanov <l00bis at mail.ru> wrote:
>
> GC, IMHO, is hardly applicable for realtime programs in common and for games
> in particular. GC happens rarely but takes a lot of time and halts execution
> for a moment that is sufficient for the game to become unplayable.

I don't believe this.

Yes, it is true that a full mark/sweep or flip will stop the world,
but I think that it
should be possible for a modern processor to make use of hard real-time GC
techniques so that GC pauses are shorter than the redraw time.

The Lisp machine had a real-time GC.  Processing would run in parallel with the
collector.  It is true that performance degraded when a flip occurred,
but there are
a number of reasons to reconsider this approach:

  1.  There was no effort to *guarantee* processor time on the Lisp Machine.
      Although the GC had real-time capability, objects were moved
atomically and
      large objects naturally took longer.  Disk seek times were not considered.
      A lot of nit-picky cycle counting needs to be done to guarantee
that each step
      in the GC takes an exact, known amount of time.  This wasn't done.

      Presumably one would put in the effort required to make these
hard real-time
      guarantees if one were writing a game.

  2.  Modern processors are *fast* compared to a Lisp Machine.  I suggest that
      implementing a read-barrier in *software* (that is, wrapping
each and every
      memory read with a oldspace check) would significantly outperform the
      hardware of an 80's vintage Lisp Machine.

  3.  Modern computers have *lots* of RAM.  The reason a full flip on a Lisp
      Machine was so slow was because you had to cycle hundreds of megabytes
      of heap through hundreds of K of RAM.  The main advantage of generational
      GC was in avoiding going to disk for the younger generations.  Nowadays
      it is not unreasonable to keep the entire process pinned in main memory.

  4.  Given the enormous changes in the hardware, techniques that were
      considered insanely wasteful in the past are now quite reasonable.

> The other issue relates to small objects. Such an objects are born and
> become garbage very often so programmer have to take care to avoid them, but
> this is rather inconvenient.

Short-lived, small objects are simply not an issue with a properly tuned
generational collector.  Just set your generation size big enough.

> A completely different approach is to use reference-counting instead of GC.
> This approach is similar to the modern C++ programming approach of smart
> pointers.

This, I think, is the wrong approach.  If you trace a program that
uses reference
counts, you'll notice that it spends a good chunk of time incrementing and
decrementing the refcounters.  This is spread rather evenly throughout the
program, so it doesn't introduce noticable pauses, but it does take up processor
time.

-- 
~jrm


Posted on the users mailing list.