468,462 Members | 1,858 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,462 developers. It's quick & easy.

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 #1
142 5136
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.

--
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)
Oct 11 '06 #2
in 700822 20061011 175810 Richard Heathfield <in*****@invalid.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?
Oct 11 '06 #3
Bob Martin said:
in 700822 20061011 175810 Richard Heathfield <in*****@invalid.invalid>
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.

Are you telling Jacob to stay out of your playpen?
No, I'm asking him to observe the topicality conventions of Usenet.

--
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)
Oct 11 '06 #4

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. I might well pass a pointer to a third party library and
forget about it.

In my view, any risk is too much to solve a relatively minor
problem, memory leaks, especially as GC can only defend
against true memory leaks. If I keep allocating memory,
remember it (so in theory I could use it), but don't use it
GC is not going to help (now if GC could do anything about
memory stomps ...) .

- William Hughes

Oct 11 '06 #5
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.

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.
In my view, any risk is too much to solve a relatively minor
problem, memory leaks, especially as GC can only defend
against true memory leaks.
No, it defends against double free() too, since you never
call free() all the bugs associated with not calling it
or calling it more than once disappear...

If I keep allocating memory,
remember it (so in theory I could use it), but don't use it
GC is not going to help (now if GC could do anything about
memory stomps ...) .
Well, if you grab memory and memory and memory and you forget
to use it, if you do not keep any pointers to it nothing will happen:

for (i=0; i<100; i++)
a = GC_malloc(100);

only the last block will be protected from the GC, since there is a
pointer to it (a). All others will be reclaimed since there are
no pointers to them.
Oct 11 '06 #6
Bob Martin wrote:
in 700822 20061011 175810 Richard Heathfield <in*****@invalid.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.

Why have this limited view of C, where any deviation from
the holy scriptures is considered an heresy?

This group is about discussions of the C language, and
memory allocation strategies are very important. Why can't we
discuss it here? Because there is no GC in the ISO-Standard?

Nonsense.

jacob
Oct 11 '06 #7
jacob navia <ja***@jacob.remcomp.frwrites:
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.
And standard C is what we discuss in this newsgroup.

[...]
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.
I appreciate the fact that, for a change, you've acknowledged the
limitations of GC.

I suggest, though, that it's up to each programmer to decide whether
these limitations are of any practical significance. It's not
difficult (I would think) to write new code that avoids doing the odd
things with pointer values that can cause GC to fail. It could be
*very* difficult to verify that an existing program is GC-safe, or to
modify one that isn't.
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.
A pause of "less than a second" isn't necessarily going to be a
problem for an interactive program like an IDE. It could be fatal for
more time-sensitive applications. Again, you acknowledge the problem,
but you seem to assume that since it's not an issue for you, it's not
going to be an issue for anyone.

[...]
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.
So it works on Unix-like systems and Windows. If those are the only
systems you use, it's portable enough *for you*, but that doesn't make
it appropriate for a newsgroup that doesn't deal with specific
platforms.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Oct 11 '06 #8

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.
I subtracted 1 (yes, this is undefined behaviour,
unless I cast to an integer type first in which case it is
implementation defined behaviour). The resulting pointer may or may
not be within the bounds of the pointed-to object. But what if
I decided to start indexing at 1000?
>
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.
But I don't know what the foreign library does with the pointer.
What if the guy who wrote the library likes to start indexing from 2K?
What if the gal who wrote the library didn't use C, but wrote
a self modifying encrypted executable using assembler.
In my view, any risk is too much to solve a relatively minor
problem, memory leaks, especially as GC can only defend
against true memory leaks.

No, it defends against double free() too, since you never
call free() all the bugs associated with not calling it
or calling it more than once disappear...
The double free is even more of a minor problem than the
memory leak.
>
If I keep allocating memory,
remember it (so in theory I could use it), but don't use it
GC is not going to help (now if GC could do anything about
memory stomps ...) .

Well, if you grab memory and memory and memory and you forget
to use it, if you do not keep any pointers to it nothing will happen:
And if, as was explicitely stated, I do keep pointers to it?
for (i=0; i<100; i++)
a = GC_malloc(100);

only the last block will be protected from the GC, since there is a
pointer to it (a). All others will be reclaimed since there are
no pointers to them.
I reiterate, in my view the putative advantages of adding GC to C do
not justify even a very small risk

- William Hughes

Oct 11 '06 #9
On Wed, 11 Oct 2006 18:52:54 +0200, jacob navia wrote:
>Conclusions
-----------
The GC is a good alternative to traditional allocation strategies for C
(and C++).
GC is incompatible with C++ (destructors) and inappropriate for the
system programming language C (you didn't even mention the huge memory
overhead of GC).
>The main weakness of the malloc/free system is that it
doesn't scale.
It scales when you use appropriate, well-known idioms like symmetric
*alloc and free calls, or high-level solutions like obstacks.
>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.
You have good tools on most platforms to detect the errors, despite
'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.
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. If you prefer GC in C, go for it. But your
code becomes dependant on a GC and therefore non-portable and
non-reusable (without that GC).

Best regards,
Roland Pibinger
Oct 11 '06 #10
Roland Pibinger wrote:
On Wed, 11 Oct 2006 18:52:54 +0200, jacob navia wrote:
>>Conclusions
-----------
The GC is a good alternative to traditional allocation strategies for C
(and C++).


GC is incompatible with C++ (destructors) and inappropriate for the
system programming language C (you didn't even mention the huge memory
overhead of GC).
Why should the destructors be touched? They just
do not call free() (delete in C++) and that is it.

The rest of C++ goes on like before.
>
>>The main weakness of the malloc/free system is that it
doesn't scale.


It scales when you use appropriate, well-known idioms like symmetric
*alloc and free calls, or high-level solutions like obstacks.
Those solutions are difficult at best.
You need to pass pointers around and store them never forgetting to free
them, etc. Or you impose yourself a HEAVY discipline that cripples your
ability to store pointers freely somewhere to use them as needed.

Example:

Thread A allocates a buffer to display some message. It passes
that message to the thread B, that handles the user interface,
displays strings, asks for input etc. Thread B is not connected
to thread A and calls are asynchronous, using a message passing
interface.

Thread B, then, must free the buffer. But then you must ensure
that all messages are allocated and that no calls are done like:
PostMessageToThreadB("Please enter the file name");
because when thread B attempts to free that it will crash.

Of course YOU know this and YOU will not do this type of call,
but when you were in Arizona in a customer place, programmer Z
had to add a message to the code because customer Y needed a fix and
DID NOT KNOW about your conventions...

Those are examples of *real* life, and software construction is
like that, as you know very well.

It is easy to say here:
"Just use some discipline", but it is MUCH HARDER to keep that
in real life.

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


You have good tools on most platforms to detect the errors, despite
'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.


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 :-)

There is a feature of the GC that allows to call a "destructor"
function, when an object will be destroyed. I haven't talked
about it because I consider it dangerous, since it is not really
a destructor, it will not be called when the variable goes out
of scope, but when the GC discovers that it is no longer used, what
can be MUCH later.

If you prefer GC in C, go for it. But your
code becomes dependant on a GC and therefore non-portable and
non-reusable (without that GC).

Best regards,
Roland Pibinger

Well if you feel like, you can always add the calls to free(), but
then, you would see that it is quite a BORING THING TO DO...
Oct 11 '06 #11
jacob navia said:
Bob Martin wrote:
>in 700822 20061011 175810 Richard Heathfield <in*****@invalid.invalid>
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.


Are you telling Jacob to stay out of your playpen?

I do not know what heathfield has against the GC.
What makes you think I have anything against GC? I have no more objection to
Garbage Collection than I have to tuna, Dusty Springfield, skateboarding,
the tiny little sequins you get on ballgowns, or the Metropolitan District
of South Humberside. None of them happens to be my cup of tea, but I have
no objection to their continued existence. Nor do I have any desire to stop
people talking about them. All I ask is that you do it some place where
they are topical. Automatic garbage collection is no more topical in
comp.lang.c than banana custard or the Falkland Islands.
Why have this limited view of C, where any deviation from
the holy scriptures is considered an heresy?
This is nothing to do with holy scripture, nothing to do with heresy, and
everything to do with topicality.
This group is about discussions of the C language, and
memory allocation strategies are very important.
This group is indeed for discussing the c language, and nuclear defence
strategies are very important. That does not make nuclear defence
strategies topical in comp.lang.c.
Why can't we discuss it here?
You *are* discussing it here. I'm asking you not to, because it's not
topical here. You are free to disagree with me, of course. And I'm free to
think of you as an ignorant bozo with no clue and no brain. Ain't freedom
wonderful?
Because there is no GC in the ISO-Standard?

Nonsense.
Really? Okay, I'll bite - show me where the ISO C Standard defines the
behaviour of GC_malloc.

--
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)
Oct 11 '06 #12
Richard Heathfield wrote:
You are free to disagree with me, of course. And I'm free to
think of you as an ignorant bozo with no clue and no brain.
Please do not write that heathfield. Mr Thompson will immediately
say that I am insulting you...
Oct 11 '06 #13
jacob navia said:
Richard Heathfield wrote:
>You are free to disagree with me, of course. And I'm free to
think of you as an ignorant bozo with no clue and no brain.

Please do not write that heathfield.
Firstly, I didn't say I *do* think of you as an ignorant bozo with no clue
and no brain. I said I'm free to think of you as an ignorant bozo with no
clue and no brain. Whether I *do* think of you as an ignorant bozo with no
clue and no brain depends very much on how long it takes you to grasp the
concept of topicality.

Secondly, you have ignored other people's requests to you not to write some
stuff here in comp.lang.c, so why should anyone pay any attention to your
requests not to write some stuff here in comp.lang.c? You're the "anything
goes" guy, not me, so you should approve that people are free to write
anything they like here, including statements such as "I'm free to think of
you as an ignorant bozo with no clue and no brain".

Note that I maintain the important logical distinction between "I'm free to
think of you as an ignorant bozo with no clue and no brain" and "you're an
ignorant bozo with no clue and no brain". I have said the former but not
the latter, and the former is merely a statement about freedom, not a claim
that you are an ignorant bozo with no clue and no brain - for such a claim
would be in poor taste at best, and I have no desire to make a claim in
poor taste (such as, for example, the claim that you are an ignorant bozo
with no clue and no brain). That would not be polite.

--
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)
Oct 11 '06 #14
On Wed, 11 Oct 2006 19:02:28 +0000, Richard Heathfield
<in*****@invalid.invalidwrote:
Whether I *do* think of you as an ignorant bozo with no
clue and no brain depends very much on how long it takes you to grasp the
concept of topicality.
I can guess, based on the fact that Jacob has been posting off-topic
articles here since at least 2000. IMO, that's quite long enough.

--
Al Balmer
Sun City, AZ
Oct 11 '06 #15
Al Balmer said:
On Wed, 11 Oct 2006 19:02:28 +0000, Richard Heathfield
<in*****@invalid.invalidwrote:
>Whether I *do* think of you as an ignorant bozo with no
clue and no brain depends very much on how long it takes you to grasp the
concept of topicality.

I can guess,
I couldn't possibly comment. :-)

--
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)
Oct 11 '06 #16
On Wed, 11 Oct 2006 18:52:54 +0200, jacob navia
<ja***@jacob.remcomp.frwrote:
>
Why a Garbage Collector?
-----------------------
Standard C knows only the malloc/calloc/free functions.
Which is why your article is off-topic here. If you are proposing that
such a mechanism be added to C, try comp.std.c.

--
Al Balmer
Sun City, AZ
Oct 11 '06 #17
jacob navia wrote:
[inflammatory off-topic crap]
Ok, that's finally enough for a plonk.


Brian
Oct 11 '06 #18
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.
>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? 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.
>In my view, any risk is too much to solve a relatively minor
problem, memory leaks, especially as GC can only defend
against true memory leaks.

No, it defends against double free() too, since you never
call free() all the bugs associated with not calling it
or calling it more than once disappear...
Still does not solve all the other problems.
>If I keep allocating memory,
remember it (so in theory I could use it), but don't use it
GC is not going to help (now if GC could do anything about
memory stomps ...) .

Well, if you grab memory and memory and memory and you forget
to use it, if you do not keep any pointers to it nothing will happen:

for (i=0; i<100; i++)
a = GC_malloc(100);

only the last block will be protected from the GC, since there is a
pointer to it (a). All others will be reclaimed since there are
no pointers to them.
You missed the point again. How about if it keeps adding stuff to a tree
and never deletes nodes that are no longer needed? Then there is always
a way to reach the pointers so they never get freed.

How about memory getting tight enough that some of the programs memory
is paged out to a swap file? Then the GC kicks in and forces those pages
to be reloaded forcing other pages to be swapped out and potentially
causing disk thrashing.

Finally, this is not the place for discussing GC as you well know. So I
am unlikely to post further in this thread even to correct any further
errors you make.
--
Flash Gordon
Oct 11 '06 #19
In article <4p************@individual.net>,
Default User <de***********@yahoo.comwrote:
>jacob navia wrote:
[inflammatory off-topic crap]
Ok, that's finally enough for a plonk.
About 93% of the "[inflammatory off-topic crap]" was written by
heathfield, so I assume that means you are plonking it. Good show!
Wise choice!

Oct 11 '06 #20
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
Oct 11 '06 #21
jacob navia <ja***@jacob.remcomp.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
Oct 11 '06 #22
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.

Oct 11 '06 #23
In article <45***********************@news.orange.fr>,
jacob navia <ja***@jacob.remcomp.frwrote:
>Bob Martin wrote:
>in 700822 20061011 175810 Richard Heathfield <in*****@invalid.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.

Oct 11 '06 #24
On Wed, 11 Oct 2006 20:01:27 +0200, in comp.lang.c , jacob navia
<ja***@jacob.remcomp.frwrote:
>Bob Martin wrote:
>in 700822 20061011 175810 Richard Heathfield <in*****@invalid.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
Oct 11 '06 #25
In article <rp********************************@4ax.com>,
Mark McIntyre <ma**********@spamcop.netwrote:
....
>(rest of Navia's stupid post snipped as it was offensive and
gratuitous)
Oh, the delicious irony...

Oct 11 '06 #26
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.announce.newusers
<http://www.geocities.com/nnqweb/>
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<http://cfaj.freeshell.org/google/>
Oct 12 '06 #27
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.announce.newusers
<http://www.geocities.com/nnqweb/>
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<http://cfaj.freeshell.org/google/>
Oct 12 '06 #28
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)
Oct 12 '06 #29
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
Oct 12 '06 #30
CBFalconer <cb********@yahoo.comwrites:
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 haven't looked at the source, but I doubt that it can be written in
portable standard C. It has to scan memory looking for pointers,
which means making assumptions about how memory is managed (I'm
guessing it only works on systems that use the typical contiguous
hardware stack). I think it also has to examine register contents,
probably using a small amount of assembly language.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Oct 12 '06 #31
Keith Thompson wrote:
CBFalconer <cb********@yahoo.comwrites:
>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 haven't looked at the source, but I doubt that it can be written
in portable standard C. It has to scan memory looking for pointers,
which means making assumptions about how memory is managed (I'm
guessing it only works on systems that use the typical contiguous
hardware stack). I think it also has to examine register contents,
probably using a small amount of assembly language.
Well, my nmalloc has similar restrictions, but I feel free to
mention it here. The following is an excerpt from its source,
spelling out the non-standardisms, if you include the use of sbrk
and alignment values. write and STDERR are used only for the
development debuggery. The user debugger via sysquery.h is
standard, in that it makes no added assumptions about memory
alignment.

#include <stddef.h /* offsetof() */
#include <stdlib.h /* malloc, free, realloc, exit, EXIT_FAILURE
*/
#include <unistd.h /* sbrk, write */
#include <signal.h /* raise, SIGABRT */
#include <string.h /* strlen, memmove, memcpy */
#include <limits.h /* CHAR_BIT, INT_MAX */
#include "sysquery.h" /* available user debugger linkages */

/* system dependant magic. Only STDERR used */
enum {STDIN = 0, STDOUT, STDERR, STDAUX, STDPRN}; /* handles */

/* Incorporation into the system should require deleting the
following <nmalloc.h>, changing all references to nmalloc
to malloc, nfree to free, nrealloc to realloc. Change the
single call to fakesbrk to sbrk. Also normally set all
DEBUGx values above to 0 in place of 1. Later many
routines will be made inline. For debugging compilations
are done with "/Dinline= " switch. For production use
the "/DNDEBUG=1" switch, which does all the above except
the inlining. But see NEWMALLDBG above.
*/

--
Some informative links:
<news:news.announce.newusers
<http://www.geocities.com/nnqweb/>
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<http://cfaj.freeshell.org/google/>

Oct 12 '06 #32
Ben Pfaff <bl*@cs.stanford.eduwrites:
>
Here's a discussion of what I mean:
http://freetype.sourceforge.net/david/reliable-c.html
That's interesting, thansk for posting it.

Regards
Friedrich
--
Please remove just-for-news- to reply via e-mail.
Oct 12 '06 #33
Mark McIntyre wrote:
On Wed, 11 Oct 2006 20:01:27 +0200, in comp.lang.c , jacob navia
<ja***@jacob.remcomp.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.

I thought of calling him "Your Majesty" or "Your Excellence" but
he felt insulted so now I use heathfield. As far as I know it is
not an insult...

But for clc regulars there is NO WAY to satisfy them of course.
Oct 12 '06 #34
jacob navia said:
Mark McIntyre wrote:
>On Wed, 11 Oct 2006 20:01:27 +0200, in comp.lang.c , jacob navia
<ja***@jacob.remcomp.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.
Can you support that claim? I don't remember doing any such thing.
Message-ID please.

I thought of calling him "Your Majesty" or "Your Excellence" but
he felt insulted so now I use heathfield. As far as I know it is
not an insult...

But for clc regulars there is NO WAY to satisfy them of course.
Yes there is. Just stay on topic (and observe common posting conventions).
Other people manage it. Why not you?
--
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)
Oct 12 '06 #35
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.

If you do things like that yes, you should not use the 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.

>>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.
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.
Oct 12 '06 #36
jacob navia said:
Flash Gordon wrote:
>>
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.
Absolutely right. How about that?

--
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)
Oct 12 '06 #37
Roland Pibinger wrote:
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 not how /I/ experience it. GC doesn't make your heapspace
infinite: it just takes care of routine deallocation. It /relies/
on programs having relatively bounded heap use.

It does some tedious bookkeeping for you. There's a price -- there's
/always/ a price -- and in some environments you can't afford it,
in others the benefit isn't worth it, and in yet others the GC
implementation isn't mature and/or has visible stress points.

I /like/ GCd languages. I've been using them for more than twenty
years. Having GC available, especially GC known to the language,
makes a /lot/ of techniques become workable idioms, and when
I'm working in C, I miss them.

But if I /really really/ missed them, I'd know I was writing
in the wrong language. Some languages are good for some things,
and some are good for other things. If I were to be given the
godlike power to improve one feature of C, it isn't GC I'd be
wanting to add: it would be properly integrated modularity,
which I think wouldn't have to change the run-time model at all.

--
Chris "Essen -7 and counting" Dollin
"Never ask that question!" Ambassador Kosh, /Babylon 5/

Oct 12 '06 #38
On Wed, 11 Oct 2006 19:41:47 -0400,
CBFalconer <cb********@yahoo.comwrote
in Msg. <45***************@yahoo.com>
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.
It doesn't even matter if it is standard C or not. Even discussions of
non-standard libaries or debugging tools are frequentely tolerated on
this forum (as long as the matter is either quickly disposed of, or the
thread moved to an appropriate group) because these things are used and
are thus of interest to all in this newsgroup.

But what Jacob does all the time is, indeed, advertising (not just
discussing) off-topical things on this newsgroup, and this latest thread
was obviously kicked off just to rile regulars in general and RH in
particular. And he's getting flamed down for it, as he deserves (and as
close as RH aver gets to flaming).

robert
Oct 12 '06 #39
On Wed, 11 Oct 2006 20:46:40 +0200,
jacob navia <ja***@jacob.remcomp.frwrote
in Msg. <45***********************@news.orange.fr>
There is a feature of the GC that allows to call a "destructor"
function, when an object will be destroyed. I haven't talked
about it because I consider it dangerous,
Oh. For a second there I thought you were going to say, "because I
consider it off-topic".

robert
Oct 12 '06 #40
In article <45**********************@news.orange.fr>,
jacob navia <ja***@jacob.remcomp.frwrote:
>Mark McIntyre wrote:
>On Wed, 11 Oct 2006 20:01:27 +0200, in comp.lang.c , jacob navia
<ja***@jacob.remcomp.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.remcomp.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.announce.newusers
<http://www.geocities.com/nnqweb/>
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<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
>>>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.
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
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.

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********@yahoo.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
fundamentally 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**********************@c28g2000cwb.googlegroups .com>,
William Hughes <wp*******@hotmail.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(CleanupGC);

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 discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

6 posts views Thread by Ganesh | last post: by
11 posts views Thread by Rick | last post: by
34 posts views Thread by Ville Voipio | last post: by
5 posts views Thread by Bob lazarchik | last post: by
8 posts views Thread by mike2036 | last post: by
28 posts views Thread by Goalie_Ca | last post: by
56 posts views Thread by Johnny E. Jensen | last post: by
350 posts views Thread by Lloyd Bonafide | last post: by
158 posts views Thread by pushpakulkar | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.