Re: How come Ada isn't more popular?


"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.


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.

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.

Regards -- Markus
.

Relevant Pages

  • LOS Optimization Using Binary Tree Structures (with demo)
    ... fast way to calculate LOS using a binary tree (properly called a binary ... describe the visibility-dependency between tiles - as in describing ... Using octants ... The cool thing about using a relational-based LOS algorithm is that you ...
    (rec.games.roguelike.development)
  • Re: Question about decision tree algorithm in sqlserver2000
    ... If your target, on the other hand, is continuous, the algorithm will build regression trees that have regression formulae in nodes and leaves. ... if your target is continuous (i.e. a regression tree) than the lift chart is replaced by a scatter plot ...
    (microsoft.public.sqlserver.datamining)
  • Re: Question about decision tree algorithm in sqlserver2000
    ... if my target is discrete, the algorithm will ... build a classification tree. ... if your target is continuous (i.e. a regression tree) than the lift chart is replaced by a scatter plot ...
    (microsoft.public.sqlserver.datamining)
  • Ultimate, God-like Algorithm
    ... An infinite tree is described by including "self references" in place ... self reference makes the tree infinite. ... believe that I have an algorithm that can show equality in m * n time. ...
    (sci.math)
  • Comparing 2 Infinite Trees
    ... An infinite tree is described by including "self references" in place ... self reference makes the tree infinite. ... believe that I have an algorithm that can show equality in m * n time. ...
    (sci.math)