[gclist] Re: gclist-digest V2 #76

Michael Spertus mps@geodesic.com
Thu, 06 Nov 1997 20:54:18 -0600

boehm@hoh.mti.sgi.com (Hans Boehm) said
>On Nov 5, 10:28am, Simon Spero wrote:
>> Ok, here are two questions to chew on :-)
>> 1: How do conservative garbage collectors for un-cooperative languages
>> degrade over time when used in extremely long-lived server processes?
>That's of course a hard question.  I would argue that we don't even have
>complete answers to that question for malloc/free programs.  Current evidence
>suggests that fragmentation should remain minor for a good nonmoving allocator.
> But I don't know of many measurements of long running server processes.
>My experience with pointer misidentification is that its usually not a problem.
> In the cases of which I'm aware for which it was a problem, it was easily
>detectable.  It was also easily remedied with a minor source change once the
>problem was identified.  The real issue at the moment is the lack of widely
>available tools for identifying such things.
>This is consistent with my intuition.  The leaks from pointer misidentification
>remain bounded so long as you don't get into a situation where the average leak
>introduces more than one additional leak, due to misidentified pointers in the
>leaked object itself.  That rarely happens.  When it does, there's an
>exponential at work, and things diverge fairly quickly.  (In real life things
>aren't quite that simple because only certain phases might provoke the bad
>behavior, etc.)
>All of this is good, in that it means that it's fairly easy to test for
>potential problems.
>It's also consistent with real experiences.  Cedar worlds at Xerox PARC stayed
>up for long periods with a conservative collector.  When they did crash it was
>for other reasons (e.g. power failures).  Some Xerox high end printers were
>Cedar-based and used a conservative collector.  As far as I know, they are
>quite stable for long periods of time.  I saw no evidence of growing leaks or
>fragmentation.  (The allocator in our GC does have a bit of a problem with
>large block fragmentation.  But it doesn't seem to get worse over time.  It's
>also fixable.)
Users of our collector almost always use our libraries that bind malloc to
gcMalloc. (The exception being Java implementors) This means that if they
are using 3rd-party libraries for which pointer misidentification is a
problem, they can't eliminate the pointer misidentification. A good example
would be a library that manipulates large compressed data structures. A goal
of data compression is to equidistribute bit patterns as much possible,
which violates an assumption of conservative collection. This can result in
substantial misidentification in programs with large heaps. For example,
200Megs of compressed video may have many millions of bit patterns, perhaps
resulting in programs for which >1% of address values occur in data words.
In addition, wastefully scanning the 200Megs of data for pointers is a
performance killer. If you have access to the source code, it is easy to fix
both problems by allocating the data as a leaf (= pointerless) object, but
if it was allocated by a 3rd-party library, you can't do that. 

Fortunately, pointer misidentification doesn't really matter, because even
if we fix 98% of all leaks, it's better having us in there. However, the
first release of Great Circle bound frees to no-op by default. Our customers
with large apps of this sort had real problems with pointer
misidentification, hence our current default is to bind free() to gcfree()
so that the default setting provides benefit to everyone. Many but not all
users would increase their benefit by turning free back into a noop. Our
gcFixPrematureFrees() API does exactly this. The above example would still
have a time problem associated with the wasteful memory scan, but not a
space problem (assuming they have not bound free to a noop)

Finally, observe that 64-bit machines turn conservative collectors
automatically  into precise collectors!

>> 2: Why are there no commercial conservative garbage collectos for Linux?
>Perhaps someone from Geodesic Systems can comment.  My impression is the reason
>is the same as for the lack of good tools to analyze memory retention in GC
>environments:  too much to do, too little time.
Unfortunately, Linux ranks quite low on porting priority for us even though
many of our developers would like to do it. Not only our SGI, A/IX, etc.
higher priorities, but even less popular OS's like Wind River would come out
ahead, based on existing revenue opportunity. Perhaps someone on this list
could point us at someone willing to pay money for Linux collectors, so we
could raise its priority.

malcolm@nag.co.uk (Malcolm Cohen) said:
>Probably for the same reason there are no commercial compilers for Linux-
>it's not easy to create a better product than the freely available one,
>and even if you did, you probably wouldn't sell many because the freely
>available one is "good enough" (or, worse yet, you cause the freely 
>available one to improve to compete with you).
Actually, our product has many features that are not even attempted in the
freeware collectors that can be used to justify the purchase of commercial
collector. These include web-based heap visualization tools, symbolic stack
traces, fragmentation-immune allocator, generation of useful reports,
complete allocation profiling, fixing of leaks in existing programs and
libraries without rebuilding, thorough support and documentation, and
consulting services, not to mention higher performance. By and large, we
view our competition not as the freeware collectors, which help increase
GC's popularity, but as manual memory management. If everyone garbage
collected their C/C++ programs, there would be plenty of room for both
freeware and commercial collectors.


Michael Spertus                            mps@geodesic.com
Geodesic Systems                           (312) 832-1221
414 N Orleans, Suite 410                   http://www.geodesic.com
Chicago, IL 60610