From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00,INVALID_DATE
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: f891f,9292211c2d4756a8
X-Google-Attributes: gidf891f,public
X-Google-Thread: 109fba,46882e3fad98420e
X-Google-Attributes: gid109fba,public
X-Google-Thread: 103376,48b89668821c1c9f
X-Google-Attributes: gid103376,public
X-Google-Thread: 1108a1,9292211c2d4756a8
X-Google-Attributes: gid1108a1,public
X-Google-Thread: f78e5,9292211c2d4756a8
X-Google-Attributes: gidf78e5,public
X-Google-Thread: 1014db,9292211c2d4756a8
X-Google-Attributes: gid1014db,public
X-Google-ArrivalTime: 1995-01-20 10:35:28 PST
Path: 
 pad-thai.cam.ov.com!noc.near.net!chpc.chpc.org!bigboote.WPI.EDU!news.mathworks.com!news2.near.net!emerald.tufts.edu!blanket.mitre.org!linus.mitre.org!spectre!eachus
From: eachus@spectre.mitre.org (Robert I. Eachus)
Newsgroups: 
 comp.lang.c++,comp.lang.c,comp.object,comp.lang.misc,comp.std.c++,comp.lang.ada
Subject: Re: Parallel & RT GC (was Re: Real-Time GC (was Re: Widespread
 C++...?)
Date: 20 Jan 1995 14:49:01 GMT
Organization: The Mitre Corp., Bedford, MA.
Distribution: world
Message-ID: <EACHUS.95Jan20094901@spectre.mitre.org>
References: <787227087snz@wslint.demon.co.uk> <3ckb8g$841@gateway.wiltel.com>
	<1994Dec21.151952.8902@merlin.h>
	<19941230.201628.350635.NETNEWS@UICVM.UIC.EDU>
	<3e9f60$8du@jive.cs.utexas.edu> <3epfsi$64d@gamma.ois.com>
	<3eua1r$4ea@gnat.cs.nyu.edu> <3f5va$r07@gamma.ois.com>
	<kelvin.790009178@kickapoo> <EACHUS.95Jan17112913@spectre.mitre.org>
	<3fmgbn$rns@watnews1.watson.ibm.com>
NNTP-Posting-Host: spectre.mitre.org
In-reply-to: ncohen@watson.ibm.com's message of 19 Jan 1995 19:59:51 GMT
Xref: pad-thai.cam.ov.com comp.lang.c++:70129 comp.lang.c:58372
 comp.object:15744 comp.lang.misc:6846 comp.std.c++:9145 comp.lang.ada:14498
Date: 1995-01-20T14:49:01+00:00
List-Id: <comp.lang.ada>


In article <3fmgbn$rns@watnews1.watson.ibm.com> ncohen@watson.ibm.com (Norman H. Cohen) writes:

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

   Read barriers are a neat trick, but for real-time applications
replacing a boolean with a pointer and... is totally intolerable.  I
have used algorithms in this class in real-time systems, and although
we devoted a whole page to each bit-vector, the typical maximums are
on the order of a few hundred bits.  But the difference between say 5
clocks and 20 (clearing two words at a time) is crucial.

    So yes, you are correct that these algorithms can be replaced by
more complex versions without the special memory clearing instruction,
but the large constant multiplier makes that approach useless.  To
give a real world example, in one application, if all the time
available was assigned to the innermost loop of an N^2 lg2 N
algorithm, you had 25 clocks per iteration--and a cache miss could
take most of that.  Fortunately I found an algorithm which met the
theoretical complexity limit, and where the all the inner loop did was
set a bit-vector of length N to false.  In that case limiting the size
of the bit-vector (so I could keep it in a register pair and avoid
write throughs) was sufficient.

--

					Robert I. Eachus

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