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=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,29850945228df59 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2003-06-17 22:57:10 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!logbridge.uoregon.edu!arclight.uoregon.edu!wn13feed!wn12feed!worldnet.att.net!204.127.198.203!attbi_feed3!attbi.com!rwcrnsc53.POSTED!not-for-mail Message-ID: <3EEFFF10.4040302@attbi.com> From: "Robert I. Eachus" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.0.2) Gecko/20021120 Netscape/7.01 X-Accept-Language: en-us, en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Boehm-Demers-Weiser conservative garbage collector and GNAT References: <1316747.mXveBPtf0Z@linux1.krischik.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit NNTP-Posting-Host: 24.62.164.137 X-Complaints-To: abuse@attbi.com X-Trace: rwcrnsc53 1055915829 24.62.164.137 (Wed, 18 Jun 2003 05:57:09 GMT) NNTP-Posting-Date: Wed, 18 Jun 2003 05:57:09 GMT Organization: AT&T Broadband Date: Wed, 18 Jun 2003 05:57:09 GMT Xref: archiver1.google.com comp.lang.ada:39373 Date: 2003-06-18T05:57:09+00:00 List-Id: Larry Kilgallen wrote: > Garbage collection is important to particular problem domains like AI. > People who need it do not appear to be a significant portion of the > Ada-using public. This is just plain wrong. There may be some portion of the general programming world that needs a generalized garbage collector. But AI is not it. I wrote a reference counting package in Ada for an AI project that thought they needed a garbage collector that would run in a background task so that their code was not subject to garbage collection delays at arbitrary places. I showed that the requirements for the GC they were asking for couldn't be met that way but a one page package could do exactly what they needed via reference counts. Yes, I know that "ordinary" reference counting can't deal with circular chains. But it turned out that for their data, there was an easy way to deal with that issue, using that low priority task they wanted. This was a data fusion AI for a radar net. In theory circular references could occur and result in garbage that required that background task to collect it. But the system was nicely instrumented, and during the entire formal qualifaction period the background task collect zero objects. Several hundred million of course were dealt with in real-time with guaranteed behavior. The system had I think, 20,000 potential objects in the pool (all were fixed size). The maximum reached during the qual testing was seven thousand something with a set of test data from the LA area. Oh, and the code was around four pages, one for the package spec, two for the body, plus one for the background task. The way it worked was that every every pointer object contained a level which was in some sense how far it was from the root pointer. Every data object contained two values, the object's level, the count of pointers from objects at the next higher level. If an object was pointed to by a new reference from a higher level object, its level was raised, and a treewalk was done by the background task to reset the levels of other objects. If you think about it for a minute you will see that hoisting a object sets the count of pointers from higher levels to one. If an object reached a reference count of zero, it was put on a list to be potentially discarded. Well, actually there was a global flag. If it was set to false, there were no objects in the treewalk, and garbage could be discarded immediately. If it was true, the backgound task was doing a treewalk, and objects had to be put on a potential holding list. In practice, in this application the flag was almost never true. Setting it to true occured only during a rendezvous between the two tasks. Setting it to false was not a synchronizing event. It would probably be easier to recreate the code than describe it. So to sum up: 1) In Ada, any thought that you need garbage collection indicates you should be using a container class. 2) Writing the container class in Ada is a pretty simple job, if one doesn't already exist. 3) No container class needs to have "full" garbage collection provided by the environment. 4) Unchecked_Deallocation means that the designer of the container class does the checking, and usually provides--if necessary--a Free operation that does the right thing. Whatever that may be. 5) For most programers, learning when to use Ada.Strings.Unbounded is the closest they will ever come to garbage collection.