Subject: Re: Why garbage collection?
From: Erik Naggum <erik@naggum.no>
Date: 1996/01/14
Newsgroups: comp.lang.lisp
Message-ID: <19960114T050927Z@arcana.naggum.no>

[Richard Villanueva]

|   I understand the classical Lisp method of automatic garbage collection,
|   and it is very elegant.  It reserves only one bit per cons cell (the
|   mark bit).  However, on large systems, the long pause for garbage
|   collection is bad, so people look for more sophisticated methods.

there is no "long pause" in modern systems.  numerous brilliant minds have
worked on garbage collection for many years.  that is nearly a guarantee
that you will need to have in-depth knowledge of the prior art in garbage
collection techniques to be able to provide useful suggestions.

|   My question is, why not plain old reference counts?

One day a student came to Moon and said, "I understand how to make a better
garbage collector.  We must keep a reference count of the pointers to each
cons."  Moon patiently told the student the following story-

       "One day a student came to Moon and said, "I understand how to
       make a better garbage collector...

(from the AI koans collection, found, among other places, at
http://www.cs.rochester.edu/u/miller/ai-koans.html.)

|   So am I missing something?  Or are there other methods that are even
|   better?

I have misplaced the address of the mother of all sites on garbage
collection, but there is one that has an excellent survey, and there are
many papers available.  the literature was sufficiently, um, extensive,
that I figured that I had work to do and news to read before I would embark
on this long journey.  if my plan to become immortal succeeds, I'll
certainly study garbage collection.  in the meantime, I know only that
anything I could come up with on my own is bound to be discarded as too
inefficient already, unless I luck out and strike 18 aces in a row.

one of the most well-known inefficient and wasteful techniques is reference
counting.  most C++ programmers invent their own particularly ugly breed of
inefficient reference counting.  this is why C++ is so popular -- the
probability that each and every C++ programmer will actually be able to
improve something in that language and feel great about it is exactly 1.

btw, your "one byte" stuff won't work.  modern computers are no longer byte
adressable, but instead waste two or three bits of the precious machine
word and address range because some inferior languages think that byte
addressability is a win.  the smallest efficiently addressable unit on RISC
processors is usually 4 bytes, sometimes 8 bytes.  even on CISCs, you may
pay a hefty penalty for misaligning your data.

#<Erik 3030584967>
-- 
the problem with this "information superhighway" is mainly that if you ask
people to go play in it, they don't even understand when they get run over.