Re: LuaChip and GC

["Michael T. Richter" <mtr1966@...>]

> Garbage collection time is a function of heap size; if the heap is
> sufficiently small, real-time performance should be practical. It is
> only problematic if you have a large heap; in that case, there are a
> number of solutions but none of them are simple.

It's been a very long time since I've looked into any of this, so please
forgive any vagueness or inaccuracies in advance.

A Baker's Treadmill is a concurrent algorithm.  Ideally it runs as a
low-priority task (which could cause a problem if you have a lot of
high-priority tasks gobbling memory, of course) and collects garbage a cell
at a time as long as nothing more important is running.  It uses a
circularly-linked list of cells and three pointers (for "black", "white" and
"grey" in effect), together with a write barrier, to manage memory.  Cells
proven to be reachable, unreachable or undetermined during the scan are
snapped into different places in the treadmill (swapping pointers -- no
actual copying occurs) as the process carries on.  Allocation is performed
similarly -- it's a matter of snapping links around in the treadmill.

Assuming you can make reasonable predictions as to the heap size, the
algorithm is hard real-time capable.  (You have to inspect the
implementation VERY carefully to ensure that it actually is, of course!)
Even if the existing treadmill is outgrown and new heap elements need to be
snapped in, a decent allocator suitable to a real-time environment can be
used to keep things in line.  And giving up unnecessary heap elements can
also be done within appropriate hard-time constraints.

This, of course, presumes that I remember Baker's Treadmill properly.