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-Thread: 103376,21960280f1d61e84 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Newsgroups: comp.lang.ada Subject: Re: How come Ada isn't more popular? References: From: Markus E Leypold Organization: N/A Date: Sat, 10 Feb 2007 03:18:41 +0100 Message-ID: User-Agent: Some cool user agent (SCUG) Cancel-Lock: sha1:FsexXBIYG0MMjb9UQ2Z/zEM7jOE= MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii NNTP-Posting-Host: 88.72.200.144 X-Trace: news.arcor-ip.de 1171073608 88.72.200.144 (10 Feb 2007 03:13:28 +0200) X-Complaints-To: abuse@arcor-ip.de Path: g2news2.google.com!news3.google.com!news4.google.com!border1.nntp.dca.giganews.com!nntp.giganews.com!newsfeed00.sul.t-online.de!t-online.de!news-lei1.dfn.de!news-fra1.dfn.de!newsfeed.arcor-ip.de!news.arcor-ip.de!not-for-mail Xref: g2news2.google.com comp.lang.ada:9247 Date: 2007-02-10T03:18:41+01:00 List-Id: "Randy Brukardt" writes: > 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!), Yes, yes. But I *had* the impression that we're now talking about languages in general and general purpose languages. We've come to that point from the discussion what distinguishes other contenders from Ada, which in turn came from the question "Why isn't Ada more popular?". Now we are discussing the up and downs of GC and those opposed on GV discuss the problems on general ground -- I wonder why I should now discuss the merits only on the grounds of how that would fit into Ada :-). > representation sharing has to be done completely behind an abstraction that > presents the appearance of deep copying (that is, no sharing). Right. I've been talking about the implementation of this sharing, how using representation sharing with reference counting compares with using it in a GC'ed system. I hope I've expressed myself clearly there, since I hate to be criticized for errors I didn't make. So the following doesn't apply to what I said ... > 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 I did not talk about deep copying. Yes, it's unacceptable, but that was taken as a given, I didn't discuss it. The problem I have been talking about was the necessity of maintaining reference counters, but I was wrong concerning the traversal (its not necessary, I've not been paying attention, but after all that is not what you're criticizing ... :-) Still, AFAIK ref counting is less efficient than other GC algorithms, but I'd like to point out, that ref counting is essentially a specialized GC. > non-zero overhead on every reference in the program. That is true. I suggested, though, that in generational GC the overhead is not as large as it seems at first (long living structures are less frequently traversed) and it would be possible to specially allocate such structures outside the heap (my approach is somewhat inverted from yours or Maciej's: I'd have GC as the default and scope bound or manually managed memory allocated outside the GC'ed heap. > That too can be an unacceptable overhead - thus it cannot be > mandated on all types. The limits, where "unacceptable" begins, vary. I doubt that many that discuss GC as having way too much overhead actually have these requirement. > >> >> 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 think you're wrong, but I'm also sure other examples can be found. Your position basically boils down to: Memory needs hardly ever be deallocated and you can always leave it to the operating system to destroy non-scoped memory. I don't think this position is really tenable in general, but I don't see an approach to decide it (here). All we can do, is to insist that our respective experience suggests it. > 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. Good. I do think this is a bit different from chess (the tree of positions is actually the call tree of functions, which means, positions in the future have to be recreated at every draw. I just suspect that is not what one wants when playing chess or GO) -- but I don't want to open up another avenue of discussion. > 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. I'm talking about exactly this: The process of determining what is reachable. This involves traversing heap allocated memory and the effort is (roughly) proportional to the allocated memory in the heap. If there is no memory in the heap (no allocated blocks), there is no overhead for traversal. So moving your large static structures from GC'ed heap > 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. I _do_ think that this concern for overhead in most cases is a case of premature optimization. As I already noted in this thread: For all the increase in processing power we have seen in the last decades I once would like to buy myself the convenient luxury of using GC because it's easier on the developer (candy for developers). For once I don't want to see that processing power go into useless blinking and flickering of smooth GUIs (candy for users). After all the users (indirectly) pay the development time and it's their money that is being saved if the developers spent less time with getting the memory manangement right. BTW: Hoe large is the overhead really? Performance of OCaml compared with C++/C compiled by Gcc suggest a factor of 2, measurements performed by J Skaller suggest a factor of around 1.2 - 1.5 at first glance for computation. > 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 Yes, the discussion is seriously OT, since we are mostly not discussing how GC will be supported in Ada in future (or not), but the general merits of GC. > 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). Yes. Despite the standard allowing GC, it doesn't align too well with the rest of Ada. Regards -- Markus