From 6477156834914459504 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: 1014db,9292211c2d4756a8 X-Google-Attributes: gid1014db,public X-Google-Thread: 1108a1,9292211c2d4756a8 X-Google-Attributes: gid1108a1,public X-Google-Thread: f78e5,9292211c2d4756a8 X-Google-Attributes: gidf78e5,public X-Google-Thread: 103376,48b89668821c1c9f X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 1995-01-23 09:06:40 PST Path: nntp.gmd.de!newsserver.jvnc.net!nntpserver.pppl.gov!princeton!gw1.att.com!csn!ncar!gatech!howland.reston.ans.net!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++...?) Followup-To: comp.lang.c++,comp.lang.c,comp.object,comp.lang.misc,comp.std.c++,comp.lang.ada Date: 23 Jan 1995 17:06:40 GMT Organization: The Mitre Corp., Bedford, MA. Lines: 54 Distribution: world Message-ID: References: <787227087snz@wslint.demon.co.uk> <3ckb8g$841@gateway.wiltel.com> <19950122.094355.149517.NETNEWS@UICVM.UIC.EDU> NNTP-Posting-Host: spectre.mitre.org In-reply-to: dhanley@matisse.eecs.uic.edu's message of Sun, 22 Jan 1995 02:56:58 +0000 Xref: nntp.gmd.de comp.lang.c++:87648 comp.lang.c:75403 comp.object:19934 comp.lang.misc:10476 comp.std.c++:11233 comp.lang.ada:18216 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...