[gclist] Re: Linux and commercial compilers

[Hans Boehm]

On Nov 5,  3:11pm, P. T. Withington wrote:
> Subject: Re: [gclist] Re: Linux and commercial compilers
> At 13:59 -0600 11/5/97, David Gadbois wrote:
> >   From: boehm@hoh.mti.sgi.com (Hans Boehm)
> >   Date: Wed, 5 Nov 1997 10:38:07 -0800
> >
> >   [...]
> >
> >   1) Garbage collecting allocators aren't good at very large objects.
> >
> >There are some tricks you can play to make big objects not be such a
> >big deal.  With a generational collector, instead of copying large
> >objects, you can just tweak the bookkeeping information so that it
> >indicates that the object is in an older, target generation.  You
> >still have to scavenge the big object, but at least no new memory is
> >allocated.
>
> And often big objects are devoid of references, e.g., they might be
> bitmaps, arrays of floats, etc.  Allocating such objects in a way that the
> GC knows it never needs to scan them can also be a big win.  A hint from
> the compiler is best (lest the programmer lie).
>
I agree.  (Our C collector never copies objects, and it has a mechanism for
allocating pointerfree objects.)  These measures are clearly necessary to get
reasonable performance.  But the result is still likely to be signifcantly
slower and/or bigger than the malloc/free program.

Consider a program that allocates a 10MB data structure, which lives until the
process dies, and then alternately allocates and drops pairs of 10MB objects.
 (This is a bit, but not terribly, contrived.)  In a malloc/free environment,
this program runs in basically 30 MB, with nearly 0 allocation cost (well,
maybe 100 instructions/roundtrip) after the allocation of the long-lived data
structure.

In the garbage collected case, we might be able to run in 50MB.  But then we
need to garbage collect every 4 (or 2 depending on the details) allocations.
 Thus the cost per allocation is at least that of scanning 2.5MB, which is
decidedly nonzero.

Granted, you can contrive a generation-based scheme that will defeat this or
any other single example.  But it serves to illustrate the fundamental issue,
which is that large object allocations force frequent collections, which
greatly increase the average cost per allocation.

I'm of course not arguing against the use of garbage collection.  The other
side of this coin is that garbage collection of very small objects is often
cheaper than for malloc/free, even if you don't copy, and especially if you do.
 And those tend to be more frequent and harder to manage manually.  I am
arguing that the cost model for GC is fundamentally different from manual
deallocation, and people should be aware of that.  Pretty much all of the cases
in which people have been unhappy with GC performance have been one of the
following:

- large very rarely accessed data structures that could be paged out, except
for GC accesses.  (These tend to perform quite poorly to start with, so it's
generally not that big a deal.)

- much of the allocation was for very large objects.  I've seen slowdowns of
something like a factor of 10 if the objects contained pointers and perhaps a
factor of 2 if they didn't.

I would rather warn people ahead of time that both of these are likely to be
problematic.



-- 
Hans-Juergen Boehm
boehm@mti.sgi.com