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

[Richard Bos]

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

Paul Connolly wrote:

and there are no relatively long (compared to
free()) pauses while garbage collection goes on?

There are pauses, but in modern workstations this is barely noticeable.

Famous last words. Never written a server program? Little bits add up.

wow that's phantastic and incredible.

Write in assembly. That's a *real* language :-)

Wrong. Real programmers _do_ eat quiche. But they bake their own,
because you can't trust fastfood cooks not to give you one of those
sissy quiches Lorraine, or a thing with all fluff and no real meat.

Richard

[William Hughes]

jacob navia wrote:

There are pauses, but in modern workstations this is barely noticeable.

I do not understand. I thought that GC had to scan the entire
amount of memory used by the program. I regularly have programs
that use over a gibabyte of memory. How is this
scanned without a noticable pause?

- William Hughes

[jacob navia]

William Hughes wrote:

jacob navia wrote:

>>There are pauses, but in modern workstations this is barely noticeable.

I do not understand. I thought that GC had to scan the entire
amount of memory used by the program. I regularly have programs
that use over a gibabyte of memory. How is this
scanned without a noticable pause?

- William Hughes

1) When you allocate data structures that have no pointers in it,
just data, you tell the GC that there are no pointers in it and that
it doesn't need to look for pointers in those areas. This is an enormous
improvement.

2)
You use 1GB, but if you allocate your data structures correctly,
(see above) the GC doesn't need to scan all of that. Scanning the
stack and following the roots in there, and scanning the data section
is not very time consuming. A large heap (1GB!)
can cause problems but you should be able to optimize away most of it.

[William Hughes]

jacob navia wrote:

William Hughes wrote:

jacob navia wrote:

>There are pauses, but in modern workstations this is barely noticeable.

I do not understand. I thought that GC had to scan the entire
amount of memory used by the program. I regularly have programs
that use over a gibabyte of memory. How is this
scanned without a noticable pause?

- William Hughes

1) When you allocate data structures that have no pointers in it,
just data, you tell the GC that there are no pointers in it and that
it doesn't need to look for pointers in those areas. This is an enormous
improvement.

But I am not allocating the memory. The memory is being allocated
by a library that I do not control. Even if I could determine where
the memory
was being allocated, I don't know that is contains only data
(knowing that it contains mostly data is not good enough).

- William Hughes

[SM Ryan]

Jean-Marc Bourguet <[e-mail] gwrote:

# Destructors do more than releasing memory. And finalisation is not a
# good substitute for these tasks as finalisation is not synchronous.

If you always know exactly when your destructors are being
called, they're not really destructors--they're methods you
haven't named. Destructors were intended to solve the problem
if collecting anonymous temporaries and the bookkeeping of
collecting local variables and class variables. You know the
destructors will be called before the stack or heap is
overwritten, but the whole point of destructors was you
don't need to know the exact time or place they are called.

If I need to guarentee a program action synchronise to some
external concern, I would have a explicit method to do so
and call it explicitly.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
I ASSURE YOU WE'RE OPEN!

[SM Ryan]

# I do not understand. I thought that GC had to scan the entire
# amount of memory used by the program. I regularly have programs
# that use over a gibabyte of memory. How is this
# scanned without a noticable pause?

Then don't use it.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
You face forward, or you face the possibility of shock and damage.

[jacob navia]

William Hughes wrote:

jacob navia wrote:

>>William Hughes wrote:

>>>jacob navia wrote:

There are pauses, but in modern workstations this is barely noticeable.

I do not understand. I thought that GC had to scan the entire
amount of memory used by the program. I regularly have programs
that use over a gibabyte of memory. How is this
scanned without a noticable pause?

- William Hughes

1) When you allocate data structures that have no pointers in it,
just data, you tell the GC that there are no pointers in it and that
it doesn't need to look for pointers in those areas. This is an enormous
improvement .

But I am not allocating the memory. The memory is being allocated
by a library that I do not control. Even if I could determine where
the memory
was being allocated, I don't know that is contains only data
(knowing that it contains mostly data is not good enough).

- William Hughes

If you are not allocating memory, then you are not deallocating it
either. Then just use the library and be happy...

jacob

[Laurent Deniau]

SM Ryan wrote:

Jean-Marc Bourguet <[e-mail] gwrote:

# Destructors do more than releasing memory. And finalisation is not a
# good substitute for these tasks as finalisation is not synchronous.

If you always know exactly when your destructors are being
called, they're not really destructors--they're methods you
haven't named. Destructors were intended to solve the problem
if collecting anonymous temporaries and the bookkeeping of
collecting local variables and class variables. You know the
destructors will be called before the stack or heap is
overwritten, but the whole point of destructors was you
don't need to know the exact time or place they are called.

If I need to guarentee a program action synchronise to some
external concern, I would have a explicit method to do so
and call it explicitly.

Then you are not familliar with RAII (Ressource Acquisition Is
Initialization) :

{ // code to synchronize
Lock lock();

// user code

} // destructor is called and unlock lock.

This has nothing to do with memory leaks but with potential deadlocks if
an exception is thrown in the user code.

a+, ld.

[William Hughes]

jacob navia wrote:

William Hughes wrote:

jacob navia wrote:

>William Hughes wrote:

jacob navia wrote:

There are pauses, but in modern workstations this is barely noticeable.

I do not understand. I thought that GC had to scan the entire
amount of memory used by the program. I regularly have programs
that use over a gibabyte of memory. How is this
scanned without a noticable pause?

- William Hughes
1) When you allocate data structures that have no pointers in it,
just data, you tell the GC that there are no pointers in it and that
it doesn't need to look for pointers in those areas. This is an enormous
improvement.

But I am not allocating the memory. The memory is being allocated
by a library that I do not control. Even if I could determine where
the memory
was being allocated, I don't know that is contains only data
(knowing that it contains mostly data is not good enough).

- William Hughes

If you are not allocating memory, then you are not deallocating it
either. Then just use the library and be happy...

But the library requires the existence of a free() function at link
time. If I link to a null-op free() then nobody deallocates
memory in the library unless the GC does, in which case
the GC has to scan the whole heap.

O.K. Suppose we solve this problem somehow (we link
the library with another malloc/free and tell the GC to
ignore anything done by the library.) I still have the
problem that if I allocate a large piece of memory I cannot
(now or in the future) store a pointer anywhere in it.
Besides being a maintenance nightmare, this means that
I cannot change from storing a data structure that does
not contain pointers to one that does.

- William Hughes

[Richard Tobin]

In article <11************ **********@f16g 2000cwb.googleg roups.com>,
William Hughes <wp*******@hotm ail.comwrote:

>I do not understand. I thought that GC had to scan the entire
amount of memory used by the program. I regularly have programs
that use over a gibabyte of memory. How is this
scanned without a noticable pause?

There are over 40 years of research on the subject, so it's not
surprising that this problem has been largely overcome.

In particular, many modern garbage collectors avoid scanning the whole
of memory, except perhaps very rarely.

-- Richard