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

[ncohen@watson.ibm.com (Norman H. Cohen)]

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.)

The trick works as follows: View the section of memory as an array of N
initializable units numbered 0 to N-1.  Allocate two arrays of integers,
Stack and Stack_Index, indexed from 0 to N-1.  Initially, both arrays
contain garbage.  There is a stack pointer, Top, pointing to the
highest-indexed element of Stack that does NOT contain garbage (so that
initially it equals -1).  When initializable unit I is initialized, Top
is incremented, the new value of Top is placed in Stack_Index(I), and I
is placed in Stack(Top).  Then the index of every initialized unit is
found exactly once in Stack(0 .. Top), and if unit I has been
initialized, Stack_Index(I) contains the index within Stack(0 .. Top)
containing I.  The test for whether initializable unit I is initialized
is: 

   if Stack_Index(I) in 0 .. Top then
      if Stack(Stack_Index(I)) = I then
         return True;
         -- Stack_Index(I) contains a valid index into the stack, and the
         --   corresponding index in the stack indicates that unit I has
         --   been initialized.
      else
         return False;
         -- The garbage in Stack_Index(I) happened to point into the
         --   initialized part of Stack, but the value in Stack reveals
         --   that unit I was not the initializable unit for which this
         --   component of Stack was initialized.
      end if;
   else
      return False;
      -- Garbage in Stack_Index(I) is not even a valid stack index.
   end if;

or, more succinctly,

   return Stack_Index(I) in 0 .. Top and then Stack(Stack_Index(I))=I;

--
Norman H. Cohen    ncohen@watson.ibm.com