Re: Lua's GC

[RLake@...]

>From Thatcher's useful notes:

* Lua's current garbage collector uses a traditional simple
  non-incremental mark-and-sweep algorithm.  When a collection cycle
  begins, it walks all reachable heap objects in the mark phase, and
  then walks the entire heap in the sweep phase.  So the time cost is
  proportional to the number of objects on the heap, plus the number
  of reachable objects.

----

This is true. Furthermore, free(3) is called on every piece of garbage. The
performance will be highly dependent on the implementation of free, but
it's unlikely to be very good, since free is generally not optimised for
garbage collection. As an example, each call to free may do quite a lot of
bookkeeping trying to consolidate consecutive pieces of garbage; it would
actually be considerably more efficient to do this once, at the end of a
bunch of frees.

If one takes care to call the garbage collector when there is a lot of
garbage, the cost of walking the heap is minimised. However, to really take
advantage of that, you need to be able to free garbage rapidly; ideally at
no cost whatsoever. Doing so is not particularly difficult; one simple
solution is to use a bitmap of allocated objects, and scan the bitmap
lazily on every call to malloc. In this case, free is actually free (or
rather, the cost is amortised into malloc calls). There are some details,
obviously :-)

What is difficult is to write such an allocator in ANSI C, since it really
requires at least a minimal understanding of the machine's hardware; at
least to the extent of understanding word lengths, alignment constraints,
and the low-level mechanism for acquiring new heap space that is used by
malloc (sbrk, mmap, or whatever). However, the porting effort for
a reasonable algorithm should not be enormous.

In any event, it may be worthwhile trying alternative malloc/free
implementations.
This is probably not relevant to anyone, but I noticed that my scripts were
running
significantly slower on BeOS than on FreeBSD (on a dual-boot machine).
Replacing
the BeOS malloc/free removed this difference.

I think (but it's just a theory) that Lua garbage collection speed could be
radically improved by focussing on the implementation of malloc/free in a
way that would provide benefits both to soft real-time programs (games) and
to other uses of Lua. Generational
garbage collection, because of the imposition of the write-barrier, tends
to increase
total garbage collection time in return for lower average latency, although
it is hard to
make sweeping generalisations since it depends so much on implementation
details and
memory usage patterns.

...

(The simple-minded algorithm presented above does not really handle
finalisation properly. Finalisation is difficult.