473,883 Members | 1,837 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Garbage Collection in C

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

Oct 11 '06
142 6919
In article <45************ **********@news .orange.fr>,
jacob navia <ja***@jacob.re mcomp.frwrote:
>Mark McIntyre wrote:
>On Wed, 11 Oct 2006 20:01:27 +0200, in comp.lang.c , jacob navia
<ja***@jacob.r emcomp.frwrote:
>>>
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.

heathfield FORBID ME EXPLICIRELY to call him by his first
name. Before I called him "richard" but HE told me not to do so.
Then I suppose calling him [a] Dick would be right out, as well.

Oct 12 '06 #41
Ben Pfaff wrote:
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
That looks interesting, but I see no obvious way to submit
corrections. For example (after partial reading), he recommends:

int do_something( .... )
{
int error;
char *block1, *block2, *block3;

error = ERR_OK;
block1 = NULL;
block2 = NULL;
block3 = NULL;

block1 = (char*) malloc( 1024 );
if ( block1 == NULL ) goto Fail;

block2 = (char*) malloc( 1024 );
if ( block2 == NULL ) goto Fail;

block3 = (char*) malloc( 1024 );
if ( block3 == NULL ) goto Fail;

.... // do something

Exit:
if (block3) free( block3 );
if (block2) free( block2 );
if (block1) free( block1 );

return error;

Fail:
error = ERR_MALLOC;
goto Exit;
}

which would be better (and more accurately IMO) written as:

int do_something( .... )
{
int error;
char *block1, *block2, *block3;

error = ERR_OK;
block1 = malloc( 1024 );
block2 = malloc( 1024 );
block3 = malloc( 1024 );
if (!block1 || !block2 || !block3) error = ERR_MALLOC
else {
.... /* do something */
}
free( block3 );
free( block2 );
free( block1 );
return error;
}

Use of the ERR_MALLOC and ERR_OK identifiers are also suspect.

Later: Found an email address in the paper, and I have sent a copy
of this article to him.

--
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/>

Oct 12 '06 #42

jacob navia wrote:
Flash Gordon wrote:
jacob navia wrote:
William Hughes wrote:

jacob navia wrote:

[...]

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.
No, but I might well subtract 1 from my pointers to change the
indexing.
This is allowed of course. Your pointer will be within the bounds
of the pointed-to object and that object will NOT be reclaimed since
there is (at least) one pointer to somewhere in it.

You missed William's point entirely.

p = malloc(N * sizeof *p) -1; /* I now have an array indexed by 1 */

Non-standard, but people do it. It means that the pointer is no longer
no longer points in to the object, so the GC will free it.
Well, this is NON-STANDARD. As far as C is concerned, a subtracting
one from the start of an object is undefined behavior.
So. Are you claiming that GC will work on any conforming program?

In any case, by casting from a pointer to an integer, subtracting
the size of an array element, and casting back to a pointer, I get
implementation defined behaviour, which will probably be the
behaviour I want.

If you do things like that yes, you should not use the GC.
And this is my point. If you do things like that you shouldn't use
GC. It took me 30 seconds to come up with that example. This
does not give me a warm fuzzy about GC.
You can
however have the same effect by

p = malloc((1+N) * sizeof *p) ; /* I now have an array indexed by 1 */

You never use the zeroth member and you keep out of undefined behavior.
The fact that you can do things that don't break GC is not the
point. The fact that you can do things that do break GC and that
these things are not that unlikely , is.

>
>I might well pass a pointer to a third party library and
forget about it.

Who cares?

The GC will see it anyway, because the foreign library is part
of your executable.

How to you know the library won't do any of the things that break GC?
Such as paging information, including your pointer, out to disk?

Exvuse me but that is likely to be done by the OS, not by a third party
library.
So? The program may have a better idea of what is going
to be needed next than the OS. In that case the program may well
implement its own "swapping" mechanism. This is certainly not
likely, but it is not that rare either.

Or
compressing it? Or subtracting 1 as above to use it as an array indexed
from 1? IIRC this last is possible if it is a library simply
implementing stuff out of Numerical Recipes in C, something which is
quite possible.

Maybe, I can't guarantee all third party libraries in the world. As far
as I know, and from the experience of people using the GC, that never
happens.
I have used a lot of NR code. Good thing I never used
GC.

- William Hughes

Oct 12 '06 #43
William Hughes wrote:
>>
Well, this is NON-STANDARD. As far as C is concerned, a subtracting
one from the start of an object is undefined behavior.


So. Are you claiming that GC will work on any conforming program?

In any case, by casting from a pointer to an integer, subtracting
the size of an array element, and casting back to a pointer, I get
implementation defined behaviour, which will probably be the
behaviour I want.
>>If you do things like that yes, you should not use the GC.


And this is my point. If you do things like that you shouldn't use
GC. It took me 30 seconds to come up with that example. This
does not give me a warm fuzzy about GC.
As I said, that is undefined behavior in C.
It happens to work in YOUR implementation, it will not work in a
segmented implementation where pointer arithmetic is not defined
at a segment boundaries, for example any 286 compatible processor.
>
>>You can
however have the same effect by

p = malloc((1+N) * sizeof *p) ; /* I now have an array indexed by 1 */

You never use the zeroth member and you keep out of undefined behavior.


The fact that you can do things that don't break GC is not the
point. The fact that you can do things that do break GC and that
these things are not that unlikely , is.
Well, if you do things that are not allowed by the standard
you are in your own.

>
>>>>>I might well pass a pointer to a third party library and
>forget about it.
>

Who cares?

The GC will see it anyway, because the foreign library is part
of your executable.
How to you know the library won't do any of the things that break GC?
Such as paging information, including your pointer, out to disk?

Exvuse me but that is likely to be done by the OS, not by a third party
library.


So? The program may have a better idea of what is going
to be needed next than the OS. In that case the program may well
implement its own "swapping" mechanism. This is certainly not
likely, but it is not that rare either.
It is funny the contortions people will invent to find something that
is against a GC.

We both agree that "this is certainly not likely".
>
Or
>>>compressin g it? Or subtracting 1 as above to use it as an array indexed
from 1? IIRC this last is possible if it is a library simply
implementi ng stuff out of Numerical Recipes in C, something which is
quite possible.

Maybe, I can't guarantee all third party libraries in the world. As far
as I know, and from the experience of people using the GC, that never
happens.


I have used a lot of NR code. Good thing I never used
GC.
NR code invokes undefined behavior if it subtracts one from
the beginning of the array. I repeat. That works in some
implementations , in some others it will break.
Oct 12 '06 #44
William Hughes posted:
So. Are you claiming that GC will work on any conforming program?

It's simple to write a fully-portable GC.

--

Frederick Gotham
Oct 12 '06 #45

jacob navia wrote:
William Hughes wrote:
>
Well, this is NON-STANDARD. As far as C is concerned, a subtracting
one from the start of an object is undefined behavior.

So. Are you claiming that GC will work on any conforming program?

In any case, by casting from a pointer to an integer, subtracting
the size of an array element, and casting back to a pointer, I get
implementation defined behaviour, which will probably be the
behaviour I want.
>If you do things like that yes, you should not use the GC.

And this is my point. If you do things like that you shouldn't use
GC. It took me 30 seconds to come up with that example. This
does not give me a warm fuzzy about GC.

As I said, that is undefined behavior in C.
It happens to work in YOUR implementation, it will not work in a
segmented implementation where pointer arithmetic is not defined
at a segment boundaries, for example any 286 compatible processor.
By strange coincidence I do happen to use my
implementation.
>You can
however have the same effect by

p = malloc((1+N) * sizeof *p) ; /* I now have an array indexed by 1 */

You never use the zeroth member and you keep out of undefined behavior.

The fact that you can do things that don't break GC is not the
point. The fact that you can do things that do break GC and that
these things are not that unlikely , is.

Well, if you do things that are not allowed by the standard
you are in your own.
And if you only do things that are allowed by the standard you
are still on your own.
>

>>>>I might well pass a pointer to a third party library and
forget about it.
Who cares?

The GC will see it anyway, because the foreign library is part
of your executable.
How to you know the library won't do any of the things that break GC?
Such as paging information, including your pointer, out to disk?

Exvuse me but that is likely to be done by the OS, not by a third party
library.

So? The program may have a better idea of what is going
to be needed next than the OS. In that case the program may well
implement its own "swapping" mechanism. This is certainly not
likely, but it is not that rare either.

It is funny the contortions people will invent to find something that
is against a GC.

We both agree that "this is certainly not likely".
Contortions? I have done something very similar.
Thre question is not "Is this likely?", but
"Is this rare enough to be ignored?" My opinion is no.
>

Or

compressing it? Or subtracting 1 as above to use it as an array indexed
from 1? IIRC this last is possible if it is a library simply
implementin g stuff out of Numerical Recipes in C, something which is
quite possible.
Maybe, I can't guarantee all third party libraries in the world. As far
as I know, and from the experience of people using the GC, that never
happens.

I have used a lot of NR code. Good thing I never used
GC.

NR code invokes undefined behavior if it subtracts one from
the beginning of the array. I repeat. That works in some
implementations , in some others it will break.
How do you know. Suppose my NR libraries are
written in Fortran? (Guess which book came first.)

- William Hughes

Oct 12 '06 #46
On Wed, 11 Oct 2006 19:41:47 -0400, CBFalconer <cb********@yah oo.com>
wrote:
>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
fundamentall y advertising the available of the Boehm library for
GC, which I presume is written in standard C, or nearly so.
That doesn't make it topical. He's discussing the product, not the
code. As we keep reminding people here, the fact that a program is
written in C doesn't make discussion of the program itself topical.

--
Al Balmer
Sun City, AZ
Oct 12 '06 #47

Frederick Gotham wrote:
William Hughes posted:
So. Are you claiming that GC will work on any conforming program?


It's simple to write a fully-portable GC.
Which wasn't the question.
It doesn't matter if the GC is written in a combination of
assembler and Lithp ( a programming language that the Igors
use to process lithtths). The question is whether it will
work on any conforming program.
This includes a program that allocates some memory,
xor's a pointer twice with the same string, and
then uses the memory.

- William Hughes

Oct 12 '06 #48
In article <11************ **********@c28g 2000cwb.googleg roups.com>,
William Hughes <wp*******@hotm ail.comwrote:
>The question is whether it will
work on any conforming program.
This includes a program that allocates some memory,
xor's a pointer twice with the same string, and
then uses the memory.
In order to xor a pointer with anything, you would need to
convert the pointer into an integral value, then convert the
integral value to a pointer and have the resulting pointer compare
equal to the original pointer.

C89 and C99 allow implementations to define casting pointers to and
from integral values, but does not define the meaning of that
conversion. C99 promises that the conversion is reversable, but C89
does not (but K&R2 does.)

There is a reversable pointer operation in C89:
printing out and scanning in a pointer with %p format.
I would, though, need to recheck the wording to see whether
implementations are allowed to do nothing useful with %p, and I would
need to recheck to see if there are any constraints on the lifetime
of the reconversion (and do the same checks in C99).

This suggests a variant scheme to yours that has more certainty of
portability: take a pointer, sprintf("%p") it to a string,
reversably munge the string and set the pointer to NULL. Invoke
or hypothesize a GC at that point. Now unmunge the string and sscanf("%p")
it back into the pointer. If this is done within the same function,
then surely any potential lifetime constraints on the %p reversability
would be met, so the doubly converted pointer would be valid -- but
any GC scheme that invokes mark/sweep operations would consider
the area unreachable and might release it.
--
There are some ideas so wrong that only a very intelligent person
could believe in them. -- George Orwell
Oct 12 '06 #49
William Hughes posted:
>It's simple to write a fully-portable GC.

Which wasn't the question.
It doesn't matter if the GC is written in a combination of
assembler and Lithp ( a programming language that the Igors
use to process lithtths). The question is whether it will
work on any conforming program.
This includes a program that allocates some memory,
xor's a pointer twice with the same string, and
then uses the memory.
Why do think it might not work? I don't see any barriers.

Even something as primitive as the following should work, although "gc.h"
would have to be included _after_ all Standard headers.

/* FILE BEGIN: gc.h */

#include <stddef.h>

void *mallocGC(size_ t const len);

#undef malloc
#undef free

#define malloc mallocGC
#define free ((void)0)

/* FILE END: gc.h */

/* FILE BEGIN: gc.c */

#include <stddef.h>
#include <stdlib.h>

typedef struct AllocLink {
void *p;
struct AllocLink *p_prev;
} AllocLink;

static AllocLink first_link = {0,0};
static AllocLink *plink = &first_link;

void *mallocGC(size_ t const len)
{
static void CleanupGC(void) ;

static int first_time = 1;
AllocLink *const p_new_link = malloc(sizeof *p_new_link);

if (!p_new_link) return 0;

p_new_link->p = malloc(len);

if(!p_new_link->p) { free(p_new_link ); return 0; }

p_new_link->p_prev = plink;

plink = p_new_link;

if(first_time) first_time = 0, atexit(CleanupG C);

return plink->p;
}

static void CleanupGC(void)
{
AllocLink *p_prev;

do
{
free(plink->p);
p_prev = plink->p_prev;
free(plink);
plink = p_prev;
} while(plink->p);
}

/* FILE END: gc.c */

--

Frederick Gotham
Oct 12 '06 #50

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
2341
by: Bob | last post by:
Are there any known applications out there used to test the performance of the .NET garbage collector over a long period of time? Basically I need an application that creates objects, uses them, and then throws them away and then monitors the garbage collection and store statistics on it, preferably in C#. I want to know what is the longest period of time that an application may lock up while garbage collection is processing. Thanks!
6
810
by: Ganesh | last post by:
Is there a utility by microsoft (or anyone) to force garbage collection in a process without have access to the process code. regards Ganesh
11
2752
by: Rick | last post by:
Hi, My question is.. if Lisp, a 40 year old language supports garbage collection, why didn't the authors of C++ choose garbage collection for this language? Are there fundamental reasons behind this? Is it because C is generally a 'low level' language and they didn't want garbage collection to creep into C++ and ruin everything? Just wondering :)
34
6449
by: Ville Voipio | last post by:
I would need to make some high-reliability software running on Linux in an embedded system. Performance (or lack of it) is not an issue, reliability is. The piece of software is rather simple, probably a few hundred lines of code in Python. There is a need to interact with network using the socket module, and then probably a need to do something hardware- related which will get its own driver written in C.
5
3628
by: Bob lazarchik | last post by:
Hello: We are considering developing a time critical system in C#. Our tool used in Semiconductor production and we need to be able to take meaurements at precise 10.0 ms intervals( 1000 measurement exactly 10 ms apart. In the future this may decrease to 5ms ). I am concerned that if garbage collection invokes during this time it may interfere with our measurement results. I have looked over the garbage collection mechanism and see no...
8
3056
by: mike2036 | last post by:
For some reason it appears that garbage collection is releasing an object that I'm still using. The object is declared in a module and instantiated within a class that is in turn instantiated by the mainline. The class that instantiated the object in question is definitely still in existence at the point garbage collection swoops in and yanks it out from under my processing. Is there a way to ensure an instantiated object cannot be freed...
28
3202
by: Goalie_Ca | last post by:
I have been reading (or at least googling) about the potential addition of optional garbage collection to C++0x. There are numerous myths and whatnot with very little detailed information. Will this work be library based or language based and will it be based on that of managed C++? Then of course there are the finer technical questions raised (especially due to pointer abuse). Is a GC for C++ just a pipe dream or is there a lot of work...
56
3736
by: Johnny E. Jensen | last post by:
Hellow I'am not sure what to think about the Garbage Collector. I have a Class OutlookObject, It have two private variables. Private Microsoft.Office.Interop.Outlook.Application _Application = null; Private Microsoft.Office.Interop.Outlook.NameSpace _Namespace = null; The Constructor: public OutlookObject()
350
11979
by: Lloyd Bonafide | last post by:
I followed a link to James Kanze's web site in another thread and was surprised to read this comment by a link to a GC: "I can't imagine writing C++ without it" How many of you c.l.c++'ers use one, and in what percentage of your projects is one used? I have never used one in personal or professional C++ programming. Am I a holdover to days gone by?
158
7951
by: pushpakulkar | last post by:
Hi all, Is garbage collection possible in C++. It doesn't come as part of language support. Is there any specific reason for the same due to the way the language is designed. Or it is discouraged due to some specific reason. If someone can give inputs on the same, it will be of great help. Regards, Pushpa
0
9796
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
11152
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10753
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10859
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9582
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
5804
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
5997
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
4225
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3239
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.