Re: How come Ada isn't more popular?


"Randy Brukardt" <randy@xxxxxxxxxxxxxx> writes:

Markus E Leypold writes:
"Randy Brukardt" <randy@xxxxxxxxxxxxxx> writes:
Maciej Sobczak <no.spam@xxxxxxxxxxx> 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

.

Relevant Pages

  • Re: Memeory management
    ... I did not allocate and deallocate memory ... A particular Ada compiler, with a particular set of compile options, ... Var2 at the beginning and deallocate on exit. ...
    (comp.lang.ada)
  • Re: "new" word
    ... > "Usually you allocate memory with the Ada new statement. ... Taken as a statement about Ada, ... However, if you're implementing Ada on an operating system, ...
    (comp.lang.ada)
  • Re: find -exec surprisingly slow
    ... > somewhere in the vicinity of 400K files in it. ... The overhead for starting new ... There is however an upper limit to how much memory will be used ...
    (freebsd-questions)
  • Re: JRuby disabling ObjectSpace: what implications?
    ... it depends on the overhead and on the invocation model. ... sound more like there is one JVM for JRuby programs... ... the way they do (object references are no pointers to memory locations). ... You just traverse the list ...
    (comp.lang.ruby)
  • Re: Another New Hardware Thought
    ... which adds data copy, interrupt, and context switching overhead. ... memory manager would become complex enough to be half an OS in its own ... On a machine with 4mb of RAM, ... Then you have the realtime cost of swapping itself, ...
    (comp.sys.apple2)