macrakis@HARVARD.HARVARD.EDU (Stavros Macrakis) (04/02/86)
A few weeks ago, there was a query about garbage collection in Ada.
I've assembled a few notes on the subject.
Several Ada systems appear to have garbage collectors (GC) in
development environments (e.g. Rational, Symbolics). As far as I have
been able to ascertain, no production Ada environment provides garbage
collection in the target computer.
The usual argument is that embedded applications shouldn't GC, because
GC is inefficient and episodic. This is spurious for several reasons:
1. Prototypes and early development versions may prefer to sacrifice
efficiency for simplicity and speed of programming.
2. Many Ada applications will in fact not be embedded.
3. If you have GC, it is very easy to add a capability to detect and
report undeallocated objects and dangling pointers.
4. Embedded applications may even want GC. Traditional episodic GC
will do for some; others will need real-time GC algorithms.
5. GC may not be as expensive as is thought, especially if currently
known advanced implementation techniques are used.
6. Given Ada's typing, scoping, and tasking, much processing can
continue even during episodic GC.
However, implementing a GC for Ada is not entirely trivial. Although
Ada's semantics certainly allow GC, some compiler-writers may have
chosen runtime models which make it impractical or impossible. Not
only must pointers in memory be traceable, but transient `hazards'
must be avoided. The conditions are even more stringent for
relocating/compacting GC, of course.
The only current compilers I know the internals of, the Intermetrics
Byron Ada compiler family, have their runtime model carefully designed
to in fact make GC practical. However, no customer so far has
specified GC. I'm sure Intermetrics would be happy to sell a GC
option as soon as the market demand became sufficient.
-s
Stavros Macrakis
Harvard Univ. and Intermetrics, Inc.RCONN@SIMTEL20.ARPA (Rick Conn) (04/02/86)
There is a simple garbage collector written in Ada in the
repository in PD:<ADA.COMPONENTS>GARBAGE*.*; data:
%4 Garbage_Collection
Author : Doug Bryan
: Computer Systems Lab
: Stanford University
Machine/System Compiled/Run on :
Data General MV/10000 running the Ada Development Environment 2.2
Keywords : MEMORY, GARBAGE, GARBAGE COLLECTION
Abstract :
This is a generic garbage collector. It simply maintains an internal
linked list of items which have been freed then reuses these items when more
are needed.
-------macrakis@HARVARD.HARVARD.EDU (Stavros Macrakis) (04/02/86)
`Garbage collection' (GC) has been used in more than one sense in
this discussion. Several contributors equate GC with `storage
reclamation'. This is misleading. The essence of GC is finding free
space by determining what access objects remain in use.
GC is a particular type of automatic storage reclamation -- reference
counting, e.g., is another. And explicit deallocation or deallocation
of stack frames at scope exit time is simply not automatic storage
reclamation. Neither is deallocating an entire collection at the exit
of the scope declaring the type. All of these are useful techniques,
but they are not GC. GC has different advantages and disadvantages
than each of these other methods.
It is not possible to write a garbage collector within Ada (unless, of
course, you have hooks into the implementation). It is not even
possible to define a private type which reclaims its own space within
Ada. The essential problem is that there is no way of determining the
``immediately accessible nodes'' in Knuth's ("Art") terminology, i.e.
the variables containing access values. It would be possible to
define a limited type that used GC or ref counting if there were a
finalization operation (see Schwarz&Melliar-Smith, ``The Finalization
Operation for Abstract Types'' ICSE/5, p273).
For a discussion of issues relating to GC implementation in an
Ada-like environment, see Susan Owicki, ``Making the World Safe for
GC'' in POPL/8, p77.
The term `Garbage collection' has had a precise meaning for over
twenty years. Here are some citations:
J.McCarthy et al, "Lisp 1.5 Programmer's Manual" (2nd ed, 1965) p105:
garbage collector: The routine in LISP which identifies all active
list structure by tracing it from fixed base cells and marking it,
and then collects all unneeded cells (garbage) into a free-storage
list so that these words can be used again.
Knuth, "Art" (1st ed, 1968), sec 2.5B p438:
...a policy of simply doing nothing until space runs out, then
searching for all the areas currently in use and fashioning a
new AVAIL list.
Aho&Ullman, "Principles of Compiler Design" (1st ed, 1977) p44:
A garbage collection scans all records, determining which are in
use, and making an <available space list> of those which may be
reused.
Note that "garbage collection" has been used in many systems other than
Lisp with the same meaning: Snobol, ECL, MIT Teco (!), ....
-s
ICSE = Intl. Conf. on Software Engineering
POPL = Principles of Programming Languages (Conf.)RCONN@SIMTEL20.ARPA (Rick Conn) (04/04/86)
The basic goal of GC is to reclaim space that is no longer needed for one purpose and allow said space to be used for something else. For an application program, this can be done by the opsys, which I believe is the focus of your message, but it can also be done by the application itself. In both cases, the desired effect, viz the utilization of less space by the application, is achieved. This is why I feel that the GARBAGE component is viable ... and it offers a solution now, rather than later. Rick -------