Garbage collection problems

[jacob navia]

As many people know, I think that garbage collection is a good
solution for many memory allocation problems.

I am aware however, that nothing is "the silver bullet", not
even the GC.

A recent article in slashdot
http://developers.slashdot.org/artic.../11/17/0552247
proves that.

A C# application was leaking memory, and the application would
become slower and slower because the memory was getting full and the
system was swapping like mad until it just failed.

Why?

Because a list that should be destroyed wasn't being destroyed.
This is similar to another bug that Sun discovered in their
Java implementation. The list wasn't being destroyed because
SOMEWHERE there was a reference to that list, and the GC could
not destroy it.

It is interesting to note that this bug is as difficult to trace as
a missing free or similar bugs. It required a specialized tool
to find it (yes, there are specialized tools to solve GC memory
allocation problems as there are specialized tools to solve
non-gc memory allocation problems)

The lesson to be learned is that you have to be careful (when using the
GC) to
1) Set all pointers to unused memory to NULL.
2) Do NOT store pointers to GC memory in permanent structures if you
want that data to eventually be collected.

The above bug was that the list registered itself in a global
data structure and wasn't getting destroyed.

If the GC wouldn't have been there, the programmer would have freed
the memory, what would have closed the memory leak but left
a dangling pointer in the global data structure!

Not a better alternative.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32

[Richard]

jacob navia <ja***@nospam.o rgwrites:

Philip Potter wrote:

>jacob navia wrote:

>>???

You XOR pointers?

You write pointer to files?

It doesn't matter what /I/ do, but what the previous programmers on
the same project did; and we all know it's a mistake to make
assumptions about such people.

I have never seen a program that XOR pointers.
Neither one that writes pointers to disk, then reads them back.
Sorry, I am programming in C since relatively few years. I
started around 1984.

Thats silly.

Conceivably a distributed system could store a block of pointers on a
remote node for a while via a remote copy which does not increment local
system reference counts. There are lots of things which can cause it to
fail. And if people become too reliant on it it would be a *nightmare*
to find the cause of a problem since none of the mallocs have frees to
match against.

The bottom line is this (using my typically black and white views of
such things) : Garbage Collection sucks. It promotes lazy programming
and a "get it all for free" mentality and is partly responsible for the
bloatware which is now regularly released .

Few seem to consider memory footprint anymore.

>

>(A side point: does your GC count a pointer to the middle of an
array as a reference? If not, that's another (much more common) case
where memory could be erroneously freed.)

It counts as a reference of course.

[Tor Rustad]

jacob navia wrote:

Tor Rustad wrote:

>jacob navia wrote:

>>As many people know, I think that garbage collection is a good
solution for many memory allocation problems.

Right, but I'm more interested in knowing what Richard Heathfield
would have liked C99 to include, but C99 didn't. :)

Yes, that is obvious. You live and love for R.H.

Your garbage collector appears to be broken.

--
Tor <bw****@wvtqvm. vw | tr i-za-h a-z>

[Tor Rustad]

cr88192 wrote:

"Tor Rustad" <to********@hot mail.comwrote in message

[...]

>IMO, the main domain of C is system and embedded development. Even if
extending this domain by including communication, security development and
DB engine development, a GC seems neither important, or of much interest.

errm, are you trying to claim that all of us good old desktop-pc developers
are all off using stuff like Java and C# or something?...

No, I say that C1X should focus on the main domain of C, and try to keep
the language small and simple. The C99 variable-length arrays was a step
too far. Adding GC to Standard C, would IMO be a major mistake.

must of us are in a land where we still want things like GC, but don't feel
like selling our souls to some proprietary VM framework to get it.

Nobody is stopping you from using the Boehm GC.

--
Tor <bw****@wvtqvm. vw | tr i-za-h a-z>

[Paul Hsieh]

On Nov 20, 4:31 am, Chris Dollin <chris.dol...@h p.comwrote:

Ben Bacarisse wrote:

Chris Dollin <chris.dol...@h p.comwrites:

I /think/ that adding exceptions would introduce run-time overheads: I
could of course be wrong.

It forces call stack uniformity (the EH needs to be able to crawl up
the stack and unwind the stack in a uniform way.) So for example,
tail-call recursion might not be able to be turned into gotos if there
is a potential for exceptions to be thrown under a call inside that
tail recursion (actually, I don't know that for sure -- but its one of
those things you would have to check very carefully). I also know
that compilers such as WATCOM C/C++ definitely use very non-uniform
stack frames whenever they can get away with it, for leaf-function
optimization reasons.

If you mean a cost incurred by program that don't even use them (just
in case)

If an entire program doesn't use any EH, then you'd expect the overhead to
be minimal.

If the entire program is one file, then sure -- the compiler could
detect this and drop the overly-uniform call-stack frames. However,
more real projects are multi-file, and not very many compilers do link-
time recompiling (though Intel's compiler does that).

It might not be zero, unless there's a way to tell the compiler to
compile compilation units assuming that they'll be used in an EH-free
program: it's possible that code that might execute in an EH
environment might suffer optimisation penalties. On the other hand,
I don't see that they'd be much different from any penalties already
paid for set/longjmp.

The set/longjmp storage is handled by the programmer. With EH, it has
to dynamically be stored somewhere -- presumably in the stack itself
(this seems to be the only solution that would make sense in multi-
threaded environments.)

I seem to recall that earlier C++ compilers had this sort of EH-controlling
switch. (Not having using C++ in anger recently, I don't know about
current C++ compilers, not even specifically g++.)

Watcom and Microsoft definitely retain those switches.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[jacob navia]

Paul Hsieh wrote:

On Nov 20, 4:31 am, Chris Dollin <chris.dol...@h p.comwrote:

>Ben Bacarisse wrote:

>>Chris Dollin <chris.dol...@h p.comwrites:
I /think/ that adding exceptions would introduce run-time overheads: I
could of course be wrong.

It forces call stack uniformity (the EH needs to be able to crawl up
the stack and unwind the stack in a uniform way.) So for example,
tail-call recursion might not be able to be turned into gotos if there
is a potential for exceptions to be thrown under a call inside that
tail recursion (actually, I don't know that for sure -- but its one of
those things you would have to check very carefully). I also know
that compilers such as WATCOM C/C++ definitely use very non-uniform
stack frames whenever they can get away with it, for leaf-function
optimization reasons.

This is only true if your language needs destructors.
C doesn't need that, so all that does not apply.

--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32

[Paul Hsieh]

On Nov 20, 12:40 am, Philip Potter <[e-mail] .ukwrote:

jacob navia wrote:

Keith Thompson wrote:

jacob navia wrote:
Normal applications like 99.9999 C applications that can use the GC
without any problems!

Is 99.9999 intended to be an exaggeration, or do you really think the
number is that high (I assume it's a percentage)?

How many applications you have seen that write pointers into
disk files, xor pointers or do such kind of nonsense?

I have never seen one.

Jacob, don't quote figures you fabricated then use anecdotal evidence to
back them up. That's just not science.

Lol! Can you point me to any other "science" being practiced in this
newsgroup? Come on now, aside from some pointer arithmetic (which
Boehm has not problem with)

[...] Unless you have done proper
research across a wide cross-section of application domains and coding
groups, the fact that you've never seen one means precisely zilch. (I
have seen precisely zero uses of ptrdiff_t - I guess it doesn't exist,
right?)

The Better String Library uses ptrdiff_t to deal with aliasing in a
conservative and portable way.

It doesn't matter how many people can use GC successfully, it matters
how many /can't/

Jacob's response to you here is very on point. GC is being proposed
to deal with the much worse problem of dealing with malloc and free.
The problems that might happen due to misuse of GC will be a drop in
the ocean compared with the rampant memory leaks C programmers create
today.

[...] - and because the sort of problems that we're talking
about, the errors are of the intermittent runtime difficult-to-debug
variety. If I can't be absolutely sure that I can use your GC on my
standard C program, I won't bother. I'd have to go through the entire
program to make sure it doesn't do 'clever' stuff with pointers; or
start a new C-with-GC program from scratch (but I wouldn't do that
because I'd be stuck with one compiler on one platform).

You are worried about non-opaque (and non-pointer offsetting) pointer
manipulation? No matter what it is you have in mind, its almost
certainly a violation of the standard. Writing pointers to a file
then reading them back? That's extremely brittle coding that I would
be very scared of -- disks can fail, and be accessed asynchronously by
other processes.

Real programs don't do this sort of nonsense. We're talking about a
percentage that is way less than the coverage missed by a typical test
suite for even the best software.

This is why the Boehm collector exists, and is being used in real
production code today.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Francine.Neary]

On Nov 20, 7:50 am, jacob navia <ja...@nospam.o rgwrote:

Keith Thompson wrote:

jacob navia wrote:

Normal applications like 99.9999 C applications that can use the GC
without any problems!

Is 99.9999 intended to be an exaggeration, or do you really think the
number is that high (I assume it's a percentage)?

How many applications you have seen that write pointers into
disk files, xor pointers or do such kind of nonsense?

I have never seen one.

Surely the point is that if you want to propose a *standardized* GC
(which would be better done in comp.std.c), then what does and doesn't
break it will need to be specified!

You could either do this negatively:
"As long as you don't xor pointers or write them to disk or ...
(expand 'such kind of nonsense' here) or ... then your program can use
GC safely"

or positively:
"You're allowed to store arbitrarily many pointers in arbitrarily deep
linked sequences, add offsets to them, cast them(?), ..., and GC is
guaranteed to work"

Either way, it seems to me that you'll end up with an extremely long
and unwieldy list of conditions if you want to cover all bases. If you
can't express an idea cleanly, that might indicate that there's
something wrong with it...

>
--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatiquehtt p://www.cs.virginia .edu/~lcc-win32

[cr88192]

"Charlton Wilbur" <cw*****@chroma tico.netwrote in message
news:87******** ****@mithril.ch romatico.net...

>>>>>"cr" == cr88192 <cr*****@hotmai l.comwrites:

crafter all, if no one really wanted GC, then Java and C# would
crleave them out, and things like Boehm, and the endless other
crcustom GC frameworks, would simply not be used.

Of course. *Someone* wants garbage collection. At times, even *I*
want garbage collection. But you cannot go from that statement, which
you have provided adequate evidence for, to your original claim that
*most* programmers want garbage collection without a whole lot more
evidence than you have thus far provided.

I see enough benefits to having a memory management scheme that's
completely deterministic and completely in the hands of the programmer
that I don't want to see it go away as an option. And (as has been
pointed out) the semantics of C make it very difficult to use a
garbage collector that's implemented as a library; I think the
effort's better spent elsewhere.

who ever said I wanted malloc to go away?...

I say, we have the GC, and we have malloc.

maybe they can share the same implementation, or maybe they dont.
in any case, I am not arguing that we abandon malloc and put everything in
the hands of the GC, rather, I argue, we have both options available, and
use each where it makes sense.

so, I argue for availability, and that it is a worthwhile option, not
mandatory usage, or even abandoning manual memory management approaches
(when it so happens that they make the most sense...).

for example, my new gc has a function, said, 'gcfree()', and what does it
do? it frees things. why? because freeing something ealier makes things a
lot faster than waiting for the heap to get full and the GC to reclaim it...
as for said "difficulty ". I have used garbage collection in my projects for
many years, and have never had much difficulty with it (apart from dealing
with certain cases, such as a previous version of my GC, when used as the
core of a previous script lang, being too damn slow and having to collect
the heap too damn often...).

Charlton

--
Charlton Wilbur
cw*****@chromat ico.net

[cr88192]

"Paul Hsieh" <we******@gmail .comwrote in message
news:24******** *************** ***********@b40 g2000prf.google groups.com...

On Nov 20, 12:40 am, Philip Potter <[e-mail] .ukwrote:

>jacob navia wrote:

Keith Thompson wrote:
jacob navia wrote:
Normal applications like 99.9999 C applications that can use the GC
without any problems!

>Is 99.9999 intended to be an exaggeration, or do you really think the
number is that high (I assume it's a percentage)?

How many applications you have seen that write pointers into
disk files, xor pointers or do such kind of nonsense?

I have never seen one.

Jacob, don't quote figures you fabricated then use anecdotal evidence to
back them up. That's just not science.

Lol! Can you point me to any other "science" being practiced in this
newsgroup? Come on now, aside from some pointer arithmetic (which
Boehm has not problem with)

it is the science of edge-cases and arguing...

>[...] Unless you have done proper
research across a wide cross-section of application domains and coding
groups, the fact that you've never seen one means precisely zilch. (I
have seen precisely zero uses of ptrdiff_t - I guess it doesn't exist,
right?)

The Better String Library uses ptrdiff_t to deal with aliasing in a
conservative and portable way.

>It doesn't matter how many people can use GC successfully, it matters
how many /can't/

Jacob's response to you here is very on point. GC is being proposed
to deal with the much worse problem of dealing with malloc and free.
The problems that might happen due to misuse of GC will be a drop in
the ocean compared with the rampant memory leaks C programmers create
today.

yes.
I use to do this some before I discovered GC.

if I could not determine well enough if/when things needed to be freed, I
didn't bother.
I also tended to end up with apps that would randomly "explode" as well...
eventually, I started implementing custom memory managers, and later,
garbage collectors, as a way of battling this problem...

the general structure of these allocators tends to remain the same though:
I allocate memory in large "chunks" (say, 256kB or 1MB). these chunks were
then divided into a large number of objects, which were allocated and freed.

some of my early allocators used linked lists and best-fit, but tended to be
kind of slow (especially when I had mark/sweep GCs, as a long time during
sweep was used up positionally inserting every freed object into the free
list...).

later on (starting in about 2002 and since), pretty much all my allocators
have been cell-based (each block is a large array of fixed-size cells
managed by bitmaps).

>[...] - and because the sort of problems that we're talking
about, the errors are of the intermittent runtime difficult-to-debug
variety. If I can't be absolutely sure that I can use your GC on my
standard C program, I won't bother. I'd have to go through the entire
program to make sure it doesn't do 'clever' stuff with pointers; or
start a new C-with-GC program from scratch (but I wouldn't do that
because I'd be stuck with one compiler on one platform).

You are worried about non-opaque (and non-pointer offsetting) pointer
manipulation? No matter what it is you have in mind, its almost
certainly a violation of the standard. Writing pointers to a file
then reading them back? That's extremely brittle coding that I would
be very scared of -- disks can fail, and be accessed asynchronously by
other processes.

Real programs don't do this sort of nonsense. We're talking about a
percentage that is way less than the coverage missed by a typical test
suite for even the best software.

it is brittle, but I have heard of a few apps doing this kind of thing.
an example of this is some forms of persistent store, where part (or all) of
the heap is stored to a file.

of course, these kind of apps usually do a custom heap (a custom memory
manager over some large mmaped block of memory), always mmap the file in the
same place, and disallow any pointers to memory outside this region.
of course, this has little to do with whether or not the implementation has
GC, since such memory is completely outside the control of the GC anyways...

of course, this is only one of several ways to implement a persistent
store...

This is why the Boehm collector exists, and is being used in real
production code today.

yes, it is used, because it is usable...

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[cr88192]

<Fr************ @googlemail.com wrote in message
news:c1******** *************** ***********@c29 g2000hsa.google groups.com...

On Nov 20, 7:50 am, jacob navia <ja...@nospam.o rgwrote:

>Keith Thompson wrote:

jacob navia wrote:
Normal applications like 99.9999 C applications that can use the GC
without any problems!

Is 99.9999 intended to be an exaggeration, or do you really think the
number is that high (I assume it's a percentage)?

How many applications you have seen that write pointers into
disk files, xor pointers or do such kind of nonsense?

I have never seen one.

Surely the point is that if you want to propose a *standardized* GC
(which would be better done in comp.std.c), then what does and doesn't
break it will need to be specified!

You could either do this negatively:
"As long as you don't xor pointers or write them to disk or ...
(expand 'such kind of nonsense' here) or ... then your program can use
GC safely"

or positively:
"You're allowed to store arbitrarily many pointers in arbitrarily deep
linked sequences, add offsets to them, cast them(?), ..., and GC is
guaranteed to work"

Either way, it seems to me that you'll end up with an extremely long
and unwieldy list of conditions if you want to cover all bases. If you
can't express an idea cleanly, that might indicate that there's
something wrong with it...

I don't think the list has to be "that" long or unweildy (after all, most of
the C standard would have to be filled with such lists in that case).

for example, here are a few general requirements for my GC:
1. pointers to GC'ed objects need to be located in GC-reachable memory to be
GC-reachable;
2. pointers need to be stored in aligned memory locations (this much is done
by the compiler);
3. a pointer is required to point somewhere inside the object being pointed
to;
4. an GC'ed object is not required to be retained if not GC-reachable at any
point in time.

and, provisions:
data, bss, and the main and gc-known thread stacks are reachable;
the search depth is only bounded by the ability to create a sufficiently
large trace stack;
....

so, no xor'ing, as this violates 3.
no files, strings, or malloc'ed memory, as this violates 1 and 4;
care needs be taken when mixing GC and byte-arrays, due to 2.

for example:
char a[4];
*((void **)a)=gcalloc(2 56);
is in potential violation of 2.

....

>>
--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatiquehtt p://www.cs.virginia .edu/~lcc-win32