Soft RT GC (was Re: [gclist] GC topics)

[Lee Webber]

First, something slightly off-topic:

   "The average Pentium PC is grossly underconfigured
   with respect to memory." [This and all quotes from
   boehm.PARC@xerox.com]

The retail cost of upgrading a 16MB Pentium to 64 MB is
about $2000. (You can knock off $500 from that if you buy
in bulk and/or install the memory yourself.) This is a size-
able fraction, possibly in excess of 100%, of the cost of the
original machine.

   "There are well-known techniques for real-time GC
   that [provide soft real-time performance].  They tend
   to be a bit more expensive to implement in practice."

Any references (preferably available on the net - I don't have
access to back issues of journals), for non-conservative
implementations that don't depend intimately on specific
OS's or hardware platforms?

                                    * * *

Not that anyone asked me :-), but here's what I would like to
find on the shelf in the GC Emporium. Assume a three-tier
priority structure: Atomic (highest), User (may contain sub-
levels, race conditions possible between Users), and
Collection (lowest). For most generality, assume a pointer is
a pointer (i.e., not tagged). The Universal GC would interface
to the compiler (or anyone else) as follows:

1. The Universal GC would deal with whole objects only.
    The compiler would allocate and deallocate all such
    objects via the UGC, supplying the size of the object
    desired and a reference finder function (see below) to
    associate with it. Allocation and deallocation would run
    at User level (although they could invoke Atomic functions
    as described in #3 below if they really had to).

2. The UGC would do the bulk of the work at Collection level.

3. The UGC would provide to the compiler a read barrier
    function (to be invoked when any object is referenced),
    a write barrier function (to be invoked when a reference
    to an object is copied), both (or neither :-). These functions
    would be invoked at User level.

4. The compiler would supply with each object allocated a
    reference finder function which, when invoked with a
    pointer to an object, would return a set of all pointers
    associated with the object. This function would be
    invoked and run at Collection level.

5. The compiler would also supply a root finder function
    which, when invoked at Collection level, would run at
    Atomic level, generate a snapshot root set of pointers,
    return to Collection level and return the set. (Note the
    priority-switching mechanism is external to the UGC.)
    The compiler might also be required to supply one or
    more other Atomic functions which I haven't thought of.
    All such functions must be capable of being implemented
    quickly, as they determine the soft RT guarantees.

6. Extra credit for C or assembler macros for anything above
    (such as the read/write barriers), to allow functions to be
    inlined.

Such a product would effectively solve the soft RT GC
problem for any implementation where everything is an
object and the overall performance hit of using the UGC
is acceptable.

Is such a thing out there? Is is possible?

Lee Webber
  I am speaking for myself and not my employer.