Re: Parallel & RT GC (was Re: Real-Time GC (was Re: Widespread C++...?)

[hbaker@netcom.com (Henry Baker)]

In article <3fmgbn$rns@watnews1.watson.ibm.com>, ncohen@watson.ibm.com wrote:

> In article <EACHUS.95Jan17112913@spectre.mitre.org>,
> eachus@spectre.mitre.org (Robert I. Eachus) writes: 
> 
> |>     There is another major reason for putting the custom hardware in
> |> the memory system.  There is a fairly large class of problems which
> |> require time proportional to n^k lg2 n on any von Neuman architecture,
> |> but can be solved in time n^(k-1) lg2 on hardware which supports
> |> clearing large sections of memory to zero in constant time.  (Note
> |> that if k is one, you can get orders of magnitude improvement.)
> 
> This doesn't make sense, because there is a well known programming trick
> (used more in analysis-of-algorithms than in real programs because of the
> large constant factor) for marking a large section of memory as
> uninitialized in constant time.  (The effect of initializing a large
> section of memory to zero is achieved by checking on each read whether
> the location read from has been initialized, and using the value zero if
> it has not been.)

This technique is known as a 'read barrier' in GC circles.

See:

ftp://ftp.netcom.com/pub/hb/hbaker/RealTimeGC.html (or .ps.Z)

for 1978 CACM reference.  (The read barrier technique is discussed twice in
this paper -- once for the basic GC algorithm itself, and once for 'moving'
and/or copying large arrays incrementally.)