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: 1014db,9292211c2d4756a8 X-Google-Attributes: gid1014db,public X-Google-Thread: f78e5,9292211c2d4756a8 X-Google-Attributes: gidf78e5,public X-Google-ArrivalTime: 1995-01-19 19:49:57 PST Newsgroups: comp.lang.c++,comp.lang.c,comp.object,comp.lang.misc,comp.std.c++,comp.lang.ada Path: pad-thai.cam.ov.com!bloom-beacon.mit.edu!spool.mu.edu!howland.reston.ans.net!ix.netcom.com!netcom.com!NewsWatcher!user From: hbaker@netcom.com (Henry Baker) Subject: Re: Parallel & RT GC (was Re: Real-Time GC (was Re: Widespread C++...?) Message-ID: Sender: hbaker@netcom.com (Henry G. Baker) Organization: nil 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> <3fmgbn$rns@watnews1.watson.ibm.com> Date: Fri, 20 Jan 1995 02:20:30 GMT Xref: pad-thai.cam.ov.com comp.lang.c++:69978 comp.lang.c:58298 comp.object:15686 comp.lang.misc:6827 comp.std.c++:9130 comp.lang.ada:14468 Date: 1995-01-20T02:20:30+00:00 List-Id: In article <3fmgbn$rns@watnews1.watson.ibm.com>, ncohen@watson.ibm.com wrote: > In article , > 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.)