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

[eachus@spectre.mitre.org (Robert I. Eachus)]

In article <19950122.094355.149517.NETNEWS@UICVM.UIC.EDU> dhanley@matisse.eecs.uic.edu (David Hanley) writes:

 >      Hmmm.  While I suppose this is possible, I haven't yet run
 > across this "large body of algorithms" in which the execution time
 > is reduced by the order of magnitude when memory blocks can be
 > zeroed out very quickly.  Even if the algorithm did have to zero
 > out the memory itself, I don't see how that could take it from,
 > say, n^2 to n^3.  Could you please point some of these out to me?

    Maybe I should have said "real-time" or "on-line" algorithms.  The
distinguishing characteristic seems to be that you have to choose the
solution method without knowing the size of (or all of) the data set
in advance.  Another way of looking at it is that you are concerned
with solving a problem, but you are only concerned with the time
between receiving the last data and getting a result.  (Although in
practice, what you want to do is, at every stage of reading in data,
have a solution based on all the data seen so far.)

    The seminal paper is "Real-time computation." by M. O. Rabin in
1963. (The reference I have is Isreal J. Math 1, 203-211, but I think
it has been reprinted.)  Hartmanis and Sterns, "On the computational
complexity of algorithms," Trans. Amer. Math. Soc. 117, 285-306(1965).

 >   Hmm.  Not sure what this has to do with GC, really.  In any
 > case, it would be pretty easy to design memory hardware that would
 > zero out pages really quickly( just don't refresh them one cycle ).
 > And the bzero() function on your C compiler could be set to use it.
 > But mabye I'm just confused.  Could you please explaain if this is
 > wrong?

      Nothing confused in that, it is done in real-time applications
all the time.  A typical scenario is one where you build a hash table
using a hash function with a very low likelihood of collision.
Normally you would have to factor the time to clear the hash table, or
the time for maintaining a structure just for clearing the table into
the time required for the algorithm.  Poof!--if supported by the
hardware--is the most elegent solution.

      The only thing it has to do with garbage collection AFIAK is
that there is a nice technique where data is ping-ponged back and
forth between two heaps.  For example, you have a structure containing
all current aircraft tracks.  If the old data is reviewed and, if
still valid, moved every sweep, all the garbage created by building
maintaining the tracks can be made to dissapear with never a worry
about fragmentation.


--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...