Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!mit-eddie!bloom-beacon!apple!oliveb!Ozona!chase
From: chase@Ozona.orc.olivetti.com (David Chase)
Newsgroups: comp.lang.misc
Subject: Re: Xerox PARC's Cedar (garbage collection)
Message-ID: <41977@oliveb.olivetti.com>
Date: 19 May 89 18:56:02 GMT
References: <460002@hpbsla.HP.COM> <11735@well.UUCP>
Sender: news@oliveb.olivetti.com
Reply-To: chase@Ozona.UUCP (David Chase)
Organization: Olivetti Research Center, Menlo Park, CA
Lines: 107

In article <11735@well.UUCP> Jef Poskanzer <jef@helios.ee.lbl.gov> writes:
>Adding garbage collection to a language that doesn't need it is an
>admission of failure.  Consider, there are two main kinds of errors
>involving dynamic memory: forgetting to free an object, and referencing
>an object after it has been freed.  The first type is commonly called a
>memory leak, and it is often easy to see (but not to find) by simply
>watching the size of your program and noting that it grows over time.
>The second type, often called a heap smash, is more pernicious; you
>will typically only find it by accident, when you re-allocate the same
>chunk of memory somewhere else in your program, and things start
>failing randomly.
>
>So what does garbage collection do?  It gets rid of some memory leaks
>(the kind where you put a pointer into a local variable and forget to
>free it).  It also converts heap smashes into memory leaks.  True, your
>program is now less likely to fail randomly and catastrophically; this
>is a win.  But it is now impossible to find any remaining memory
>leaks.  In the long run, your programs are *less* reliable.
>
>It is much better to use proper programming discipline and modern
>debugging tools than to punt the issue with the short term (and
>expensive) fix of garbage collection.

I couldn't let this one pass.  As I read it, you say that adding
garbage collection allows me to replace memory leaks and heap smashes
with memory leaks, and that is bad.  I conclude that heap smashes are
good?

You should read Boehm and Weiser's SP&E paper [1] for a description
of a garbage collector that can be used with "a language that doesn't
need it" (C).  Their experience was that their collector plugged more
leaks than it opened.  I have used this collector, and the expense is
quite modest (typically 10% -- this may seem anomalously low, but
consider that most C programs don't allocate memory at the same
vicious rate that Lisp, ML, or Smalltalk programs do.  Even so, Appel
et al make the [somewhat convincing] argument that garbage collection
is *cheaper* than alloc-free style memory management [2,3]).  Using a
garbage collector, even in C, means that I don't need to worry about
smashes at all and need only worry about leaks a little, and lets me
spend time worrying about frivolous things like correctness and
algorithmic improvements.  That is, I dispute the "expense" of garbage
collection; it has costs, but relatively minor ones.  Furthermore,
"modern debugging tools" can do a much better job of providing
sensible information about memory leaks than they can about pointer
smashes.  From a semantic point of view, a leaky program has meaning,
but trouble with its resource consumption.  A pointer-smashing program
has no defined meaning, is much more difficult to reason about, and
may not even be debuggable at the "source level".

A typical memory-debugging tool maintains a hash table of the last few
PCs in a call chain, tags each block allocated with the index, and
performs the obvious reporting upon subsequent free or garbage
collection.  I've done this in simple form to profile memory
allocation hot-spots, and Boehm and Weiser describe a more
sophisticated tool which turns a garbage-collector into a leak-finder
for programs which treat "free" as an assertion (this can also point
up potential pointer smashes, but this information is less reliable
because unused but still reachable pointers to memory may still exist
at the time of a garbage collection -- before you say "aha! a leak", I
should point out that any resulting leaked storage tends to get
collected during the next collection, and that Boehm and Weiser have
found that this happens comparatively rarely).  For a programmer who
insists on banishing garbage collection from the finished code,
garbage collection can still serve as a development tool (and if you
claim that memory management must be designed in from the start, I'll
respond "aha! and I'll bet it doesn't make the design any easier!").
If you talk to former Cedar programmers and users (I work for one),
you will find that they insist on retaining the ability to work around
or avoid using the garbage collector in certain crucial pieces of
code, but that it is typically the memory manager of choice.
("Occasionally indispensable" does not mean "everywhere desirable").

It is also worth noting that programming takes on a different style,
given a garbage collector.  Interface specifications need not include
details about whether a subroutine or its caller is responsible for
allocating or freeing a piece of storage.  "Free(x)" is replaced by
"x = 0".  Cleanup after errors is simpler; rather than leaking, or
requiring tedious code to undo allocations, a program can let the
garbage collector handle it.

Keep in mind that I am not arguing for a garbage collector per se, but
rather for its function.  The *programmer* should see a system that
appears to be garbage-collected, but if the compiler can do away with
some of this and make it faster, so much the better.

I'm sure I'll hear more about this.

David

[1] AUTHOR = "Hans Boehm and Mark Weiser", TITLE = "Garbage Collection
in an Uncooperative Environment", JOURNAL = spe, YEAR = 1988, MONTH =
sep, PAGES={807--820}

[2] AUTHOR = "A. W. Appel and D. B. MacQueen", TITLE = "A Standard
{ML} Compiler", BOOKTITLE = FPLCA87, YEAR = 1987, PAGES = {301--324}

[3] AUTHOR = "Andrew W. Appel and John R. Ellis and Kai Li", TITLE =
"Real-time concurrent garbage collection on stock multiprocessors",
BOOKTITLE = PLDI, YEAR = 1988, PAGES= {11--20}

{PLDI = "{SIGPLAN} Symposium on Programming Language Design and
Implementation"}

{FPLCA87 = "Functional Programming Languages and Computer
Architecture"}

{spe = "Software, Practice and Experience"}