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=-2.9 required=5.0 tests=BAYES_00,MAILING_LIST_MULTI autolearn=unavailable autolearn_force=no version=3.4.4 X-Google-Thread: 103376,21960280f1d61e84 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news4.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!newsfeed00.sul.t-online.de!t-online.de!tiscali!newsfeed1.ip.tiscali.net!proxad.net!cleanfeed3-b.proxad.net!nnrp12-1.free.fr!not-for-mail Return-Path: From: "Randy Brukardt" To: Subject: RE: How come Ada isn't more popular? Date: Fri, 9 Feb 2007 19:31:58 -0600 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.6604 (9.0.2911.0) In-Reply-To: <9rveib56n0.fsf@hod.lan.m-e-leypold.de> X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1807 Importance: Normal X-Trash-Finder: Limited filtering for message, local (outbound) source X-Virus-Scanned: amavisd-new at ada-france.org X-BeenThere: comp.lang.ada@ada-france.org X-Mailman-Version: 2.1.9rc1 Precedence: list List-Id: "Gateway to the comp.lang.ada Usenet newsgroup" List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.ada Message-ID: X-Leafnode-NNTP-Posting-Host: 88.191.17.134 Organization: Guest of ProXad - France NNTP-Posting-Date: 10 Feb 2007 02:35:01 MET NNTP-Posting-Host: 88.191.14.223 X-Trace: 1171071301 news-1.free.fr 425 88.191.14.223:46958 X-Complaints-To: abuse@proxad.net Xref: g2news2.google.com comp.lang.ada:9219 Date: 2007-02-10T02:35:01+01:00 Markus E Leypold writes: > "Randy Brukardt" writes: > >> Maciej Sobczak writes: > >> > Still, there is a strong argument is that for some class of algorithms it > >> > might be beneficial to be able to "drop on the floor" a bigger part of the > >> > graph altogether. [...] Reclaiming that abandoned part might require > >> > implementing the same tracking logic that GC already provides out of the box > >> > and therefore the argument goes that the use of off-the-shelf GC can be > >> > beneficial for the memory-management aspect of such an algorithm. (Any > >> > thoughts on this?) > >> > >> My thoughts: not "might", but "definitely". Also, the advantage is not > >> restricted to some class of algorithms -- it is in fact the common case. > > > > YMMV, of course, but it's not my experience. It's rare to destroy only part > > of a data structure; it's usually the entire structure that needs to be > > discarded. > > "it's usually the entire structure" => In a world without > representation sharing. In one with representation sharing (and that > makes the production of new trees from existing ones really > efficient), one would have to traverse the whole subtree any time a > tree referencing this subtree is deleted - if only to adjust the > reference counters. In a world with GC you just overwrite one > reference to some subtree. When the GC hits it just traverses the tree > once (and then perhaps decides which parts to deallocate). Dependend > on the application domain (e.g. if you produce and drop many shared > representions between GC cycles) that might be much more efficient. In an imperative language like Ada (and this *is* the Ada newsgroup!), representation sharing has to be done completely behind an abstraction that presents the appearance of deep copying (that is, no sharing). Anything else is a receipe for bugs, as modifications occuring to one tree that magically appear in another (supposedly independent) cannot be tolarated. The net effect is it can be used only in limited ways. That's not horrible, since one of the goals of Ada is to provide the ability (not the requirement, remember) to get the performance level of the machine. For that to be possible, you cannot have distributed overhead (that is, overhead from features that you don't use). Deep copying of trees has unacceptable overhead, as you note. But GC has a non-zero overhead on every reference in the program. That too can be an unacceptable overhead - thus it cannot be mandated on all types. > >> You don't need a complex mesh for this kind of advantage to kick in, even > >> regular tree cleanup is greatly simplified: just let go of the > >> subbranch you no longer need, and avoid that whole cleanup traversal. > > > > I'm primarily interested in destroying the entire structure, and often I > > need no destruction at all: the structures exist until the termination of > > the program. > > This certainly is a special case? E.g a chess playing program (any > playing program) would have to create and destroy game trees at a > pretty good rate. I doubt that very much, at least one that is trying to maximize the "thinking". This is a very performance dependent application, and "creating" and "destroying" much of anything is likely to be overhead that you can't afford. I haven't written a Chess playing program, but I have written Freecell and Solitare solvers (and, in the more distant past, programs for playing Othello and a couple of other games). I'm pretty sure I've never created or destroyed any trees. The Freecell solver is based on queues of pending moves to try. The queues are implemented mainly with lists of arrays; the queue blocks are never destroyed and new ones are allocated only if there are no unused ones to use. Moves in the queues are ordered by heuristics so the most likely ones that lead to a solution are tried first. Positions are stored (compressed) in a large hash table in which each bucket is a pointer to an array which is allocated from a custom storage pool that directly uses Windows memory management (and supports expansion with a special call). It can solve most initial positions in under a minute on a 500 MHZ machine with 256Meg memory (harder ones take longer, possibly much longer). > > There's no point of earlier cleanup in such programs, and > > surely no point in non-zero overhead to support such cleanup. I'm not aware > > of any zero-overhead GC algorithm, because the basic tenet of GC is that you > > can find all reachable objects: doing that requires some time and/or space > > overhead. > > I can imagine to allocate some memory in a special, non garabage > collected heap. Furthermore generational garbage collection AFAIK has > the property to touch old objects seldom -- so there is not so much > cost (as it might seem at first glance) for keeping large structures > around unchanged. And if the program is short running you could also > increase the garbage collection threshold(s), so that the collection > never sets in. The overhead of GC that I'm worrying about here is not that of the collector itself (which is trivial in this case because nothing will need to be collected), but rather the part that is usually hand-waved in GC papers: determining what is actually reachable. This is a non-trivial exercise which requires time and space overhead for every reference - whether or not it will ever be possible to collect anything. As Ray said, you could argue whether or not GC should be the default. It's not an argument for Ada -- it isn't the default, and would never be the default simply because making existing programs run slower is not an option in all but the most serious cases. I could see a predefined GC storage pool being added to the language, or something like that. But the language would need other fixes to really allow GC (although I doubt anyone will stop you from implementing a GC in Ada, it's likely to be wrong in some subtle - some would say pathological - cases). Randy.