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

[jacob navia]

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.

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

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

[jacob navia]

Chris Dollin wrote:

Ben Bacarisse wrote:

>Chris Dollin <ch**********@hp.comwrites:

>>Charlton Wilbur wrote:

I see enough benefits to having a memory management scheme that's
completely deterministic
[which malloc isn't]

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.
If someone offered me the choice: C-with-GC /or/ C-with-namespaces, for
relatively sane versions of namespaces, I'd pick C-with-namespaces in
an instant.

Ack. If I added my own, I'd have C+exceptions or C+simple templates.

>>Why?

Pretty much any C program could usefully use namespaces /right now/.
They impose no run-time overheads. Their specification and implementation
are much less likely to encounter intractable legacy thickets.

For the same reasons.

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

lcc-win implements try/catch since 1997.
Only programs that use try/catch are affected, and then, only those
functions that use try/catch are affected. Other functions
are NOT affected at all.

There is a common cost (of around a few dozens instructions)
by establishing a try/catch around the "main" function. This
is completely negligible in a program that normally executes
millions of instructions.

This implementation of try/catch relies on the support existing
under the windows system for this, and in the C language that
doesn't need destructors. Other languages/Operating systems may
do less well.

Specifically in C++ all programs pay this price. Under linux,
for instance, gcc generates huge tables of data to support
the exception handling mechanism. This makes for code bloat
(data bloat in this case)

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

[Philip Potter]

jacob navia wrote:

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.

I assume you mean "I have been programming in C for relatively few
years" and that you are being ironic (ie you *really* mean "I have been
programming in C for relatively many years").

(Normally I don't correct grammar, but in this case I'm not sure what
you mean and I want to be clear. I hope you don't take offense!)

Anyway, I'd like to reiterate:

>>Jacob, don't quote figures you fabricated then use anecdotal
evidence to back them up.

It's not enough that *you* haven't seen it, even if you *have* been
coding since 1984.

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

That's good then :)

[borkhuis]

On Nov 19, 6:44 pm, jacob navia <[e-mail]:

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

I never had any use for a GC, as probably most developers working on
embedded and/or real time systems. Anything that causes unknown
overhead makes my think a number of times before including it, and
something that is touching memory

When I write my program I think about what areas I need to allocate,
and make sure they are allocated before I my application is started.
And there is no dynamic allocating and freeing memory, as most
embedded developers would agree to.

And as most devices used in the world are embedded devices (which run
usually months or years without problems (and without the need for GC)
I would suggest that you change that number from 99.something to
9.something, which is probably closer to the percentage of software
that can use a GC.

Kind regards,
Johan Borkhuis

[Old Wolf]

On Nov 19, 10:53 pm, "cr88192" <[e-mail]:

after all, if no one really wanted GC, then Java and C# would leave them
out,

non-sequitur. Proprietary languages include all sorts of crap
that a few people want, and then try to convice everybody
that they all need to use the feature (and thus get locked in).

[santosh]

In article <47***********************@news.orange.fr>, jacob navia
<ja***@nospam.orgwrote on Tuesday 20 Nov 2007 5:07 pm:

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.

I guess that intentionally obfuscated (for whatever reasons) programs
might XOR their pointers.

Again I'm guessing that some very old programs, designed to run on
highly memory constrained systems, might write out their state to disk
files, from time to time. Programs (old or recent) that implement some
form of crash recovery or hibernation might also do this.

A GC might not really be suitable for such programs anyway. I don't see
how a Standardised GC will break such programs if it's made an optional
element, much like the intN_t types and bool today.

<snip>

[santosh]

In article <47***********************@news.orange.fr>, jacob navia
<ja***@nospam.orgwrote on Tuesday 20 Nov 2007 5:14 pm:

Chris Dollin wrote:

>Ben Bacarisse wrote:

>>Chris Dollin <ch**********@hp.comwrites:

Charlton Wilbur wrote:

I see enough benefits to having a memory management scheme that's
completely deterministic
[which malloc isn't]

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.
If someone offered me the choice: C-with-GC /or/ C-with-namespaces,
for relatively sane versions of namespaces, I'd pick
C-with-namespaces in an instant.
Ack. If I added my own, I'd have C+exceptions or C+simple
templates.

Why?

Pretty much any C program could usefully use namespaces /right
now/. They impose no run-time overheads. Their specification and
implementation are much less likely to encounter intractable legacy
thickets.
For the same reasons.

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

<snip>

Specifically in C++ all programs pay this price.

<snip>

Is this so? I thought C++ preserved the C spirit of incurring overhead
for only what you actually use?

[Chris Dollin]

Ben Bacarisse wrote:

Chris Dollin <ch**********@hp.comwrites:

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

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.

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.

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

--
Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

[Chris Dollin]

Richard Tobin wrote:

In article <fh**********@tadcaster.hpl.hp.com>,
Chris Dollin <ch**********@hp.comwrote:

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

Java allegedly has exceptions with no run-time overhead: the range of
instructions covered by a "try" is recorded in the symbol table, and
only when an exception occurs is work done to determine what happens.

The instruction-ranges aren't just in the compiler symbol table; they're
in the class-file and subsequently in the tables associated with the
method.

I would count those tables as run-time overhead, but I agree it wasn't
obvious I meant space as well as time.

No doubt this has implications for optimisation, at least.

Indeed. (As I said elsethread, WRT C it isn't clear [to me] whether that
would be additional to the implications from set/longjmp.)

Any [other] C compiler-writers around to comment?

--
Chris "through a beerglass, darkly" Dollin

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

[Chris Dollin]

jacob navia wrote:

I have never seen a program that XOR pointers.

It was at one point the standard hack to do doubly-linked lists
with just one link. (Not in C, perhaps. I seem to remember that
I came across it for the PDP-8, except, since the PDP-8 didn't
have a XOR [1], one used TAD instead.)

[1] For almost all X you might have expected from a processor,
the PDP-8 didn't have X. Like a STORE instruction, or index
registers [2].

[2] For some value of "STORE", or index, or registers.

--
Chris "Mary Hopkins" Dollin

Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

[Richard]

jacob navia <ja***@nospam.orgwrites:

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********@hotmail.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 <[e-mail]:

Ben Bacarisse wrote:

Chris Dollin <[e-mail]:

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 <[e-mail]:

>Ben Bacarisse wrote:

>>Chris Dollin <[e-mail]:
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]:

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 <[e-mail]:

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/informatiquehttp://www.cs.virginia.edu/~lcc-win32

[cr88192]

"Charlton Wilbur" <cw*****@chromatico.netwrote in message
news:87************@mithril.chromatico.net...

>>>>>"cr" == cr88192 <cr*****@hotmail.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*****@chromatico.net

[cr88192]

"Paul Hsieh" <we******@gmail.comwrote in message
news:24**********************************@b40g2000 prf.googlegroups.com...

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

>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.comwrote in message
news:c1**********************************@c29g2000 hsa.googlegroups.com...

On Nov 20, 7:50 am, jacob navia <[e-mail]:

>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(256);
is in potential violation of 2.

....

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

[cr88192]

"Tor Rustad" <to********@hotmail.comwrote in message
news:hJ*********************@telenor.com...

cr88192 wrote:

>"Tor Rustad" <to********@hotmail.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.

I will agree to a point here:
those kind of arrays, IMO, do not belong within the main language.

but, GC is a runtime feature, and it is very sensible that it be left out
for embedded targets.
I was not arguing for standardized GC though, only that GC, itself, has
value.
where and for who it has value, are the people who use it.

to what extent standardization would make sense, would be in terms of a
"standardized" definition of the API and provided functionality and
semantics (said, "portable" GC), but I do not expect by any means that it be
somehow "required" (as is the case with Java and C#, where GC is an assumed
and fundamental part of the language).

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

what do you think I was arguing through most of the thread?...

this is what I was arguing, that using Boehm is a very valid and sensible
option (however, certain other people were opposing that GC has use in C
land, ever...).

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

[CBFalconer]

jacob navia wrote:

>

.... snip ...

>
This change doesn't look good for being able to use third party
libraries compiled with a different compiler...

You can't count on that anyhow. In fact, you expect failure.

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

[CBFalconer]

Paul Hsieh wrote:

>

.... snip ...

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

To bring things back to reality, there is no reason to have a stack
in any C system.

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.
--
Posted via a free Usenet account from http://www.teranews.com

[cr88192]

"CBFalconer" <cb********@yahoo.comwrote in message
news:47***************@yahoo.com...

jacob navia wrote:

>>

... snip ...

>>
This change doesn't look good for being able to use third party
libraries compiled with a different compiler...

You can't count on that anyhow. In fact, you expect failure.

theoretically, yes.

in practicality, one is forced to deal with this issue.

for example, between windows and linux, there are any number of compilers
you can compile code with, and they can make dlls and static libraries.

if one makes their compiler incompatible, say, by using a different calling
convention, then they are unable to use really any code (static libraries,
DLLs, ...) for their platform, and the compiler becomes essentially useless.
so, on x86, there is a singular more or less mandatory calling convention
(cdecl), and on windows, another less-common but still mandatory convention
(stdcall).

on x86-64, there are 2 calling conventions, the SystemV x86-64 convention
(followed by linux and friends), and the Win64 calling convention (windows).

and, again, to be useful on these archs, one needs to support these
conventions (even as such, I have been vaguely tempted to just use my own
convention for x86-64, but this would require, of all horrors, stubbing, to
interface external code).

what convention would I use:
I would actually just "upgrade" the existing 32-bit x86 calling convention
to work on x86-64...
that or use the Win64 convention internally, which should not be too
difficult to support (would just need to come up with some means of creating
a Win64 to SysV adaptor interface...).

or such...

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home.att.net>
Try the download section.

--
Posted via a free Usenet account from http://www.teranews.com

[cr88192]

"CBFalconer" <cb********@yahoo.comwrote in message
news:47***************@yahoo.com...

Paul Hsieh wrote:

>>

... snip ...

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

To bring things back to reality, there is no reason to have a stack
in any C system.

errm?...

what kind of 'reality' is it you are living in?...
I guess it is theoretically possible, but it would lead to incompatibility
and what reason is there that anyone should implement such a thing?...

I guess, maybe you mean, all the call-frames are allocated on the heap, but
then one has to totally re-engineer the calling conventions, recompile all
the libraries, and likely deal with a pretty damn major performance hit.
I guess it could allow things like scheme style continuations, lazy
evaluation, and simplify using fine-grained concurrency (no more "threads",
only 'workers' and 'work queues').
the fact that pretty much every arch has a stack, and those that don't, fake
it, this is telling of its relevance...

[jacob navia]

cr88192 wrote:

"CBFalconer" <cb********@yahoo.comwrote in message
news:47***************@yahoo.com...

>Paul Hsieh wrote:
... snip ...

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

To bring things back to reality, there is no reason to have a stack
in any C system.

errm?...

what kind of 'reality' is it you are living in?...

Mr Falconer has his own world, as many people here around.

A stack is not necessary, one complement or sign magnitude
representations rule the world, etc etc.

I think we have touched a trap representation
:-)

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

[santosh]

In article <fi**********@aioe.org>, jacob navia <ja***@nospam.comwrote
on Wednesday 21 Nov 2007 7:05 pm:

cr88192 wrote:

>"jacob navia" <ja***@nospam.comwrote in message
news:fi**********@aioe.org...

<snip>

>but, it is maybe interesting from a theoretical perspective, aka:
a C-implementation allocating all the call frames on a heap.

so, we want a call frame?
grab it from a free-list (or, somehow, allocate more if needed).

need to store locals? grab a chunk of memory for this and attach to
call frame.
need space for args? likewise, grab a chunk of memory, evaluate and
store in the args, and attach it to the (newly created) call frame of
the function being called.

So, you are implementig the stack in software. Instead of doing a
single register subtract, you allocate memory, put that in the list
of active frames, etc etc!

That would be really bad for performance

I think that with a lot of restrictions on usage a software stack can
compete reasonably well with a hardware one. The actual memory is very
likely to be held in the CPU caches and the machine instructions to
manipulate the stack are also likely to be very similar.

Of course, using a software stack when dedicated hardware support is
available is probably unnecessary unless special flexibility is needed.

And it's not within the spirit of C, as I understand it, to chose
inefficient means to do what _can_ be done more efficiently, time and
space wise.

<snip>

[cr88192]

"santosh" <sa*********@gmail.comwrote in message
news:fi**********@registered.motzarella.org...

In article <fi**********@aioe.org>, jacob navia <ja***@nospam.comwrote
on Wednesday 21 Nov 2007 7:05 pm:

>cr88192 wrote:

>>"jacob navia" <ja***@nospam.comwrote in message
news:fi**********@aioe.org...

<snip>

>>but, it is maybe interesting from a theoretical perspective, aka:
a C-implementation allocating all the call frames on a heap.

so, we want a call frame?
grab it from a free-list (or, somehow, allocate more if needed).

need to store locals? grab a chunk of memory for this and attach to
call frame.
need space for args? likewise, grab a chunk of memory, evaluate and
store in the args, and attach it to the (newly created) call frame of
the function being called.

So, you are implementig the stack in software. Instead of doing a
single register subtract, you allocate memory, put that in the list
of active frames, etc etc!

That would be really bad for performance

I think that with a lot of restrictions on usage a software stack can
compete reasonably well with a hardware one. The actual memory is very
likely to be held in the CPU caches and the machine instructions to
manipulate the stack are also likely to be very similar.

Of course, using a software stack when dedicated hardware support is
available is probably unnecessary unless special flexibility is needed.

And it's not within the spirit of C, as I understand it, to chose
inefficient means to do what _can_ be done more efficiently, time and
space wise.

yes, I agree...

what I was writing about was actually, something a little odd, namely
compiling C in a way very much unlike C...
in effect, it would be compiling C like it were scheme.

as for "special flexibility", at least in scheme implementations, where this
kind of thing is often done, this adds in features like easy support for
continuations and lexical scoping (neither of which are traditionally
present in C).

this is because, with a non-linear memory structure, we can determine, for
example, that something in a function will "capture" the state from that
function (such as the current continuation, part of the lexical scope, ...).
as a result, when the function returns (after this capture has occured), the
call or environment frames are not released (this is possible to determine
statically because things like 'lambda' or 'call/cc' are visible lexically,
though special considerations exist for call/cc).

this is not too terrible of a problem, since, the memory layout is
non-linear, later calls simply use different frames and different memory.
of course, probably a better approach performance-wise would be to switch
out the approach, and only really use call-frames in the case where closures
or continuations are used (closures are easier than continuations, because
although closures are always visible lexically, the use of a continuation
may not be).

luckily, the most common use of a continuation is to implement something
analogous to longjmp (said 'partial' or 'exit-only' continuations). these do
not require as much in terms of special treatment.

but, usage of full continuations are a problem, since they apply potentially
to the entire call graph.

another common approach, makes code itself fast, but call/cc very expensive.
this is an approach focusing around saving/restoring the stack (call/cc
saves the stack, and using a continuation restores it). another approach I
have heard of, is to implement each continuation as a seperate thread (how
this is done in practice I am less certain of, the basic idea is that
call/cc either forks or spawns duplicate threads, and invoking a
continuation causes executon to continue from that thread, or something...).

or such...

<snip>

[Tor Rustad]

cr88192 wrote:

"Tor Rustad" <to********@hotmail.comwrote in message
news:hJ*********************@telenor.com...

>cr88192 wrote:

>>"Tor Rustad" <to********@hotmail.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.

I will agree to a point here:
those kind of arrays, IMO, do not belong within the main language.

but, GC is a runtime feature, and it is very sensible that it be left out
for embedded targets.

Yes, perhaps the fragmentation of memory issue when using GC has been
solved these days, but not long ago, it wasn't AFAIK. Besides, my MISRA
C copy, prohibits non-deterministic memory allocations anyway.

I was not arguing for standardized GC though, only that GC, itself, has
value. where and for who it has value, are the people who use it.

Well, we do discuss in the context of Standard C here, so when a
non-existing features is the subject, particularly when OP is J.N. (!)
-- I assume he want it added.

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

what do you think I was arguing through most of the thread?...

this is what I was arguing, that using Boehm is a very valid and sensible
option (however, certain other people were opposing that GC has use in C
land, ever...).

I have never used GC myself, but has no strong feelings against some
high-level applications using such libraries, but I wouldn't like to see
a GC during audit, in security and/or safety related software.

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

[Paul Hsieh]

On Nov 20, 6:51 pm, CBFalconer <[e-mail]:

Paul Hsieh wrote:
... snip ...

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,

To bring things back to reality, there is no reason to have a stack
in any C system.

Not only are you wrong, but you preface it in a way that makes you
even wronger. Amazing.

Functions calls are to push as return is to pop. It might not be
*called* a stack, but it *IS* a stack, and this has nothing to do with
system implementation details. The C *STANDARD* implicitly implements
a stack.

And as long as we are talking about reality, we should note that most
C implementations use a literal common stack for both return/link
addresses and autos.

You may have meant that you don't need a particular implementation of
a hardware stack. But that's irrelevant to the point I am making. To
run an exception the system, one way or another needs to implement
"pop (return) until catch found" at runtime without actually executing
the returns, which means that a uniform "pseudo-return" has to exist
outside of implicit execution.

Using longjmp is insufficient because you can set catch #1, then call
into something, then set catch #2, then return enough times to make
catch #2 no longer in the call stack scope, thus re-enabling catch
#1. If you throw/raise at this point, you expect catch #1 to be
triggered -- not catch #2, and not vacated entirely (and simply
leading to a runtime error.) That means these catches must exist at
each level of the call stack.

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

[Chris Torek]

(This is now about "stack unwinding", as in throw in C++ or longjmp
in C, rather than GC.)

In article <9c**********************************@t47g2000hsc. googlegroups.com>
Paul Hsieh <we******@gmail.comwrote:

>Functions calls are to push as return is to pop. It might not be
*called* a stack, but it *IS* a stack ...

Indeed, function call and return -- and exception-handling or nested
setjmp() operations -- function as a kind of stack. There are some
significant differences between C and C++ here though, including
the fact that in C, the onus of "using longjmp only in a stack-like
manner" is placed entirely on the C programmer. A C++ programmer
using "throw" cannot accidentally pass an invalid goto-label-buffer
(C's "jmp_buf").

>And as long as we are talking about reality, we should note that most
C implementations use a literal common stack for both return/link
addresses and autos.

Most, but not all. Significantly, many modern compilers optimize
"leaf" procedures to avoid separate stack frames, and some (probably
not as many) will use both "fake" and "real" frame pointers (as on
MIPS CPUs, where a frame pointer is generally used only if the size
of the stack frame varies, e.g., due to C99 VLAs).

>... To run an exception the system, one way or another needs to implement
"pop (return) until catch found" at runtime without actually executing
the returns, which means that a uniform "pseudo-return" has to exist
outside of implicit execution.

One should, however, note that "uniform" can apply only after a
sort of union operation. The stack-unwind code might, for instance,
read something like this (here target_frame is assumed to be given
directly via longjmp; for exceptions it has to be calculated):

target_frame = jmpbuf_info[0]; /* or whatever index */
while (curframe != target_frame) {
switch (calculate_frame_type(curframe)) {
case FRAME_IN_LEAF_FUNCTION: /* can only happen once */
prevframe = jmpbuf_info[1]; /* or whatever */
break;
case FRAME_WITH_REAL_FRAME_POINTER:
prevframe = curframe->prev;
break;
case FRAME_WITH_VIRTUAL_FRAME_POINTER:
prevframe = curframe + compute_offset(curframe);
break;
default:
__panic("longjmp");
/* NOTREACHED */
}
}

>Using longjmp is insufficient because you can set catch #1, then call
into something, then set catch #2, then return enough times to make
catch #2 no longer in the call stack scope, thus re-enabling catch
#1.

Indeed. However, longjmp() is *also* insufficient simply because
it just does not work properly: it may trash any non-"volatile"-qualified
variables local to the target of the longjmp()[*]. But if the compiler
is clever enough (i.e., so that setjmp/longjmp do not destroy local
variable values; and note that longjmp() is provided by the
compiler-writer, who can decide whether his compiler is sufficiently
clever), the same kinds of innards used in longjmp() *can* be used
to implement exceptions, as long as "catch" records something about
the call stack and "throw" can use that to decide whether catch-#2
is "active", for instance.

In the case of several real GCC implementations, throw really does
work a lot like the above, with the target frame being computed
somewhat dynamically and calculate_type_frame() and compute_offset()
being rather complicated operations that match the "instruction
pointer" (PC or IP register, typically) of the supplied frame[%]
against large "exception info" tables, all so that ordinary function
call and return need not manipulate the current catch stack. (In
other words, the compiler throws code-space at the problem, to
avoid a time penalty.)

[* If I had been writing the C standard, I think I would have
forced compiler-writers to handle setjmp/longjmp non-local "goto"
operations "correctly". In other words, I would have put the
burden on compiler-writers instead of C programmers, so that C
programmers would not have to mark variables "volatile" to get
predictable behavior when using longjmp.]

[% Even worse, the return-PC is often not in that frame, but rather
one frame away and/or "adjusted" somehow. Some CPUs save the PC
of the "call" instruction, some save the PC of the "next" instruction.
Some even have funny special-case frames in which multiple PCs are
saved. If longjmp and/or throw are to work across "exception"
frames, including Unix-like signal handlers, these also must be
handled.]
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) [phone]
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Chris Dollin]

Paul Hsieh wrote:

On Nov 20, 4:31 am, Chris Dollin <[e-mail]:

>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 meant optimisation opportunities for the non-exceptional code, not mere
storage for the jmp_buf equivalent.

When you have exceptions, there are (possibly) more places at which the
behaviour of the code is constrained, and hence more places where an
optimisation cannot be applied.

Working out a specification [and implementation] for exceptions-in-C
which is effective /and/ doesn't mess C up for the microoptimisationophiles
is, I believe, non-trivial, and (bringing me back to my earlier position
statement) significantly harder than namespaces would be. IMAO.

--
Chris "glad I don't have to do it" Dollin

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

[Chris Dollin]

cr88192 wrote:

as for "special flexibility", at least in scheme implementations, where this
kind of thing is often done, this adds in features like easy support for
continuations and lexical scoping (neither of which are traditionally
present in C).

Nitpick: C /is/ lexically scoped. What C doesn't have is /full/ lexical
scoping, across nested functions, because it doesn't have nested functions
at all.

[One of the benefits of garbage collection being built-in to a language
is that it can handle the really full bits of lexical scoping where a
function that refers to a local variable from an enclosing function
/can be exported/ as a fully-fledged function object. Doing that with
neither GC nor storage leaks is ... harder.]

--
Chris "seeking a life of ease and comfort" Dollin

Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

[cr88192]

"Tor Rustad" <to********@hotmail.comwrote in message
news:-5*********************@telenor.com...

cr88192 wrote:

>"Tor Rustad" <to********@hotmail.comwrote in message
news:hJ*********************@telenor.com...

>>cr88192 wrote:
"Tor Rustad" <to********@hotmail.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.

I will agree to a point here:
those kind of arrays, IMO, do not belong within the main language.

but, GC is a runtime feature, and it is very sensible that it be left out
for embedded targets.

Yes, perhaps the fragmentation of memory issue when using GC has been
solved these days, but not long ago, it wasn't AFAIK. Besides, my MISRA C
copy, prohibits non-deterministic memory allocations anyway.

ok.

>

>I was not arguing for standardized GC though, only that GC, itself, has
value. where and for who it has value, are the people who use it.

Well, we do discuss in the context of Standard C here, so when a
non-existing features is the subject, particularly when OP is J.N. (!) --
I assume he want it added.

ok.

well, I have not been reading his posts long enough to know what he thinks.

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

what do you think I was arguing through most of the thread?...

this is what I was arguing, that using Boehm is a very valid and sensible
option (however, certain other people were opposing that GC has use in C
land, ever...).

I have never used GC myself, but has no strong feelings against some
high-level applications using such libraries, but I wouldn't like to see a
GC during audit, in security and/or safety related software.

yes, it is not the best idea, everywhere.

I don't expect it to be a magic bullet everywhere or anything. so, for some
subsystems I use it, and for others, I don't.

for example, I have certain libraries in my projects which, very simply,
don't use GC...
a lot depends on the specific design philosophy of that particular
subsystem.
some subsystems are very single-tasked, and generally follow a "closed"
design, and generally do not use any GC or other features (and are very
strict and do not allow any dependency on external code, or, for one of my
libs, severely limits allowed internal access as well).

other libs are a lot more open, and depend on many other subsystems, and
tend to rely fairly heavily on GC.

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

[David Thompson]

On 19 Nov 2007 08:54:05 GMT, ri*****@cogsci.ed.ac.uk (Richard Tobin)
wrote:

In article <87************@bsb.me.uk>,
Ben Bacarisse <be********@bsb.me.ukwrote:

You miss my point. Conservative GC is always "safe" since anything that
even looks like a reference will prevent memory from being freed

In C, you do have to keep pointers as things that look like a

IRRTYM you _don't_ have to.

reference. You can memcpy() the bits of a pointer and shuffle them
up, wait a while, then unshuffle them and store them back in a
pointer. You can even print them out to a file. No GC is going to
handle that unaided.

- formerly david.thompson1 || achar(64) || worldnet.att.net