From jackson@parcplace.com Fri Aug 16 08:56:14 1991
Received: from ads.com by cs.utexas.edu (5.64/1.107) with SMTP
	id AA24111; Fri, 16 Aug 91 08:56:06 -0500
Received: from parcplace.parcplace.com by ads.com (5.65+/1.34v1.3)
	id AA08221; Fri, 16 Aug 91 06:55:58 -0700
Received: from zodiac by parcplace.com (4.0/SMI-3.2)
	id AA04077; Fri, 16 Aug 91 06:55:56 PDT
Received: by zodiac (4.1/PARC-Place V1.0)
	id AA20273; Fri, 16 Aug 91 06:55:55 PDT
From: jackson@parcplace.com (Frank Jackson)
Message-Id: <9108161355.AA20273@zodiac>
Date: 16 August 1991 6:55:52 am
Subject: GC 91 Position Paper
To: wilson@cs.utexas.edu, bhayes@cs.stanford.edu
Cc: krasner@parcplace.com
Fonts: 8121 1 
Status: OR

Paul and Barry,

	The following is a draft of the position paper that I am submitting for
inclusion in the OOPLSLA '91 Garbage-Collection workshop. Rather than submit
something dry and scientific, I thought it might be a nice change of pace to
focus on something slightly more amusing; namely some of the more annoying bugs
that I have stubbed my toes on in the past five years. Admittedly the paper
below is little more than a sketch (it's sort of like the trailer to a movie
except that I don't reveal any of the punchlines), but if you like, I could
easily prepare a short talk on the subject for presentation at the workshop.

	For the record, my credentials in memory managagement amount roughly to the
following: I have been responsible for the design and implementation of all of
the Smalltalk-80 memory managers built at ParcPlace Systems since 1986. Our
current memory manager incorporates three decidedly different reclamation
systems: a generation scavenger, a fully incremental, mark-sweep garbage
collector, and a global, non-incremental, mark-sweep garbage collector. My
publications in this field have, to date, all been on the subject of generation
scavenging, the most recent being on the topic of adaptive tenuring policies
(to be published in an upcoming issue of TOPLAS). I am also a co-author on
another paper submitted to this workshop by Dave Ungar and myself on the
subject of incremental garbage collection.

	Since I regrettably had to withdraw from the `90 workshop at the last minute,
I am looking forward to attending this year's workshop.

	By the way, is the address for hardcopy (University of Illinois) up to date,
or should I send it elsewhere? Or better yet, can I simply blow off hardcopy
for now?

Frank

----------------------------Draft---------------------

Garbage-Collection Bugs That I Have Known

	The following is a light-hearted look at some of the more unusual bugs that
have, at various times, bedeviled the three generations of Smalltalk-80 memory
managers that I, along with Dave Ungar, have designed and implemented for
ParcPlace Systems over the past five years. Why bother, you ask, to stir up old
bugs that are now, for the most part, fixed? Well, I can think of three reasons:

	1. Because some of the bugs are, in retrospect, amusing;

	2. Because it can be instructive to examine the sorts of problems that are
uncovered when a memory manager that seems to work perfectly well in the lab is
actually put to the test by real users running real applications;

	3. Because such bugs often occur in precisely those areas of emerging
technology that deserve special attention; and

	4. Because it gives me a great excuse to talk about those aspects of memory
management that are of interest to me, but that I find are frequently neglected
in the literature.

	At any rate, I have categorized the bugs below according to the aspect of
memory management from which they sprang.

I. Weak Pointers

	Our beta customers thought it was great when we introduced weak pointers
(i.e., pointers that don't prevent the garbage collector from reclaiming an
object) into our system. Now they could keep tabs on and gather statistics
about object populations without inadverdantly keeping such objects alive
simply because the statistics-gathering machinery needed to maintain a pointer
to the objects being studied. Now they could take an object census with
artificially inflating the result. Yes, our users were quite pleased until they
encountered the

	Reincarnation Bug.

	That is, objects that were pointed to by WeakArrays suddenly began changing
their spots. What was once a simple character String, suddenly became a
ComposedTextView; Nice, quite ReadStreams became TranslatingWrappers; and
ByteArrays suddenly lost their byte.

	So what was going on? Well, when the moon was full and the tide high, our
scavenger would sometimes become confused and forget to nil out those weak
pointers whose referents had been reclaimed. It was then only a matter of time
before the allocator handed out the very same oop to another object, and
presto, what had once been a bag now became a set....

Moral:

	It's amazing how long you can run with a dangling pointer, when that pointer
is weak.

II. Finalization

	Systems that have automatic memory managers frequently need to take some final
action when an object has expired or is about to expire. For example,
Smalltalk-based systems frequently refer to external resources that are not
subject to automatic memory management. This is especially true now that the
host platform generally manages the window system rather than the
program-development environment itself, and even more so if the window system
(e.g., X) allocates such resources in a separate heavyweight process. At any
rate, once the object that is acting as a proxy to the external resource has
been recycled, someone needs to inform the provider of the external resource
that it can now recycle that resource. Wouldn't it be nice if the memory
manager automatically informed the provider?

	In fact, our current system does exactly that for externally managed resources
such as file descriptors and window handles. Which would be great except for the

	Resurection Bug

which permitted objects that have been finalized to come back to life....

	Well, we fixed that bug by using weak pointers to implement finalization ...
only to have windows suddenly disappear from the screen, because of

	Premature Finalization ...

Moral:

	For every bug that you fix, there is an equally pernicious, but logically
opposite bug waiting to happen.

III. The Case for Hybrid Memory Managers

	When I was young and carefree, I naively thought that, for a given system
running on a given machine, there must be a single reclamation algorithm that
would perform reasonably under most circumstancs. Or rather, I thought so until
I encountered the

	Pig-in-a-python bug...

	Different object populations that have different demographics can easily
overturn the assumptions that are implicit in any given algorithm. For example,
generation scavengers in particular, and copying collectors, in general, are
most effective if the mortality rate of a given object population is high.
These techniques are less than optimal, however, for object populations where
the mortality rate is quite low. Even adaptive algorithms (short of wholesale
algorithmic changes) cannot generally cope with the differences in the object
populations that our users' applications have been known to produce...

Moral:

	Object populations with dramatically different demographics require different
algorithmic treatment if you hope to achieve near-optimal performance.

IV. Adaptive Algorithims

	Before Dave and I actually started to build memory managers for ParcPlace
Systems, we carefully measured actual users while running atop an older,
instrumented system. We then built a simulator and laboriously ran numerous
simulations to come up with what we thought was a reasonable reclamation system
controlled by a reasonable policy. Our studies indicated, for example, that if
our scavenger tenured objects only after they had survived at least 7-10
minutes, then the system would not accumulate an inordinate amount of tenured
garbage. The resulting system worked without problems for several months of
extensive in-house use. Then, we let our first outside customer try to compile
a fairly large application on the new system, and we were horrified when it
produced 3.2 MBytes of tenured garbage in a matter of minutes...

	Fortunately, this problem was remedied when we switched to an adaptive
tenuring policy. In fact, the amount of tenured garbage was reduced to 270 KBytes....

Moral:

	Fixed policies, even ones based on empirical studies, fall apart when the
studies are at odds with the characteristics of the application being run.

V. Running Out of Memory

	Running out memory in many systems is like driving an automobile with no
brakes: when you hit the wall, you simply crash...

VI. Then there was the one about mechanism vs policy....

------------------------draft--------------------------