[gclist] Experience with conservative GC sought

Carl Bruggeman bruggema@ranger.uta.edu
Thu, 22 Jan 1998 10:33:50 -0600

> Oy.  I suspect you have not done significant work on Emacs.  Almost
> every release of Emacs has had some bugs related to improper
> maintenance of the stack root list.  Stallman admits he makes these
> mistakes frequently himself, so I don't think it's an issue of
> programmer competence.  (Come on, you know what I mean. :) )

This is unrelated to my point.  I was not commenting on the abilities
of the programming team; I commend them.  I certainly agree than a
precise collector is much more difficult than an imprecise collector. 
You left out my summary:

Without knowledge of how well an imprecise collector works for millions
of different heaps you have no way of knowing whether you are headed
from the frying pan into the fire.

> Give my experience with Emacs, I am a solid fan of conservative
> techniques.  I am more of a fan of languages that support precise GC,
> but sometimes one hasn't a choice about such things.

There is always a choice and each choice has a cost.  I suggested some
possible costs in my previous message.  You have added some insights into
the current costs of maintaining a precise collector.

> I'm running SCWM, the Scheme-Configurable Window Manager for X
> Windows, which is based on Guile.  That's a long-running application.
> I haven't noticed any leakage bugs.  Aubrey Jaffer uses his Scheme
> system, SCM, on which Guile is based, for long-running digital circuit
> simulations, and reports that he has never encountered a storage leak
> due to the conservative GC.  Note that Guile uses conservative marking
> only to find pointers on the C stack, and in continuations; it uses
> precise techniques for all other intra-heap pointers.

These are a few more data points supporting conservative collection.

There are two missing links in the argument that these successes will
translate into success for emacs:

1) Do these successful applications have roughly similar
   characteristics (heap size, allocation rate, average retention, etc.)
   as emacs, so that it is reasonable to infer similar behavior for emacs?

2) Imprecise collectors have a probability P > 0 of having space leaks
   but P is application dependent (and can be data dependent).  In my
   last message I was asking if anyone had a large sample size (a
   program used by 10,000 people daily) so that it might be reasonable
   to infer the failure rate for a program like emacs that I assume
   has a installed base that is even larger.

> I suspect you are simply suffering from the usual Indiana University
> Perfectionism Syndrome.  :)

Even precise collectors are not always perfect...  We had an
application that had a "generational space leak".  The collector is
precise, but the heap size increased from 14MB to 22MB on average
because one type of short-lived structure was often promoted
(correctly) to an older generation (after which it promptly died), but
rooted a lot of otherwise dead structures.  Luckily is was trivial to
determine when the structures died so that the application could nil
out the offending field and the memory could be reclaimed at each
collection.  Imprecise collectors simply make these problems much more
common, completely random, and, perhaps worst of all, give the application
programmer no support for identifying the problem or correcting it.

Explicit allocation has tradeoffs
Precise collectors have tradeoffs
Generation-based precise collectors have tradeoffs
Imprecise collectors have tradeoffs

Without data you cannot tell the difference between the frying pan
and the fire. Even with a thousand "it worked for me" stories, you
still have no guarantee that it will not be a disaster for emacs
(or any other large production system).

Suggestion:  It seems to me it should be trivial to plug Boehm's
collector into the current version of emacs:  just have the collect
handler nil out the pointers on the root stack before doing a
collection (no need to remove any of the current GC support code). 
Distribute this change as a patch and let thousands of people test it
for the team and provide feedback.  It might be a good idea to add
instrumentation code to generate heap statistics (for both the patched
and unpatched version) as well as a hook to ask users who are exiting
long running sessions whether it would be OK to email the stats to
some automatic collection facility for the emacs programming team.
I'll even volunteer to help with the analysis of the data.


Carl Bruggeman -- bruggema@cse.uta.edu -- Phone: (817) 272-3600 Fax: 272-3784
Computer Science and Engineering Department -- University of Texas at Arlington