[comp.lang.modula2] Garbage Collection

sommar@enea.se (Erland Sommarskog) (03/15/88)

Edmund E Howland (cbseeh@fang.ATT.COM) writes:
>Huh?
>Since when have these three ever had a need for garbage collection?
>I am not too familiar with Ada, but garbage collection exists in
>languages for whom dynamic binding is a way of life, not an option.

If I define and implement a package for a data type of some sort in 
Ada I can hide the implementation of the type, just providing a set
of operations. At a later state I can change the implementation without
affecting the interface. 
  However, I must already in the first step, decide whether objects of 
this type should be dynamic or not. Not so much for a allocation routine, 
you quite often need an initiation routine, anyway. But do I need a 
deallocation routine? If there is garbage collection, I don't have to 
think of this problem.
  Yes, I can one there just in case, but then the calling units have to
bother about using them, which may require a lot of clean-up code, which
might be totally unnecessary.

Generally, garbage collection is a must in object-oriented programming.
(No, I don't belive Ada is a true OO-language.)

-- 
Erland Sommarskog       
ENEA Data, Stockholm        
sommar@enea.UUCP           "Si tu crois l'amour tabou...
                            Regarde bien, les yeux d'un fou!!!" -- Ange

nagler%olsen@unizh.UUCP (Robert Nagler) (03/23/88)

> From Erland Sommarskog
> Not so much for a allocation routine, you quite often need an
> initiation routine, anyway. But do I need a deallocation routine?
> If there is garbage collection, I don't have to think of this problem.
...

Automatic garbage collection (AGC) is not the answer to all memory
allocation problems.  Cedar (from Xerox) is a typical structured language
which has AGC.  I have read articles on Cedar (never used it) and
they say that allocators and deallocators are *required* for circular
data structures, e.g. trees with "parent-links", doubly-linked lists,
circular lists, etc.  Another problem with AGC is that it consumes
CPU time.  If you are writing real-time applications (often what Modula-2
is used for), this can be annoying and dangerous.

Although many objects in programs are "just memory", some objects are
connected to other real-world entities, e.g. files, devices, etc.
With these objects, you always need a instantiation and destruction routine,
because they must open/close files, turn-on/off interrupts, etc.  AGC
doesn't even solve these problems.

With all this talk about AGC, no one is discussing the *need* for it.
My experience with AGC is that is required for applications which run
for extended periods of time or do lots of allocation and deallocation.
For example, if you are writing an operating system kernel, you don't
want it to lose memory.  However, if you are writing a compiler, it is
*ok* if it loses memory, because the whole memory space is wiped away
when the compiler exits after a few minutes at most.  Languages like Lisp
do a lot of allocation and deallocation, because the coding style requires
it.  In Modula-2, this is less often the case and in most of the code
I have seen, there is little dynamic memory allocation (here "little"
means 100K or so).  The primary reason for this is the lack of object-
oriented libraries available, e.g. ones that provide ADTs like lists.

> Generally, garbage collection is a must in object-oriented programming.

We have developed a real-time distributed information system consisting of
about 150K lines of code in 500 modules (or so).  Development time
was about a year and a half.  Coding and testing took about 9 months.
The software runs non-stop (excepting bugs and reconfiguration).  Some
of the processes have run for weeks.  We don't have memory leakage problems.
*All* of our software is object-oriented.  We program with Modula-2 as it
was intended to be programmed and we don't try to simulate Ada or Lisp
(although we borrow ideas occasonally).

> From Snorri Agnarsson:
> Not true.  It is not possible in general to "roll-your-own" in a
> satisfactory manner.  ... abstraction garbage collection is a necessity.

Somehow, I think you will be difficult to satisfy, but here goes:

The example of Modula-2 list code you gave seems kind of like Lisp and not M2.
>        X := CONS(Y,Z);
>        X := HEAD(Y);
>        X := TAIL(Y);

The first question I ask is: what does it do?  Program fragments taken
out of context are always difficult, but this piece of code is beyond me.
Why would anyone construct a list he never uses?  Why would he get tail
and head into a variable and not reference them?

We have a module called lists.  A typical usage is:
    Lists.MakeFirstNext( elements );
    WHILE Lists.Next( elements, element, data ) DO
        (* Do something with "element" and "data" *)
    END; (* WHILE *)

You might want to insert into the list:
    Lists.Insert( elements, newElement, itsData );

You might want to delete an element from a list:
    IF Lists.Find( elements, element, data ) THEN
        Lists.DeleteCurrent( elements );
    END;

The Lists module supports an abstraction of lists which is useful
in Modula-2, but maybe not Ada or Lisp.  You create a list by saying:
    Lists.Create( elements, Lists.typeCard, Lists.stack );
You can have sorted (forward and reverse) lists and also queues.
Importers can create new types easily (typeCard seemed like an
obvious built-in).

This simple module handles a majority of our M2 list processing code.
If special list processing or very high performance is required
(e.g. ready queue processing), we copy code and adapt it to the
special needs.  I've included a bastardized def mod (at the end of
this message) to give you an idea of what our Lists module is like.

BTW, you could implement a garbage collecting Modula-2 implementation,
but no one has bothered to do it.  The code to manage it is large
and often takes advantage of special hardware which makes it non-portable.

Object-oriented programming is a state of mind not a language feature.
I've found many people talk about it, but very few people are really
willing to commit to it.

Rob Nagler
mcvax!olsen!nagler@uunet.uu.net
------------------------------------------------------------------
Disclaimer:
    This module is a very much abbreviated version of Lists.  There
    are many features and comments which I have edited out, because
    they would add nothing to the discussion.  The real implementation
    and definition will be available in our ``soon-to-be-released''
    public domain library.

    For those backwards M2 implementations that only support SYSTEM.WORD,
    this module will still work, but you will have to change SYSTEM.BYTE
    to SYSTEM.WORD.  This implementation is in heavy use with Sun Modula-2
    and Logitech Modula-2/86.

DEFINITION MODULE Lists;
(*
 * Provides a simple method for managing lists of "keys".  One can specify
 * either sorted (reverse or forward), queued (FIFO), or stacked (LIFO)
 * orderings.  Keys need not be unique, but they must be non-zero in length.
 * This is a generic module, that is, you must provide a specific "type"
 * for the keys in the list.  The types are specified at run-time.
 *)
TYPE
    Object;     (* A list *)
    Orderings = (
        forwardSorted, (* the lesser keys are returned first *)
        reverseSorted, (* the greater keys are returned first *)
        queue,         (* first key Inserted, first returned by Next *)
        stack          (* first key Inserted, is the last returned *)
    );
PROCEDURE Create(
    VAR list          : Object;         (* "in" value is ignored *)
        typeName      : ARRAY OF CHAR;  (* must be registered *)
        howToTraverse : Orderings       (* How to go about finding things *)
    );
PROCEDURE Destroy(
    VAR list : Object   (* deallocates list and its elements, but not impObjs *)
    );
PROCEDURE Insert(
    list           : Object;               (* Must be a valid list *)
    key            : ARRAY OF SYSTEM.BYTE; (* to be inserted *)
    importerObject : SYSTEM.ADDRESS        (* data value associated with key *)
    );
PROCEDURE DeleteCurrent(
    list : Object       (* "current" must be valid *)
    );
PROCEDURE Find( (* key in list and set "current" *)
        list           : Object;                (* must be valid *)
        key            : ARRAY OF SYSTEM.BYTE;  (* set to "current" *)
    VAR importerObject : SYSTEM.ADDRESS         (* found data value *)
    )                  : BOOLEAN;  (* FALSE => not found; impObj invalid *)

PROCEDURE Next( (* traverse element after "current" or "first" *)
        list            : Object;               (* traverse *)
    VAR key             : ARRAY OF SYSTEM.BYTE; (*
    VAR importerObject  : SYSTEM.ADDRESS
    )                   : BOOLEAN;

PROCEDURE MakeFirstNext( (* first element in list will be returned by "Next" *)
    list : Object       (* Must be valid list *)
    );

(* Registering new types *)
TYPE
    AssertProc = PROCEDURE (
        SYSTEM.ADDRESS  (* pointer to object to be assertion checked. *)
    );
    CompareProc = PROCEDURE (
        SYSTEM.ADDRESS, (* pointer to "left" side of comparison *)
        SYSTEM.ADDRESS  (* pointer to "right" side of comparison *)
    ) : Intrinsics.CompareResults;

PROCEDURE Register( (* a new type with this module for use by others *)
    typeName    : ARRAY OF CHAR; (* must be unique *)
    assertProc  : AssertProc;    (* Procedure to check inserted values *)
    compareProc : CompareProc;   (* For sorting and finding *)
    keySize     : CARDINAL       (* SYSTEM.TSIZE( Type ) *)
    );
END Lists.

snorri@rhi.hi.is (Snorri Agnarsson) (03/29/88)

From article <8803231100.AA08757@klaus.olsen.uucp>, by nagler%olsen@unizh.UUCP (Robert Nagler):
>> From Snorri Agnarsson:
>> Not true.  It is not possible in general to "roll-your-own" in a
>> satisfactory manner.  ... abstraction garbage collection is a necessity.
> 
> Somehow, I think you will be difficult to satisfy, but here goes:
> 
> The example of Modula-2 list code you gave seems kind of like Lisp and not M2.
>>        X := CONS(Y,Z);
>>        X := HEAD(Y);
>>        X := TAIL(Y);
> 
> The first question I ask is: what does it do?  Program fragments taken
> out of context are always difficult, but this piece of code is beyond me.

The point I'm trying to make is that I don't want to call anything list
processing that does not allow you to write code such as the above and
not worry about eating memory.  The usual definition of CONS, HEAD and TAIL
is that the following equations apply for all X and Y:

	X=HEAD(CONS(X,Y))
	Y=TAIL(CONS(X,Y))

In a real list processing language you should be able to create values
such as CONS(X,Y) and return them as values from a function, discard the
values if you wish without having to deallocate them explicitly, for example
by using the value temporarily in the middle of an expression.
You will also be able to share parts of lists without having to remember
which parts can safely be deallocated and so on.

> 
>  We have a module called lists.  A typical usage is:
>     Lists.MakeFirstNext( elements );
>     WHILE Lists.Next( elements, element, data ) DO
>         (* Do something with "element" and "data" *)
>     END; (* WHILE *)
> 
> You might want to insert into the list:
>     Lists.Insert( elements, newElement, itsData );
> 
 .... long code for module called lists



You can call this module "Lists" if you wish, you can even call this
list processing if you wish, but *I* would not call this list processing.
It seems to me a better name for this module would be "Table".


-- 
Snorri Agnarsson                  Internet:  snorri@rhi.hi.is
Raunvisindastofnun Haskolans      uucp:      ...!mcvax!hafro!krafla!snorri
Dunhaga 3 107 Reykjavik ICELAND

g-rh@cca.CCA.COM (Richard Harter) (03/31/88)

In article <628@ra.rice.edu> boehm@titan.rice.edu (Hans Boehm) writes:

>  My experience is that any attempt at manipulation of interesting linked
>structures in a language that doesn't support real automatic storage
>management will either fail, or waste large amounts of debugging time.
>(My experience includes a (working) 40,000 line compiler, written in C, that
>manipulates a reference counted syntax "tree", or more accurately, a
>reference counted syntax graph.)  Normally, it is extremely difficult
>to track down bugs created by premature deallocation.  When such bugs are
>finally removed, the resulting programs normally include a substantial
>number of storage leaks.
>  Some recent experiments by Mark Weiser and myself with retrofitting a
>garbage collector to existing C programs, verify the latter point.
>(The garbage collector should never free anything since that was the
>programmers responsibility.  It does.  In other people's code.
>Our paper on this should appear in Software P&E shortly.)
>Mike Caplinger reported similar results for another application at the last
>USENIX conference, I believe.  We have resurrected C code with storage
>management bugs by linking it against a garbage collector (which in the case
>of C doesn't always work either, but it has a better track record than manual
>storage management).

	There is problably something I am missing, but I don't quite see
how you can implement garbage collection in C without collateral assumptions
-- how is the garbage collector supposed to know that that a block is free?

	Your main point is certainly true - manual allocation and deallocation
with the programmer being responsible for ensuring that all comes out right
really doesn't work very well.  This was a critical issue for us -- our
software has to run on systems which do not have pseudo-infinite memory
and it sometimes has to run for very long runs.  We can't afford memory
leaks (or premature deallocation).  What we did was to write our own
storage allocation package.  Salient features:

The allocation routine takes two arguments, a size and an ID.  The latter
is a unique integer specifying that particular call.  (We manage the ID list
manually.)  The allocator creates a node for each request block.  In this
node are sundry links, the ID, and (in effect) a date stamp.  There is also
a hash table that contains the address of every allocated block.  All allocator
control information is stored in a separate space from allocated memory itself.
(This eliminates a large class of mystery bugs associated with overwriting
allocator control data.)

The deallocation routine takes one argument, the address of the block being
returned.  The deallocation routine validates the address as being an
allocated address.  This eliminates another class of bugs caused by passing
an improper or stale address to the deallocation routine.

There is a facility for printing out a complete map of allocated memory
including call ID's and date stamps.  We use this, from time to time, to
check the code for storage leaks.

This scheme is not as good as automatic garbage collection, but we have
found it to be satisfactory.  
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.

boehm@titan.rice.edu (Hans Boehm) (04/01/88)

In reference to g-rh@cca.CCA.COM (Richard Harter)'s question:
>        There is problably something I am missing, but I don't quite see
>how you can implement garbage collection in C without collateral assumptions
>-- how is the garbage collector supposed to know that that a block is free?

  This is usually, but not always, possible.  The idea is to use a traditional
non-compacting mark-sweep collector.  On a UN*X system, we start by scanning
the registers, stack, data, and (statically allocated) bss segments for
any addresses of valid allocated objects.  We subsequently scan allocated
objects we find in the same way.  For a typical C program, all reachable
objects can be found in this manner.  (Storing exclusive or'ed pointer
values, tagged pointers, and similiar programming tricks, as well as some
rarely used (for C) compiler optimization techniques may break this scheme.)
  In theory, we may end up marking a few unreachable objects as reachable
as well, since integers may be misinterpreted as pointers.  The collector
can be designed so that the only result of this is excess storage retention.
(This does require that we don't compact.)  In my experience, I have never
seen any indication of such unnecessary retention in practice.  There is
an argument to be made that no garbage collector is completely immune
from this phenomenon.
  The fact that the collector has to perform a fairly complicated (but still
O(1)) check for pointer validity does slow it down a little.  On a Sun 3/260,
with a 2 Meg heap, half of which is in use, we normally see collection times of
about 3 seconds.  (This assumes longword aligned pointers and small data and
static bss areas.)  All of this is largely irrelevant if the
collector is used as a debugging tool to detect storage leaks.
  More details can be found in Mark Weiser's and my upcoming Software P&E
article entitled "Garbage Collection in an Uncooperative Environment".

Hans-J. Boehm
boehm@rice.edu

g-rh@cca.CCA.COM (Richard Harter) (04/01/88)

In article <632@ra.rice.edu> boehm@titan.rice.edu (Hans Boehm) writes:
>>        There is problably something I am missing, but I don't quite see
>>how you can implement garbage collection in C without collateral assumptions
>>-- how is the garbage collector supposed to know that that a block is free?

>  This is usually, but not always, possible.  The idea is to use a traditional
>non-compacting mark-sweep collector.  On a UN*X system, we start by scanning
>the registers, stack, data, and (statically allocated) bss segments for
>any addresses of valid allocated objects.  We subsequently scan allocated
>objects we find in the same way.  For a typical C program, all reachable
>objects can be found in this manner.  (Storing exclusive or'ed pointer
>values, tagged pointers, and similiar programming tricks, as well as some
>rarely used (for C) compiler optimization techniques may break this scheme.)

I see.  My block was in not thinking of the entire address space of the
program as accessible.  For our purposes it is not (we live in portability
land and are not allowed to do things like that :-)).  That is one reason
we did our own allocator (in C) -- it allows us to track down memory problems
portably.

I still don't see how a garbage collector helps with premature deallocation,
unless you scrap deallocation entirely, and rely entirely on garbage
collection.

The problem with garbage collectors in the old days was that they did
garbage collection when the available space was allocated.  This works
well enough until the actual amount of space allocated starts to approach
the amount of available space, and then the garbage collector starts
thrashing.  Is this a problem?  If not, how do you deal with it?
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.

boehm@titan.rice.edu (Hans Boehm) (04/02/88)

  Richard Harter writes:
>I still don't see how a garbage collector helps with premature deallocation,
>unless you scrap deallocation entirely, and rely entirely on garbage
>collection.

>The problem with garbage collectors in the old days was that they did
>garbage collection when the available space was allocated.  This works
>well enough until the actual amount of space allocated starts to approach
>the amount of available space, and then the garbage collector starts
>thrashing.  Is this a problem?  If not, how do you deal with it?

  Our current version of the collector doesn't help you with
premature deallocation.  Further instrumenting it might help.  For example,
you could use the marking algorithm to determine whether "free"d objects
really were inaccessible.  (This requires a coding style in which
unused references are explicitly cleared.  Replacing "free" by a
macro that clears its argument takes care of a lot of that and,
by itself, occasionally helps track down bugs.)  I don't have much experience
with this though.
  In non-real-time applications, we tend to use explicit deallocation where
it's easy to do, and let the collector take care of the error-prone cases.
  You are right in that the garbage collector code is not completely portable.
It should really be viewed as part of the run-time library, which is rarely
completely portable anyway.  Actually porting it isn't terribly hard.  There
is only about a screenful of machine dependent code in the collector.
The longest part of that deals with marking from the machine registers.
  Frequent collections in small address spaces can become a problem.
We operate in a virtual memory environment, so we deal with it by expanding
the heap size whenever a collection fails to return enough memory.  This
requires allocating a bit of extra memory.  For debugging, this hardly
matters.  (Memory is supposedly cheap.) In a production environment,
especially without virtual memory, it could be a problem.  On the other hand,
for some existing code, this can be much less significant than memory
otherwise lost to leaks.

Hans-J. Boehm  (boehm@rice.edu)

nevin1@ihlpf.ATT.COM (00704a-Liber) (04/05/88)

[followups to comp.lang.misc]

In article <26358@cca.CCA.COM> g-rh@CCA.CCA.COM.UUCP (Richard Harter) writes:
>	There is problably something I am missing, but I don't quite see
>how you can implement garbage collection in C without collateral assumptions
>-- how is the garbage collector supposed to know that that a block is free?

The only way to do this is to allocate a giant heap with malloc()
and do *all* the memory management on your own.  It is no different
than implementing in C or C++ a language that does automatic garbage
collection.

The problem I found with languages that do automatic garbage collection is
that there is no way for me to modify the implementation of the class (or
the type, for those of you unfamiliar with C++ lingo :-)) to make it better
suit my needs.

For applications where the programmer cost is greater than the run-time
cost (such as prototypes, personal tools, one-shot programs), I tend to use
languages with built in memory management.  For other applications, however,
I would rather use a language like C++ which allows me to change the
implementation of a class without affecting the rest of my code.
-- 
 _ __			NEVIN J. LIBER	..!ihnp4!ihlpf!nevin1	(312) 510-6194
' )  )				"The secret compartment of my ring I fill
 /  / _ , __o  ____		 with an Underdog super-energy pill."
/  (_</_\/ <__/ / <_	These are solely MY opinions, not AT&T's, blah blah blah

ncjuul@diku.dk (Niels Christian Juul) (12/27/90)

	     POSITION PAPERS ON GARBAGE COLLECTION ISSUES.
				FROM
	Workshop on Garbage Collection in Object-Oriented Systems.

The workshop was held in conjunction with the Joint ECOOP/OOPSLA'90 
Conference at Hotel Chateau Laurier, Ottawa, Canada on Sunday October, 
21st, 1990.

Most of the position papers from the workshop are now made available 
for anonymous FTP from  

	midgard.ucsc.edu (North America) in:  /pub/gc/
	(IP. 128.114.134.15)		 Only available until 1 Feb 1991
and
	ftp.diku.dk 	 (Europe) 	 in:  /pub/GC90/
	(IP. 129.142.96.1)		 Available until further notice.

Login as anonymous and state your own email-address as password.

THE PAPERS ARE SUBMITTED IN POSTSCRIPT FORMAT AND COMPRESSED.
TO PRINT THE PAPERS:

	uncompress xxxxx.ps.Z 
and
	lpr  xxxxx.ps		'on your favorite printer'

Further information on the individual papers are available by contacting the
appropriate authors; see list of attendees in file: Attendees.ps

In case of trouble you may contact:

	daniel@terra.ucsc.edu 	(Daniel Edelson)
or:
	ncjuul@diku.dk		(Niels Christian Juul)


Enclosed you find a list of the available position papers.
Good luck,	
1990.DEC.27.

		Daniel Edelson		&	Niels Christian Juul
		UCSC, CA, USA			DIKU, Denmark, Europe
-------------------------------------------------------------------------

CONTENTS:

	A Generational, Compacting Garbage Collector for C++
	Joel F. Bartlett, WRL/DEC, Palo Alto, CA, USA.

	Real-Time Compacting Garbage Collection
	Mats Bengtsson and Boris Magnusson, Lund University, Sweden.

	Experience with Garbage Collection for Modula-2+ in the Topaz 
	Environment
	John DeTreville, SRC/DEC, Palo Alto, CA, USA.

	Concurrent, Atomic Garbage Collection
	David L. Detlefs, SRC/DEC, Palo Alto, CA, USA.

	The Case for Garbage Collection in C++
	Daniel Edelson, University of California, Santa Cruz, CA, USA.

	Garbage Collection in an Object Oriented, Distributed, Persistent 
	Environment
	A. El-Habbash, Trinity College, Dublin, Ireland.

	Storage Reclamation
	Paulo Ferreira, INESC/IST, Lisboa, Portugal.

	Open Systems Require Conservative Garbage Collection
	Barry Hayes, Stanford University, CA, USA.

	Adaptive Garbage Collection for Modula-3 and Smalltalk
	Richard Hudson and Amer Diwan, University of Massachusetts, 
	Amherst, MA, USA.

	A Distributed, Faulting Garbage Collector for Emerald
	Niels Christian Juul, DIKU, Copenhagen, Denmark.

	SPiCE Collector: The Run-Time Garbage Collector for Smalltalk-80 
	Programs Translated into C
	Satoshi Kurihara, Norihisa Doi, and Kazuki Yasumatsu, 
	Keio University, Japan.

	Real-Time Concurrent Collection in User Mode
	Kai Li, Princeton University, NJ, USA.

	A Fast Expected-Time Compacting Garbage-Collection Algorithm
	Christer Mattsson, Lund University, Sweden.

	Garbage Collecting Persistent Object Stores
	J. Eliot B. Moss, University of Massachusetts, Amherst, MA, USA.

	Hardware Support for Garbage Collection of Linked Objects and Arrays in
	Real Time
	Kelvin Nielsen and William J. Schmidt, Iowa State Univesity, Ames, 
	IA, USA.

	A garbage detection protocol for a realistic distributed
	object-support system
	Marc Shapiro, INRIA, Rocquencourt, France.

	Three Issues In Obejct-Oriented Garbage Collection
	Jon L. White, Lucid, Inc., Menlo Park, CA, USA.

	Garbage Collection in a High-Performance System
	Mario Wolczko, The University, Manchester, UK.

	Designing Systems for Evaluation: A Case Study of Garbage Collection
	Benjamin Zorn, University of Colorado at Boulder, CO, USA.