RE: Incremental garbage collection coming to Lua soon?

[RLake@...]

drj:

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

nt:

> 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?

I don't think he is suggesting anything :) just describing some
possibilities. Since there is no ANSI standard way of interfacing
with VM systems (and indeed no requirement in standard C that
there even be a VM system), it would not be a plausible strategy
for Lua.

However, fwiw, the "usual way" of doing this sort of thing is to
mark pages as unreferenceable (or unreadable), and then do the work
when an memory exception is raised by the VM. I'm just guessing, but
since David says it is a mostly-moving GC, it probably colours all
grey objects on the page black before returning to the mutator; if so,
there is no need to field another interrupt on the same page (until
another object on the page becomes grey).

A common way of time-bounding incremental marking algorithms is to
mark a number of objects on every allocation.

Copying garbage-collectors do not need to use handles to facilitate
object moving, although some do in order to deal with large objects.

I don't think that a copying garbage collector would be appropriate
for Lua, though: you could certainly copy some internal objects, but
copying a userdata could be disastrous if the rest of the application
is not expecting that to happen; Lua has so far avoided putting
serious restrictions on the environment in which it is embedded and
I wouldn't expect that to change. I suspect that maximising efficiency
would demand writing an entire application to a common memory 
management regime (although that regime might have different policies
for different object pools) but, sadly, C compiler do not generally
concern themselves with cooperating with garbage collectors.

I continue to believe that garbage collection is a Good Idea, that
it generally improves performance (or at least does not degrade it)
and that it certainly improves coding time; it would be even better
if more widely adopted. For example, cooperating with garbage
collectors could become a priority for C compiler writers, and
hardware-assisted garbage collection could become more generally
available; these things would probably happen if there were enough
demand.

R.