I have been reading many articles so far that beat on LISP because of garbage
collection. This is completely unfair and narrow in thinking:
1) Garbage collection *specifically* improves productivity no matter *what*
language you write in. Part of the reason for big move toward pure OO
languages is because hacks like C++ (a hybrid OO lang) cannot provide
good garbage collection. Again, in a C or a C++ environment one spends
most of the debugging time chasing down obscure memory bugs which should
not be there in the first place! All the new promising languages have
GC in them. Explicit memory management is a needless burden maximally
prone to errors. Errors so bad that it creeps with time, sometimes
almost impossible to detect, causing problems half an hour into the
application. This is a problem computers are well-equipped to solve.
2) There is a whole branch of CS working on garbage collection algorithms
because it is an *extremely* important addition to any environment.
Almost all implementation of LISP has *very* old garbage collection
algorithms in them. Because halting the program for GC is neither
efficient nor desirable; all the new languages use "generational
garbage collection" completely invisible to the user & environment
and operates on real-time. This algorithm for instance, cannot be
implemented in C based languages and it is exactly of this reason C
& C++ has no future as a productive language.
All that is required is to add generational gc to LISP.
It is absolutely shocking to read articles that reject GC for strange
reasons. Please go to your library and familiarize yourselves with the
current state of technology.
Reha Elci
Email: ····@bugs.gs.com
In article <·····················@cunixf.cc.columbia.edu>, ····@cunixf.cc.columbia.edu (Reha Elci) writes:
> ...
>
> 1) Garbage collection *specifically* improves productivity no matter *what*
> language you write in. Part of the reason for big move toward pure OO
>
> ...
>
> It is absolutely shocking to read articles that reject GC for strange
> reasons. Please go to your library and familiarize yourselves with the
> current state of technology.
>
Thanks for pointing out this new technology. Unfortunately, the last
time I checked, it hasn't made its appearance into the "current state
of technology". By current state of technology, I mean what is
commercially available today on workstations (== SUN?), namely Allegro
CL and Lucid CL.
I have to disagree with you when you say that "garbage collection
*specifically* improves productivity". Yes, it may be true that
automatic memory management improves productivity, but I can see no
gain from GC itself.
o--------------------------------------o-------------------------------------o
| Ik Su Yoo | Office: (908) 699-5764 |
| Bell Communications Research | Fax: (908) 336-2969 |
| RRC 1H-229, 444 Hoes Lane | E-mail: ··@ctt.bellcore.com |
| Piscataway, NJ 08854 | ...!bellcore!ctt!ik |
o--------------------------------------o-------------------------------------o
In article <·····················@walter.bellcore.com> ··@ctt.bellcore.com (Ik Su Yoo) writes:
>Thanks for pointing out this new technology [generational GC].
>Unfortunately, the last
>time I checked, it hasn't made its appearance into the "current state
>of technology". By current state of technology, I mean what is
>commercially available today on workstations (== SUN?), namely Allegro
>CL and Lucid CL.
This is no longer the case. Lucid 4.xx has a fast and effective
generational garbage collector.
I was recently suprised by its speed. With some effort, I reduced the
consing done in a program from 2meg to under 256k -- a factor 8
improvement. I expected this to result in a substantial improvement
in the overall execution time of the program. Much to my dismay,
however, the speedup of the program was less than 10% [from 12 down to
11 seconds]. In the future, I'll spend less time trying to reduce the
construction of short-lived objects!
Adam Farquhar
In article <·····················@walter.bellcore.com> ··@ctt.bellcore.com (Ik Su Yoo) writes:
>Thanks for pointing out this new technology. Unfortunately, the last
>time I checked, it hasn't made its appearance into the "current state
>of technology". ... namely Allegro CL and Lucid CL.
Lucid Common Lisp has had generational garbage collection (they call it
"Ephemeral Garbage Collection", because that's what Symbolics called it
before there was a common name in the industry) for several years. I'm
pretty sure that Allegro CL also has a generational garbage collector.
--
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar
From: Bill Andersen
Subject: Re: Is LISP better than C -- garbage collection issue
Date:
Message-ID: <45608@mimsy.umd.edu>
>Thanks for pointing out this new technology. Unfortunately, the last
>time I checked, it hasn't made its appearance into the "current state
>of technology". By current state of technology, I mean what is
>commercially available today on workstations (== SUN?), namely Allegro
>CL and Lucid CL.
Allegro CL has generation scavenging garbage collection (GSGC). Is
this the same thing as what you are referring to????
...Bill
--
Bill Andersen (·······@cs.umd.edu) |
University of Maryland | clever .signature saying
Department of Computer Science | under construction
College Park, Maryland 20742 |
In article <·····················@cunixf.cc.columbia.edu> ····@cunixf.cc.columbia.edu (Reha Elci) writes:
>2) There is a whole branch of CS working on garbage collection algorithms
> because it is an *extremely* important addition to any environment.
> Almost all implementation of LISP has *very* old garbage collection
> algorithms in them. Because halting the program for GC is neither
> efficient nor desirable; all the new languages use "generational
> garbage collection" completely invisible to the user & environment
> and operates on real-time. This algorithm for instance, cannot be
> implemented in C based languages and it is exactly of this reason C
> & C++ has no future as a productive language.
>
> All that is required is to add generational gc to LISP.
Most generational garbage collectors aren't real-time. They're only
"nondisruptive," or strive to be, by making MOST pauses so short that
MOST users don't notice them. Ungar's was the first to do this, that
I know of. Some of the tradeoffs involved are discussed in my 1989
OOPSLA paper.
Unfortunately, the classic real-time generational gc (Hewitt & Lieberman's,
and the Ephemeral GC's for Lisp Machines) doesn't work very well on
stock hardware. (The problem is that programs execute while the heap
is still in an inconsistent (incompletely collected) state, so there
have to be checks to "fix up" any inconsistencies when they're
encountered by the running program. Lisp machines have hardware to
do those checks, normal machines must execute a bunch of extra instructions,
slowing things down by tens of percent. This is Baker's technique,
published in his 1978 (?) CACM paper).
Appel, Ellis, and Li published a paper in the 1988 SIGPLAN proceedings
about a variant of the Baker algorithm, which uses normal virtual
memory hardware to do the checking, and page protection traps to
trigger the incremental "fixing up" of bad pointers. Unfortunately,
it's not really real-time either, because the units of work done
may be relatively large and closely spaced. But it's close enough
for most things, and has the attractive benefit of allowing
concurrent collection.
There are also incremental non-copying algorithms, including Yuasa's
(from the J. of Systems and Software a while back) and Henry Baker's
new "treadmill" algorithm, which is abstractly like his incremental
copying algorithm, but snaps objects onto and off of free lists rather
than actually moving them from one space to another. In the usual case,
allocation only requires bumping through a linear free list, so allocation
is still pretty fast even though it's not quite as fast as incrementing
a pointer through a contiguous area.
David Detlefs' algorithm is "mostly copying" (but conservative about
ambiguous pointers from the stack, which can "pin" objects and keep them
from being movable), a la Joel Bartlett's mostly copying collector.
Detlefs incorporates the Appel-Ellis-Li technique of using page protection
to trigger increments of gc work.)
One of the problems with talking about "real-time" gc's is that
"real-time" means different things to different people. Some people
can deal with a few little (say, 1/4 sec) here and there, as long
as there's a half second or so of "real work" done every second.
A few people have MUCH stricter real-time requirements, like not
spending more than a few cycles per memory operation. Even Baker's
algorithm has trouble with the latter, and for really hard real-time
GC, you probably need hardware support or considerable software
overhead. (Kelvin Nilsen of the U of Iowa is working on hardware
support that doesn't interfere with the pipeline of a standard
CPU, causing only pipeline stalls from the processor's point of
view, so the smarts can be put into a memory module rather than
making CPU design even more complicated.)
Nilsen has also improved Baker's algorithm by putting reasonable
bounds on *allocation* times---the bound is proportional to the
size of object allocated, because copying is lazier than in the
original algorithm. Ralph Johnson (U. of Illinois) has made similar
improvements to the Appel-Ellis-Li algorithm to reduce the likelihood
of bad cases of clustered increments of work.
Ungar and Jackson take a different approach in their GC for Parc Place
Smalltalk (on stock hardware) combining a non-incremental copy collector
for the youngest generation with an incremental mark-sweep system for
the older data. This may or may not be real-time, depending on whether
your response-time requirements are more or less than a handful of
milliseconds.
>It is absolutely shocking to read articles that reject GC for strange
>reasons. Please go to your library and familiarize yourselves with the
>current state of technology.
A lot of new this stuff was discussed at the OOPSLA workshops on
garbage collection last year and the year before. (Barry Hayes and
I organized last year's). Other topics include GC's for C++ and
distributed garbage collection. The abstracts of the papers that were
presented, and ftp instructions for the papers themselves, will appear
in the Addendum to the Proceedings that will come out as a special
issue of SIGPLAN Notices. (I think the papers will be on cs.utexas.edu,
in the directory pub/garbage/GC91. Some of them are there now, but don't
expect them all to be there, or count on them being final versions,
for about a month.) If you're serious about GC's, you should have a
look at the abstracts.
-- Paul
--
| Paul R. Wilson, runtime environmentalist email: ······@cs.utexas.edu |
| U. of Texas Computer Sciences Dept. voice: (512) 471-9555 |
| Taylor Hall 2.124, Austin, TX 78712-1188 fax: (512) 471-8885 |
| "What doesn't kill me makes me stranger" DoD MC #: e (SZ GS450T) |
Thanks, Paul, for a well-stated and much-needed overview
for this discussion.
> One of the problems with talking about "real-time" gc's is that
> "real-time" means different things to different people. Some people
> can deal with a few little (say, 1/4 sec) here and there, as long
> as there's a half second or so of "real work" done every second.
> A few people have MUCH stricter real-time requirements, like not
> spending more than a few cycles per memory operation.
It's worth noting that this particular problem can generally
be addressed by buying N times faster hardware. If N is
large, and you're already on fast hardware, this may trade
your "real-time" requirements for your "need it this year"
requirements, however. Still, with 200+ MIPS 64-bit chips
on the near horizon, this isn't such an outlandish strategy
as it might seem.
However, it's worth distinguishing between those algorithms
which guarentee a constant upper bound on GC-introduced delays,
those which introduce an upper bound proportional to the largest
object allocated, and those with no upper bound.
Most uses can tollerate no upper bound, if it has good expected
"normal usage" behaviour. Truely critical systems, like pacemakers
and nuclear reactors require one of the first two categories. They're
pretty similar, if you don't mind rewriting your program to only use
arrays below a certain fixed size.
In article <·····················@cunixf.cc.columbia.edu> ····@cunixf.cc.columbia.edu (Reha Elci) writes:
| [regards generational GC] This algorithm for instance, cannot be
| implemented in C based languages and it is exactly of this reason C
| & C++ has no future as a productive language.
Regards the first half of this statement, my computer and I disagree.
Regards the second half of this statement, neither my computer nor I
pretend to be able to predict.
From: Jeff Dalton
Subject: Re: Is LISP better than C -- garbage collection issue
Date:
Message-ID: <5889@skye.ed.ac.uk>
In article <·····················@cunixf.cc.columbia.edu> ····@cunixf.cc.columbia.edu (Reha Elci) writes:
>2) There is a whole branch of CS working on garbage collection algorithms
> because it is an *extremely* important addition to any environment.
> Almost all implementation of LISP has *very* old garbage collection
> algorithms in them.
Not true.