Re: Ada GC and a bunch of other stuff

I should point out that many of David Chase's observations on the
interactions between a GC and an optimiser are borne of the way
conservative GCs go to work.


With a Mark-and-Sweep GCs we arrange to know the types and know the
sufficient set of pointers into the heap from the stack (held via
identifiers). GC occurs at a well-defined point and it is easy to
arrange that the primary pointers are comfortably stacked (without
imposing much overhead since the GC will be invoked with the HEAP
generator which will be invoked by a call known to the compiler (or
built into the language). Yes we do need to be carefull about safely
initialising storage with pointers in them, but this can often be
replaced with the user's own initialisation (at least in a sane
language like Algol 68 where there are no constraints on the
'initialisation-expression') or be deferred beyond the first
assignment if it comes before a potential GC point. No, we do not
need to scavenge pointers from floating point registers or worry about
intermediate address computations. And yes you do need some feedback
between the dead-code eliminator and the heap reference manager -
essentially any pointer in scope can be accessed by the GC
'asynchronously' to the normal program flow.


Compaction makes things a bit trickier as secondary pointers (copies
of pointers already registered with the heap) become important - these
will not be traced but must be relocated. It is not too much to ask
the compiler to keep secondary pointers tidy around a potential GC
point. The compiler can ignore some secondary pointers if they are
proven to be outside the heap (stack or elsewhere) which covers many
uses of temporary pointers. We have yet to do this, as the pay-offs of
compaction are not straight-forward.


Preemptive multi-threading is hairier still depending on one's
strategy. We chose to use semaphores to force all processes to
synchronise before a GC. This may cause a longer latency in the
process that triggered the GC but there is a gap in the process's view
of synchronisation with the GC in which compute which doesn't interact
with the GC or GC-owned pointers can be hidden (e.g. a vector product
of reals). The analysis is tractable for many useful cases in Algol 68
and PCF-Fortran, but I have yet to get this far.


This can even be extended into multi-processor MIMD arrays, but I
suspect the comms traffic will be too high and a generational approach
which can hold onto a set of pointers on/off processor would be
better.


With a Mark-and-Sweep GC you get more interested in using static
analysis to determine whether a GC really could occur within a region
of code, and determining whether a pointer is already registered via
another name. The only real disadvantage of a Mark-and-Sweep GC that I
have found is that the Mark stage can be critically dependent on the
number of pointers to an object as well as the number of pointers out
of an object.


Regards,
  ----------------------------------------------------------------------
Dave Lloyd Email: Dave@occl-cam.demon.co.uk
Oxford and Cambridge Compilers Ltd Phone: (44) 1223 572074
55 Brampton Rd, Cambridge CB1 3HJ, UK
--

Return to the comp.compilers page.
Search the comp.compilers archives again.