473,900 Members | 4,105 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 6942

jacob navia wrote:
CBFalconer wrote:
William Hughes wrote:
>jacob navia wrote:
... snip ...
>>GC_malloc is compatible with malloc/free. You should not MIX both,
i.e. giving a GC_malloced chunk to free().

This I don't understand. The major problem I see is not the mixing
of calls to free. How can GC_malloc operate correctly, if there
is another malloc operating independently of it? How does GC_malloc
know where it is safe to allocate memory? What happens if the other
malloc (which does not know about GC_malloc) allocates memory
that GC_malloc has already allocated?

This simply means that GC_malloc has to call malloc to get memory.
When the GC system decides that something is freeable, it has to
call free to do it. That means that all the foibles of the malloc
system are still present, including the free delays (see my post
elsethread though), except that those delays can occur at
uncontrolled times. In exchange you get a license to be sloppy
about releasing memory, provided you adhere to other unspecified
restrictions.

The GC calls directly the OS. It knows where are the areas
of virtual memory that it has reserved memory, so it knows if a
word points into its memory areas.
This will probably work if the other implementation of malloc
does not assume that it is the only thing modifying the heap
and act accordingly. I don't know what the present
situation is (the C standard cannot address this problem as
the only way C defines to access the heap is malloc), but
I would guess that assuming that a malloc implementation is
safe to use with other independent memory allocators is
similar to the assumption that an unknown function is
multi-thread safe. I am very short on warm fuzzies.

-William Hughes

Oct 21 '06 #131
William Hughes wrote:
This will probably work if the other implementation of malloc
does not assume that it is the only thing modifying the heap
and act accordingly. I don't know what the present
situation is (the C standard cannot address this problem as
the only way C defines to access the heap is malloc), but
I would guess that assuming that a malloc implementation is
safe to use with other independent memory allocators is
similar to the assumption that an unknown function is
multi-thread safe. I am very short on warm fuzzies.
Look, if you use a brain dead malloc it is not somebody else's
fault. In windows, for instance, you can allocate using malloc, but
also with GlobalAlloc, VirtualAlloc, and a dozen of other functions.
Under unix you have sbrk() and many others.

Any malloc that assumes that all heap is allocated by malloc
is completely brain dead. Besides, WHY would such an assumption
need to be done?

As we advance in the discussion, your arguments become more and more
contrieved.
Oct 21 '06 #132

"William Hughes" <wp*******@hotm ail.comwrote in message
news:11******** **************@ f16g2000cwb.goo glegroups.com.. .
>
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?
Most modern GC uses "generation al scavenging" (as opposed to the old full
stop-and-copy that some older pure functional programming languages had) - a
generation is a partition of the whole allocated memory - with the more
recently allocated memmory being in the first generation to be compacted -
generational scavenging is based on an assumption that the most recently
allocated memory is the most likely to require collection - this is often a
good bet and mitigates the problem of "pauses", but does not eliminate the
problem - well-written malloc/free code will be superior in terms of speed
and amount memory allocated.
Oct 21 '06 #133

"jacob navia" <ja***@jacob.re mcomp.frwrote in message
news:45******** *************** @news.orange.fr ...
Paul Connolly wrote:
>"SM Ryan" <wy*****@tang o-sierra-oscar-foxtrot-tango.fake.orgw rote in
message news:12******** *****@corp.supe rnews.com...
everything? so this garbage collection doesn't use any more memory than
hand written malloc/free code,

Not really. Garbage is automatically collected. You can fine-tune this,
specifying the threshold or call a gc when you think it is a good moment
to do that.
Explicitly calling GC more often isn't free (excuse the pun) - I think it
will slow the execution of my program (I tried explicitly calling GC in an
ASP .NET application - it got slower - the manual warned me it might, but I
wouldn't be told)
>and the application doesn't run slower than hand written malloc/free
code,

No, it doesn't run slower. Allocation is a bit slower since each
allocation does a bit of a GC (incremental GC)
It doesn't run slower but allocation is slower - so does it make up the
ground on freeing? - I find that difficult to believe - the freeing takes
longer under automatic GC - one possibility is that locality of reference is
improved by compaction of the heap and processors with cache might benefit
from that - but is that enough to balance the other work that automatic GC
has to do? - my experience is that languages with automatic GC (ML,
Haskell, Prolog, C#) run slower (admittedly ML, Haskell, Prolog might also
suffer from lack of mutable data, Haskell from laziness, and Prolog from
backtracking)
>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.
>wow that's phantastic and incredible.

Write in assembly. That's a *real* language :-)
Actually I wrote a _little_ bit of assembler this morning, which turned into
this afternoon, as it often does with assembler :-)
Oct 21 '06 #134

"Paul Connolly" <pg********@blu eyonder.co.ukwr ote in message
news:0W******** ********@fe1.ne ws.blueyonder.c o.uk...
>
Most modern GC uses "generation al scavenging" (as opposed to the old full
stop-and-copy that some older pure functional programming languages had) -
a
I thought about this again - generational scavenging works best with pure
functional languages (where every structure refers to earlier created
structures) - assignment means that older structures can be made to refer to
newer ones - making it much more complicated and inefficient to do GC in a
language with destructive assignment - so that makes GC in C even more
inefficient than I first imagined.
Oct 23 '06 #135
"Paul Connolly" <pg********@blu eyonder.co.ukwr ites:
"Paul Connolly" <pg********@blu eyonder.co.ukwr ote in message
news:0W******** ********@fe1.ne ws.blueyonder.c o.uk...
>>
Most modern GC uses "generation al scavenging" (as opposed to the old full
stop-and-copy that some older pure functional programming languages had) -
a

I thought about this again - generational scavenging works best with pure
functional languages (where every structure refers to earlier created
structures) - assignment means that older structures can be made to refer to
newer ones - making it much more complicated and inefficient to do GC in a
language with destructive assignment - so that makes GC in C even more
inefficient than I first imagined.
Strange that Smalltalk, Common Lisp etc have no troubles with GC
than...

Friedrich
--
Please remove just-for-news- to reply via e-mail.
Oct 24 '06 #136
"SM Ryan" <wy*****@tang o-sierra-oscar-foxtrot-tango.fake.orgw rote in
message news:12******** *****@corp.supe rnews.com...
ro******@ibd.nr c-cnrc.gc.ca (Walter Roberson) wrote:
# In article <45************ **********@news .orange.fr>,
# jacob navia <ja***@jacob.re mcomp.frwrote:

[...]
Boehm-Demers garbage collection doesn't work for all programs on
all systems. The systems it has been ported to do work (ie they
have been verified with system libraries and compilers) if you
write your programs in the restricted language.
[...]

FWIW, here is an experimental protoyope of an atomically thread-safe
reference counted pointer:

http://appcore.home.comcast.net/vzoom/refcount/

It has strict C API and the ABI adheres to the C calling convention... You
can use it to do garbage collection like activities:

http://groups.google.com/group/comp....8308f5e7188bb4
Here is some more information:

http://softwareforums.intel.com/ISN/.../30225804.aspx
Enjoy!
;^)

Oct 24 '06 #137
Here is some more information:
>
http://softwareforums.intel.com/ISN/.../30225804.aspx
Just to quick summarize, you can do stuff with this pointer that is
impossible to do with shared_ptr... Perhaps its more flexible... It already
outperforms shared_ptr wrt pointer swaps and weak count updates...

I am hoping that it will get accepted into the Boost library.
Oct 24 '06 #138
In article <87************ @flarge.here>,
Friedrich Dominicus <ju************ *****@q-software-solutions.dewro te:
>"Paul Connolly" <pg********@blu eyonder.co.ukwr ites:
>I thought about this again - generational scavenging works best with pure
functional languages (where every structure refers to earlier created
structures) - assignment means that older structures can be made to refer to
newer ones - making it much more complicated and inefficient to do GC in a
language with destructive assignment - so that makes GC in C even more
inefficient than I first imagined.
>Strange that Smalltalk, Common Lisp etc have no troubles with GC
than...
No, they just have more complicated garbage collectors than would be required
if all pointers pointed backwards.

Pure functional languages don't necessarily have that property - such
a language could perfectly well have a syntax for circular structures.

-- Richard

Oct 24 '06 #139
"Chris Thomasson" <cr*****@comcas t.netwrote:

# FWIW, here is an experimental protoyope of an atomically thread-safe
# reference counted pointer:

How well does it collect cyclic graphs?

--
SM Ryan http://www.rawbw.com/~wyrmwif/
What kind of convenience store do you run here?
Oct 24 '06 #140

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

Similar topics

1
2344
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
2754
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
6458
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
3630
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
3058
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
3206
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
3743
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
12007
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
7963
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
9997
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, weíll explore What is ONU, What Is Router, ONU & Routerís main usage, and What is the difference between ONU and Router. Letís take a closer look ! Part I. Meaning of...
0
9845
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
10866
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
10976
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
10497
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
5891
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...
1
4721
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4301
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3320
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.