Re: Incremental garbage collection coming to Lua soon?

[David Jones <drj@...>]

In message <911F8C8EB7A8084AAEDD55CEDC54D8F80CB544@iggy.rockstarvancouver.com>,
 "Nick Trout" writes:
> 
> 
> > From: David Jones [mailto:drj@pobox.com]
> > As deployed the collector is a mostly copying read barrier collector:
> > the Dijkstra tricolor invariant is maintained by turning grey objects
> > black whenever the mutator attempts to read a grey object.  The
> > Virtual Memory page protection system is used to implement the read
> > barrier meaning that the mutator has no extra code to implement the
> > read barrier.
> 
> How does this work? Is the VM managed in software, not hardware? Are you
> suggesting an (optional?) VM type system for Lua so a copying collector
> could be written?

We use a non portable interface to the host operating systems VM
interface.  This is typically mmap/mprotect and friends on UNIX like
operating systems and VirtualAlloc/VirtualProtect and friends on Win32.
When the mutator attempts to access a grey object fault is generated.
This is a signal in UNIX and a Structured Exception in Win32.

Obviously this approach is non-portable, so not something that would be
suitable for the Lua base system.  I wasn't really suggesting that Lua
use it, I was just using a real example of a real system with GC to
dispel many of the myths that were being promoted.

> > > 3) Pausing collectors are a constant nusance holding back the
> > >    capabilities of languages with garbage collection.
> > 
> > There are incremental collectors with bounded pause times.
> 
> What would you suggest as heuristics for bounding collection in Lua?
> Would you do it on a timer? It would be nice to be able to specify an
> amount of time that you could delegate to Lua for collection. Or,
> perhaps some sort of volatile flag could be checked by Lua whilst GC'ing
> so that you could interrupt it at will - e.g. on a timer or when you
> exit an idle period - mmm which suggests multiple threads. Or, perhaps
> there could be a call back to the client application periodically to
> check whether GC should wind up. In time sensitive environments the
> client application needs to make a call how important GC is and do as
> much as possible when under low stress. GC pauses will no doubt become
> necessary in extreme circumstances on limited systems to avoid
> allocation failures. It would be nice to have plenty of control over
> when this happened.

Generally there are 3 things that drive an incremental collector forward
(or cause it to do work):

* mutator accesses a protected object (usually black objects in a
  write-barrier scheme or grey objects in a read-barrier scheme).  The
  collector must do sufficient work to change the colour of the object.
  In fact in the usual write-barrier scheme the collector simply turns the
  black object grey which in fact regresses the collection instead of
  progressing it.
* allocation.  Really this is just one of many opportunities for the
  collector to do some work.  It's convenient because the mutator has
  explicitly called the collector.
* opportunistic.  The simplest interface (as Adam Moss points out) is
  for the mutator to explicitly call the GC to do a small amount of work
  and specifying how much work the GC is allowed to do and how much idle
  time the mutator thinks it has.

This is all a bit off topic really.

A more interesting question for Lua is how will Lua expose an
incremental collector to the host application.

Cheers,
 drj