Garbage Collection in C

[jacob navia]

Abstract
--------
Garbage collection is a method of managing memory by using a "collector"
library. Periodically, or triggered by an allocation request, the
collector looks for unused memory chunks and recycles them.
This memory allocation strategy has been adapted to C (and C++) by the
library written by Hans J Boehm and Alan J Demers.

Why a Garbage Collector?
-----------------------
Standard C knows only the malloc/calloc/free functions. The programmer
must manage each block of memory it allocates, never forgetting to call
the standard function free() for each block. Any error is immediately
fatal, but helas, not with immediate consequences. Many errors like
freeing a block twice (or more) or forgetting to free an allocated
block will be discovered much later (if at all). This type of bugs are
very difficult to find and a whole industry of software packages
exists just to find this type of bugs.

The garbage collector presents a viable alternative to the traditional
malloc/free "manual" allocation strategies. The allocator of Boehm
tries to find unused memory when either an allocation request is
done, or when explicitely invoked by the programmer.

The main advantage of a garbage collector is that the programmer is
freed from the responsability of allocating/deallocating memory. The
programmer requests memory to the GC, and then the rest is *automatic*.
Limitations of the GC.
---------------------
The GC needs to see all pointers in a program. Since it scans
periodically memory, it will assume that any block in its block list is
free to reuse when it can't find any pointers to it. This means that the
programmer can't store pointers in the disk, or in the "windows extra
bytes", as it was customary to do under older windows versions, or
elsewhere.

This is actually not a limitation since most programs do not write
pointers to disk, and expect them to be valid later...
Obviously, there is an infinite way to hide pointers (by XORing them
with some constant for instance) to hide them from the collector.

This is of no practical significance. Pointers aren't XORed in normal
programs, and if you stay within the normal alignment requirements
of the processor, everything works without any problems.

Performance considerations
--------------------------
In modern workstations, the time needed to make a complete sweep in
mid-size projects is very small, measured in some milliseconds. In
programs that are not real time the GC time is completely undetectable.
I have used Boehm's GC in the IDE of lcc-win32, specially in the
debugger. Each string I show in the "automatic" window is allocated
using the GC. In slow machines you can sometimes see a pause of
less than a second, completely undetectable unless you know that is
there and try to find it.

It must be said too that the malloc/free system is slow too, since at
each allocation request malloc must go through the list of free blocks
trying to find a free one. Memory must be consolidated too, to avoid
fragmentation, and a malloc call can become very expensive, depending
on the implementation and the allocation pattern done by the program.
Portability
-----------
Boehm's GC runs under most standard PC and UNIX/Linux platforms. The
collector should work on Linux, *BSD, recent Windows versions, MacOS X,
HP/UX, Solaris, Tru64, Irix and a few other operating systems. Some
ports are more polished than others. There are instructions for porting
the collector to a new platform. Kenjiro Taura, Toshio Endo, and Akinori
Yonezawa have made available a parallel collector.

Conclusions
-----------
The GC is a good alternative to traditional allocation strategies for C
(and C++). The main weakness of the malloc/free system is that it
doesn't scale. It is impossible to be good at doing a mind numbing task
without any error 100% of the time. You can be good at it, you can be
bad at it, but you can NEVER be perfect. It is human nature.

The GC frees you from those problems, and allows you to conecntrate in
the problems that really matter, and where you can show your strength
as software designer. It frees you from the boring task of keeping track
of each memory block you allocate.

jacob

[Roland Pibinger]

On Wed, 11 Oct 2006 20:46:40 +0200, jacob navia wrote:

>Roland Pibinger wrote:

>GC handles only one resource, memory. Other resources in a program eg.
file handles, database connections, locks, etc. still need to be
handled by the programmer.

Well, it will not make your coffee anyway :-)

For C the heap is a scarce resource like any other resource. Heap
memory has to be acquired and released. For a GC language the heap
(conceptually) is an infinite space. That's the difference. I prefer
the C point of view.

Best wishes,
Roland Pibinger

[Ben Pfaff]

jacob navia <ja***@jacob.re mcomp.frwrites:

[garbage collection]

I'd suggest use of resource pools as a viable alternative to
garbage collection that can actually be implemented in standard
C. Resource pools are not perfect, but when used in a
disciplined way they can make some kinds of programming much
simpler.

Here's a discussion of what I mean:
http://freetype.sourceforge.net/david/reliable-c.html
--
"C has its problems, but a language designed from scratch would have some too,
and we know C's problems."
--Bjarne Stroustrup

[sjdevnull]

Roland Pibinger wrote:

For C the heap is a scarce resource like any other resource. Heap
memory has to be acquired and released. For a GC language the heap
(conceptually) is an infinite space.

The last sentence is untrue. Not all the world is mark-sweep or
copy-collect. There are deterministic GCs that give the programmer
guarantees on when memory will be released. Simple reference counting
is the most common. There are also GC systems where a call can be made
to force immediate collection.

[Kenny McCormack]

In article <45************ ***********@new s.orange.fr>,
jacob navia <ja***@jacob.re mcomp.frwrote:

>Bob Martin wrote:

>in 700822 20061011 175810 Richard Heathfield <in*****@invali d.invalidwrote:

>>>jacob navia said:
Why a Garbage Collector?
-----------------------
Standard C knows only the malloc/calloc/free functions.

Quite so. Please move discussions of non-C matters to some other newsgroup
where it is topical.

Are you telling Jacob to stay out of your playpen?

I do not know what heathfield has against the GC.

The following links may be useful - especially the first:

http://en.wikipedia.org/wiki/Aspergers
http://en.wikipedia.org/wiki/Clique
http://en.wikipedia.org/wiki/C_programming_language

Anyway, Jacob, why do you punish yourself so? Why do you go around with
a kick-me sign on your backside? You could state that 2+2 = 4 and
heathfield would say it isn't so. That's just what it is.

And here's another thing (indirectly, from Wikipedia, which, as we know,
heathfield thinks is rubbish), on the subject of creationism (and that
oxymoron of oxymorons "creation science"). Note that there are many
good and deep parallels between creationists and cls regulars (although
they all, of course, deny it). But, the idea is this: some famous
scientish (I believe it was Richard Dawkins) holds that it is silly to
debate creationists for much the same reasons as why you don't debate
with clc regulars, er, I mean, pigs ("They like it" and "you just get
dirty"). But more specifically, Dawkins says that debate is a silly
activity, because the way to win is never to say another positive about
your own position, that is never to espouse a positive view, because if
you do, then you give the other side something to attack. Instead, all
you do it nitpick their position; that's how you score points.

The obvious analogy to heathfield and CLC regulars in general should be
numbingly obvious.

That's why heathfield will never claim to like or support anything
(e.g., valgrind, for which any sensible person would have taken his post
to be one of support, yet when questioned, claimed he never supported
it). Just generally: what a wuss.

[Mark McIntyre]

On Wed, 11 Oct 2006 20:01:27 +0200, in comp.lang.c , jacob navia
<ja***@jacob.re mcomp.frwrote:

>Bob Martin wrote:

>in 700822 20061011 175810 Richard Heathfield <in*****@invali d.invalidwrote:

>>>jacob navia said:
Why a Garbage Collector?
-----------------------
Standard C knows only the malloc/calloc/free functions.

Quite so. Please move discussions of non-C matters to some other newsgroup
where it is topical.

Are you telling Jacob to stay out of your playpen?

I do not know what heathfield has against the GC.

And I don't know what Navia has against being polite. Last time I
checked, even the French thought it more polite to refer to people by
first name, or failing that with the correct honorific.

Lets move on shall we, quietly reflecting as we do that Richard has
already made it plain he has nothing against GC, merely against rude
and persistent offtopic posters who regard the rules of usenet as
theirs to ignore as they please.

(rest of Navia's stupid post snipped as it was offensive and
gratuitous)
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

[Kenny McCormack]

In article <rp************ *************** *****@4ax.com>,
Mark McIntyre <ma**********@s pamcop.netwrote :
....

>(rest of Navia's stupid post snipped as it was offensive and
gratuitous)

Oh, the delicious irony...

[CBFalconer]

Richard Heathfield wrote:

jacob navia said:

>Why a Garbage Collector?
-----------------------
Standard C knows only the malloc/calloc/free functions.

Quite so. Please move discussions of non-C matters to some other
newsgroup where it is topical.

I think this particular carp is unfair. Jacob has been
fundamentally advertising the available of the Boehm library for
GC, which I presume is written in standard C, or nearly so.

--
Some informative links:
<news:news.anno unce.newusers
<http://www.geocities.c om/nnqweb/>
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html >
<http://www.netmeister. org/news/learn2quote.htm l>
<http://cfaj.freeshell. org/google/>

[CBFalconer]

jacob navia wrote:

>

.... snip ...

>
It must be said too that the malloc/free system is slow too, since at
each allocation request malloc must go through the list of free blocks
trying to find a free one. Memory must be consolidated too, to avoid
fragmentation, and a malloc call can become very expensive, depending
on the implementation and the allocation pattern done by the program.

Not necessarily. My nmalloc for DJGPP, which is believed to be
applicable to most Linux systems, is a counter example. Free
operations are always O(1), in that the system always knows whether
or not any adjacent blocks are free. Allocation normally requires
only one probe, although in the worst case it could become as large
as 24 or so probes. nmalloc also has provisions for detecting most
application errors. The code can be found at:

<http://cbfalconer.home .att.net/download/>

nmalloc is written almost completely in standard C. It requires a
single system call (sbrk) and knowledge about alignment
requirements. The debugging provisions for the actual package
(which are normally disabled) also require non-standard system
calls, such as write. The auxiliary user debuggery system is in
standard C. The package is freely available under the same terms
as the DJGPP system.

--
Some informative links:
<news:news.anno unce.newusers
<http://www.geocities.c om/nnqweb/>
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html >
<http://www.netmeister. org/news/learn2quote.htm l>
<http://cfaj.freeshell. org/google/>

[Richard Heathfield]

CBFalconer said:

Richard Heathfield wrote:

>jacob navia said:

>>Why a Garbage Collector?
-----------------------
Standard C knows only the malloc/calloc/free functions.

Quite so. Please move discussions of non-C matters to some other
newsgroup where it is topical.

I think this particular carp is unfair. Jacob has been
fundamentally advertising the available of the Boehm library for
GC, which I presume is written in standard C, or nearly so.

I'm not convinced (having flicked briefly through the source code).

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Eric Sosman]

jacob navia wrote:

[...]
Standard C knows only the malloc/calloc/free functions. [...]

Jacob is about 75% correct, as usual.

--
Eric Sosman
es*****@acm-dot-org.invalid