Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!mailrus!cornell!uw-beaver!rice!flora!boehm
From: boehm@flora.rice.edu (Hans Boehm)
Newsgroups: comp.lang.c++
Subject: Re: Eiffel vs. C++ (vs Smalltalk)
Summary: Garbage collection is not that expensive
Message-ID: <3498@kalliope.rice.edu>
Date: 12 Jun 89 16:03:17 GMT
References: <5316@tekgvs.LABS.TEK.COM> <77300030@p.cs.uiuc.edu>
Sender: usenet@rice.edu
Reply-To: boehm@flora.rice.edu (Hans Boehm)
Organization: Rice University, Houston
Lines: 56

In article <77300030@p.cs.uiuc.edu> johnson@p.cs.uiuc.edu writes:
> ...  Garbage collection does not get along
>very well with real-time programming.  The Smalltalk garbage
>collectors are pretty good, usually only taking a fraction of a
>second to collect garbage.  However, if this happened in a middle
>of an interrupt then even 1/4 a second is too long.
>
>...  However, designing a language so that it
>provides complete memory management and still permits real-time control
>is an unsolved problem, as far as I know.  True incremental garbage
>collection either requires special processor design or is very inefficient,
>and the real-time programming people don't like inefficiency, either.
>Thus, there are still very important application areas (and real-time
>programming is growing in importance) for which garbage collection is
>inappropriate.

  Though I agree entirely with the content of Ralph's message, I am afraid that
parts of it are likely to be misinterpreted.
  I know of no way to guarantee 1 millisecond response in the presence of
a garbage collector running on a standard processor.  However, there are 
a number of garbage collection schemes that use conventional paging hardware
to provide somewhat larger granularity incremental behavior (cf., Appel,
Ellis, and Li, ``Real-time Concurrent Collection on Stock Hardware'',
SIGPLAN '88 Proceedings).  My impression is that if you can afford to
run in a virtual memory environment, you can afford an efficient garbage
collector.  If you can't afford virtual memory, you can't afford the
collector without special hardware or noticable extra overhead.

>Many people do not know that it is possible to use a garbage collector
>in C++ or C.  Hans Boehm has such a collector, which he developed for
>Russel.  I just saw an announcement of a Modula-3 implementation, and
>they are using it, so it is pretty general purpose.  This garbage collector
>is not fast, because it can make almost no assumptions about the layout of
>objects and so must be conservative.  However, the main reason for a garbage
>collector in C++ would be to catch "space leaks", so it would not have to
>be called very often.
>
>Ralph Johnson

Our garbage collector is slower than a good copying collector.
But, as has been pointed out before, garbage collector performance tends
to be judged by tougher standards than malloc/free performance.  Garbage
collectors are frequently used in environments where 1 allocation per
100 instructions is considered normal.  Some standard malloc/free
implementations are completely unusable under such conditions.  We have
sometimes seen performance improvements in going from the vendor supplied
malloc/free implementation to our allocator with full garbage collection.

The current collector is not incremental in any sense, so bursty response
is a bit of a problem.  But it is important to keep perspective on this as
well.  Very long garbage collection times usually arise only in systems that
keep the editor/compiler/programming environment entirely in one address
space, or for really large applications.  Garbage collection times for a
half full 1 Meg heap on a MIPS M/120 are on the order of 1/4 sec.

Hans-J. Boehm