By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,433 Members | 776 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,433 IT Pros & Developers. It's quick & easy.

C garbage collection -crazy idea

P: n/a
This idea might be vey crazy. But I hope to get answers to this .. from
comp.lang.c

If a compiler is designed such that it automatically adds a free()
matching every malloc()
then is it not a garbage collection (in the first place , garbage will
not be generated !! ) . Is it
possible to have a compiler with such feature. Or if Its not a good
idea (or may be this is an idiotic idea) please tell me why is it so ??

Thanks,

Dec 15 '06 #1
Share this Question
Share on Google+
28 Replies


P: n/a
onkar wrote:
This idea might be vey crazy. But I hope to get answers to this .. from
comp.lang.c

If a compiler is designed such that it automatically adds a free()
matching every malloc()
then is it not a garbage collection (in the first place , garbage will
not be generated !! ) . Is it
possible to have a compiler with such feature. Or if Its not a good
idea (or may be this is an idiotic idea) please tell me why is it so ??

Thanks,
Fun idea though, but I think you may try C++ auto_ptrs.
I don't think auto-free would be wrote into C standards.

Dec 15 '06 #2

P: n/a
onkar wrote:
This idea might be vey crazy. But I hope to get answers to this .. from
comp.lang.c

If a compiler is designed such that it automatically adds a free()
matching every malloc()
then is it not a garbage collection (in the first place , garbage will
not be generated !! ) . Is it
possible to have a compiler with such feature. Or if Its not a good
idea (or may be this is an idiotic idea) please tell me why is it so ??
How is the compiler supposed to know /where/ to add the `free` call?

--
Chris "halting problem" Dollin
The shortcuts are all full of people using them.

Dec 15 '06 #3

P: n/a
onkar said:
This idea might be vey crazy. But I hope to get answers to this .. from
comp.lang.c

If a compiler is designed such that it automatically adds a free()
matching every malloc()
....then you wouldn't be able to use it for translating any existing C
programs that correctly call free().

And how would it know when to call free()? I'll be the judge of that, thank
you.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Dec 15 '06 #4

P: n/a
onkar wrote:
This idea might be vey crazy. But I hope to get answers to this .. from
comp.lang.c

If a compiler is designed such that it automatically adds a free()
matching every malloc()
then is it not a garbage collection (in the first place , garbage will
not be generated !! ) . Is it
possible to have a compiler with such feature. Or if Its not a good
idea (or may be this is an idiotic idea) please tell me why is it so ??
How would the compiler react to this?

int x, i;
....
int **foo = malloc (sizeof *foo * x);
....
for (i=0; i<x; i++) {
foo[i] = malloc (sizeof *foo[i]);
}
....

How many calls to free should there be, and where should
they be placed?

goose,
google for Boehm GC for C.

Dec 15 '06 #5

P: n/a
Richard Heathfield wrote:
onkar said:
>This idea might be vey crazy. But I hope to get answers to this .. from
comp.lang.c

If a compiler is designed such that it automatically adds a free()
matching every malloc()

...then you wouldn't be able to use it for translating any existing C
programs that correctly call free().
If -- I say /if/ -- the compiler could correctly deduce where to put
the matching malloc, then it could also discard the explicit calls
to free.
And how would it know when to call free()? I'll be the judge of that, thank
you.
Verily. (For values of "verily" that mean "GC is wonderful and the
machine can do a better job of store management than I can, but C
isn't meant for the kind of programs that benefit -- if I have a GC
environment I'm sure as heck that I won't waste it on writing C
when there are lots of GC-exploiting idioms I could be using instead.")

--
Chris "short word, long meaning" Dollin
"Our future looks secure, but it's all out of our hands"
- Magenta, /Man and Machine/

Dec 15 '06 #6

P: n/a
Chris Dollin wrote:
If -- I say /if/ -- the compiler could correctly deduce where to put
the matching malloc,
The matching /free/.

What idiot wrote that snippet?

--
Chris "rhetorical" Dollin
"- born in the lab under strict supervision -", - Magenta, /Genetesis/

Dec 15 '06 #7

P: n/a


On Fri, 15 Dec 2006, onkar wrote:
This idea might be vey crazy. But I hope to get answers to this .. from
comp.lang.c

If a compiler is designed such that it automatically adds a free()
matching every malloc()
The question is *when* to insert the call to free(). When the function
that called malloc() returns? But in many cases memory allocated via
malloc() is used even after the function that performed the allocation
returns. So, in order to know when it is appropriate to call free(), you
need a more elaborate scheme (reference counting and tracking) which is
what a garbage collector does.

then is it not a garbage collection (in the first place , garbage will
not be generated !! ) . Is it
possible to have a compiler with such feature. Or if Its not a good
idea (or may be this is an idiotic idea) please tell me why is it so ??
Garbage collectors incur a run-time penalty. Therefore most C
implementations won't use it. However, the C language by itself does not
explicitly forbid using garbage collection. In fact there are some
performant implementations of garbage collectors available.

See the following link for an implementation of a garbage collector for C
and C++.

http://www.hpl.hp.com/personal/Hans_Boehm/gc/
Emil
>
Thanks,

Dec 15 '06 #8

P: n/a
On Fri, 15 Dec 2006 11:36:33 +0000, Chris Dollin wrote:
>onkar wrote:
>If a compiler is designed such that it automatically adds a free()
matching every malloc()
then is it not a garbage collection (in the first place , garbage will
not be generated !! ) . Is it
possible to have a compiler with such feature. Or if Its not a good
idea (or may be this is an idiotic idea) please tell me why is it so ??

How is the compiler supposed to know /where/ to add the `free` call?
The compiler just needs to add the 'free' call(s) in the same scope in
which *alloc is called (in inverse order). When a pointer to allocated
memory is returned from the scope no call to free has to be performed.
I guess that would not be difficult to implement but is not compatible
to current C and therefore unrealistic.

Best wishes,
Roland Pibinger
Dec 15 '06 #9

P: n/a
af
I wouldn't say automatic placing of free() statements is a *crazy*
idea. To my point of view, this is a good idea, first. 

I believe It is quite possible to detect a lot of places where to add
free() with static code analysis. I can do it by examining code, so the
clever program also should be able to do this. It would save a lot of
$$ to issue at least a warning for such case. The only problem is
compiler developers are too busy to develop such checks, and static
code analyzers repay their high price.

I know the only free tool for static code analysis [1], and it is
unable to validate memory allocation. Probably one can improve it in
this direction. BTW, there are plenty of runtime leak detectors such as
[2].

[1] CCCC tool, http://sourceforge.net/projects/cccc
[2] Leaky, http://lxr.mozilla.org/mozilla/sourc...aky/leaky.html

With best regards,
Alexei

"""onkar писал(а):
"""
This idea might be vey crazy. But I hope to get answers to this .. from
comp.lang.c

If a compiler is designed such that it automatically adds a free()
matching every malloc()
then is it not a garbage collection (in the first place , garbage will
not be generated !! ) . Is it
possible to have a compiler with such feature. Or if Its not a good
idea (or may be this is an idiotic idea) please tell me why is it so ??

Thanks,
Dec 15 '06 #10

P: n/a
Roland Pibinger said:
On Fri, 15 Dec 2006 11:36:33 +0000, Chris Dollin wrote:
>>onkar wrote:
>>If a compiler is designed such that it automatically adds a free()
matching every malloc()
then is it not a garbage collection (in the first place , garbage will
not be generated !! ) . Is it
possible to have a compiler with such feature. Or if Its not a good
idea (or may be this is an idiotic idea) please tell me why is it so ??

How is the compiler supposed to know /where/ to add the `free` call?

The compiler just needs to add the 'free' call(s) in the same scope in
which *alloc is called (in inverse order).When a pointer to allocated
memory is returned from the scope no call to free has to be performed.
Doesn't that kind of defeat the purpose? It certainly would for me, since
most of my pointers-to-allocated-memory end up getting returned by the
function in which they are defined.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Dec 15 '06 #11

P: n/a

Roland Pibinger wrote:
On Fri, 15 Dec 2006 11:36:33 +0000, Chris Dollin wrote:
onkar wrote:
If a compiler is designed such that it automatically adds a free()
matching every malloc()
then is it not a garbage collection (in the first place , garbage will
not be generated !! ) . Is it
possible to have a compiler with such feature. Or if Its not a good
idea (or may be this is an idiotic idea) please tell me why is it so ??
How is the compiler supposed to know /where/ to add the `free` call?

The compiler just needs to add the 'free' call(s) in the same scope in
which *alloc is called (in inverse order).
Nope. Not a good idea.

There are many examples where the results of malloc() are or can be
passed out of scope, to the next level higher. I certainly don't want
my compiler to throw away the deliberately malloc()ed memory that my
node allocation function in my binary tree builder grabbed. It is up to
the node deallocation function to do that.
When a pointer to allocated
memory is returned from the scope no call to free has to be performed.
/If/ I grant you this, then you have not only "improved" the garbage
collection, you have crippled the ability to use dynamically allocated
memory in conjunction with function calls. Sorry, but I believe that
the freedom I already have wrt function calls is not worth trading away
in that manner.
I guess that would not be difficult to implement
You might be surprised at how difficult this is to implement
/correctly/.
but is not compatible to current C
Or past C, or (if I understand correctly) future C, either
and therefore unrealistic.
--
Lew

Dec 15 '06 #12

P: n/a
Roland Pibinger wrote:
On Fri, 15 Dec 2006 11:36:33 +0000, Chris Dollin wrote:
>>onkar wrote:
>>If a compiler is designed such that it automatically adds a free()
matching every malloc()
then is it not a garbage collection (in the first place , garbage will
not be generated !! ) . Is it
possible to have a compiler with such feature. Or if Its not a good
idea (or may be this is an idiotic idea) please tell me why is it so ??

How is the compiler supposed to know /where/ to add the `free` call?

The compiler just needs to add the 'free' call(s) in the same scope in
which *alloc is called (in inverse order). When a pointer to allocated
memory is returned from the scope no call to free has to be performed.
I guess that would not be difficult to implement but is not compatible
to current C and therefore unrealistic.
Not compatible with being useful, either.

--
Chris "Perikles triumphant" Dollin
A rock is not a fact. A rock is a rock.

Dec 15 '06 #13

P: n/a
On Fri, 15 Dec 2006 13:10:24 +0000, Richard Heathfield wrote:
>Roland Pibinger said:
>The compiler just needs to add the 'free' call(s) in the same scope in
which *alloc is called (in inverse order).When a pointer to allocated
memory is returned from the scope no call to free has to be performed.

Doesn't that kind of defeat the purpose? It certainly would for me, since
most of my pointers-to-allocated-memory end up getting returned by the
function in which they are defined.
Not necessarily most. It depends on the programming style. You use
'bottom-up' I prefer 'top-down'. Even if some allocated memory is
returned from the function especially string manipulation would
benefit from a 'local' alloc (which should have names different from
the known *alloc functions, e.g. lmalloc).

Best regards,
Roland Pibinger
Dec 15 '06 #14

P: n/a
On 15 Dec 2006 05:11:33 -0800, "Lew Pitcher" wrote:
>Roland Pibinger wrote:
>The compiler just needs to add the 'free' call(s) in the same scope in
which *alloc is called (in inverse order).

Nope. Not a good idea.
There are many examples where the results of malloc() are or can be
passed out of scope, to the next level higher. I certainly don't want
my compiler to throw away the deliberately malloc()ed memory that my
node allocation function in my binary tree builder grabbed. It is up to
the node deallocation function to do that.
Ok, then call those functions lmalloc ('local malloc') ... and
everything is clear. You can assign locally allocated memory to local
variables and pass it to other functions but you cannot return it or
assign it to non-local variables. In a sense alloca does something
similar (but only on the stack).

Best wishes,
Roland Pibinger
Dec 15 '06 #15

P: n/a
On 15 Dec 2006 03:59:10 -0800, "goose" wrote:
>How would the compiler react to this?

int x, i;
...
int **foo = malloc (sizeof *foo * x);
...
for (i=0; i<x; i++) {
foo[i] = malloc (sizeof *foo[i]);
}
...

How many calls to free should there be, and where should
they be placed?
How would you do it manually? The compiler would roughly do the same.
Dec 15 '06 #16

P: n/a

Roland Pibinger wrote:
On 15 Dec 2006 05:11:33 -0800, "Lew Pitcher" wrote:
Roland Pibinger wrote:
The compiler just needs to add the 'free' call(s) in the same scope in
which *alloc is called (in inverse order).
Nope. Not a good idea.
There are many examples where the results of malloc() are or can be
passed out of scope, to the next level higher. I certainly don't want
my compiler to throw away the deliberately malloc()ed memory that my
node allocation function in my binary tree builder grabbed. It is up to
the node deallocation function to do that.

Ok, then call those functions lmalloc ('local malloc') ... and
everything is clear. You can assign locally allocated memory to local
variables and pass it to other functions but you cannot return it or
assign it to non-local variables. In a sense alloca does something
similar (but only on the stack).
First off, I don't see the difference between your proposed lmalloc()
function and "automatic storage", other than your proposed lmalloc()
needs new compiler magic, where "automatic storage" does not.

Consider

{
struct a { int aa; char ab;};
struct a element, *ptr_to_element; /* "automatic storage" */
ptr_to_element = &element;

/* do useful work with element, ptr_to_element */

} /* element, ptr_to_element automatically deallocated */

vs

{
struct a { int aa; char ab;};
struct a *ptr_to_element;

ptr_to_element = lmalloc(sizeof *ptr_to_element);

/* do useful work with ptr_to_element */

} /* ptr_to_elementt automagically deallocated */

Of course, "automatic storage" doesn't need to be checked for
successful allocation, where your lmalloc() does. OTOH, "automatic
storage" only allocates the object and you have to derive a pointer in
code, where your lmalloc() only provides the pointer, which you must
use in all later work.

To me, your lmalloc() proposal is a half-measure. If you are going to
change the compiler and the language to perform an automatic garbage
collection, you might as well make it work properly and not require a
function call to allocate something that will not (and must not) be
deallocated by a function call. So, why not just add a new language
element instead of your lmalloc()? How about

{
struct a { int aa; char ab;};
new struct a *ptr_to_element; /* keyword "new" takes the place of
lmalloc() */

/* do useful work with ptr_to_element */

} /* ptr_to_elementt automagically deallocated */

Of course, now we've made the complete tranformation to a new language
that looks like C++.

Dec 15 '06 #17

P: n/a
2006-12-15 <45***************@news.utanet.at>,
Roland Pibinger wrote:
On 15 Dec 2006 05:11:33 -0800, "Lew Pitcher" wrote:
>>Roland Pibinger wrote:
>>The compiler just needs to add the 'free' call(s) in the same scope in
which *alloc is called (in inverse order).

Nope. Not a good idea.
There are many examples where the results of malloc() are or can be
passed out of scope, to the next level higher. I certainly don't want
my compiler to throw away the deliberately malloc()ed memory that my
node allocation function in my binary tree builder grabbed. It is up to
the node deallocation function to do that.

Ok, then call those functions lmalloc ('local malloc') ... and
everything is clear. You can assign locally allocated memory to local
variables and pass it to other functions but you cannot return it or
assign it to non-local variables. In a sense alloca does something
similar (but only on the stack).
alloca is not a standard function. Also, GNU "libiberty" contains
a version of alloca that uses "the heap" (i.e. it calls malloc and
automatically frees stuff later)
Dec 15 '06 #18

P: n/a
2006-12-15 <11**********************@f1g2000cwa.googlegroups. com>,
af@ipclearingboard.com wrote:
BTW, there are plenty of runtime leak detectors such as [2].

[2] Leaky, http://lxr.mozilla.org/mozilla/sourc...aky/leaky.html
Or valgrind, which is, as far as I can tell, a bit more well-known, but
doesn't specifically support xpcom.
Dec 15 '06 #19

P: n/a
onkar <on*******@gmail.comwrote:
Newsgroups: comp.lang.c

This idea might be vey crazy. But I hope to get answers to this .. from
comp.lang.c

If a compiler is designed such that it automatically adds a free()
matching every malloc()
then is it not a garbage collection (in the first place , garbage will
not be generated !! ) . Is it
possible to have a compiler with such feature. Or if Its not a good
idea (or may be this is an idiotic idea) please tell me why is it so ??

Thanks,
You can allocate on the stack and not on the heap.
in this case the memory will be freed automatically
when leaving the function.

See 'man alloca'

------------------------------------------
CoverageMeter Software Factory
Code Coverage Tool for C/C++ <
Homepage: http://www.coveragemeter.com
------------------------------------------
Dec 15 '06 #20

P: n/a
in**@coveragemeter.com said:

<snip>
You can allocate on the stack and not on the heap.
in this case the memory will be freed automatically
when leaving the function.

See 'man alloca'
But bear in mind that alloca() may not be available on your system. It is
not a standard C library function.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Dec 15 '06 #21

P: n/a

Roland Pibinger wrote:
On 15 Dec 2006 03:59:10 -0800, "goose" wrote:
How would the compiler react to this?

int x, i;
...
int **foo = malloc (sizeof *foo * x);
...
for (i=0; i<x; i++) {
foo[i] = malloc (sizeof *foo[i]);
}
...

How many calls to free should there be, and where should
they be placed?

How would you do it manually? The compiler would roughly do the same.
It cannot; it does not have enough information at compile-time
to determine how many free() calls are needed. What if I read the
value x from a file at runtime?

goose,

Dec 15 '06 #22

P: n/a
"goose" <ru**@webmail.co.zawrites:
Roland Pibinger wrote:
>On 15 Dec 2006 03:59:10 -0800, "goose" wrote:
>How would the compiler react to this?

int x, i;
...
int **foo = malloc (sizeof *foo * x);
...
for (i=0; i<x; i++) {
foo[i] = malloc (sizeof *foo[i]);
}
...

How many calls to free should there be, and where should
they be placed?

How would you do it manually? The compiler would roughly do the same.

It cannot; it does not have enough information at compile-time
to determine how many free() calls are needed. What if I read the
value x from a file at runtime?
The compiler can generate a loop as easily as you can. But I'd be
very very surprised if something like this could be implemented
usefully.

--
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.
Dec 15 '06 #23

P: n/a
In article <6v******************************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:
>If a compiler is designed such that it automatically adds a free()
matching every malloc()
>...then you wouldn't be able to use it for translating any existing C
programs that correctly call free().
It could do what existing garbage collectors for C do, and replace
free() with a no-op function. Of course, when he said the compiler
would add calls to free() he meant real_free().
>And how would it know when to call free()? I'll be the judge of that, thank
you.
If you could correctly judge it for all my programs, it would be very
helpful.

-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
Dec 16 '06 #24

P: n/a

Keith Thompson wrote:
"goose" <ru**@webmail.co.zawrites:
Roland Pibinger wrote:
On 15 Dec 2006 03:59:10 -0800, "goose" wrote:
How would the compiler react to this?

int x, i;
...
int **foo = malloc (sizeof *foo * x);
...
for (i=0; i<x; i++) {
foo[i] = malloc (sizeof *foo[i]);
}
...

How many calls to free should there be, and where should
they be placed?

How would you do it manually? The compiler would roughly do the same.
It cannot; it does not have enough information at compile-time
to determine how many free() calls are needed. What if I read the
value x from a file at runtime?

The compiler can generate a loop as easily as you can. But I'd be
very very surprised if something like this could be implemented
usefully.
Why? alloca can be implemented in such a way that it allocates from
the "heap" not the "stack". Basically, to implement a malloca, you
just call malloc and keep a list of things you need to free along with
the point at which you need to free them. If you design your functions
to use a single exit point then you can do this yourself, you don't
even need compiler support (with the minor proviso that if a variable
goes out of scope there is a "memory leak" till the end of the
function).

- William Hughes.

- William Hughes
--
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.
Dec 16 '06 #25

P: n/a
"onkar" <on*******@gmail.comwrote:
# This idea might be vey crazy. But I hope to get answers to this .. from
# comp.lang.c
#
# If a compiler is designed such that it automatically adds a free()
# matching every malloc()

If you want automatic garbage collection, use the auto or register
storage class.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
Death is the worry of the living. The dead, like myself,
only worry about decay and necrophiliacs.
Dec 16 '06 #26

P: n/a
Richard Tobin said:
In article <6v******************************@bt.com>,
Richard Heathfield <rj*@see.sig.invalidwrote:
<snip>
>>And how would it know when to call free()? I'll be the judge of that,
thank you.

If you could correctly judge it for all my programs, it would be very
helpful.
If the rate is right...

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
Dec 16 '06 #27

P: n/a

onkar wrote:
This idea might be vey crazy. But I hope to get answers to this .. from
comp.lang.c

If a compiler is designed such that it automatically adds a free()
matching every malloc()
then is it not a garbage collection (in the first place , garbage will
not be generated !! ) . Is it
possible to have a compiler with such feature. Or if Its not a good
idea (or may be this is an idiotic idea) please tell me why is it so ??

Thanks,
First of all, you might want to check out the Boehm-Demers-Weiser GC
(http://en.wikipedia.org/wiki/Boehm_GC for basic information,
http://www.hpl.hp.com/personal/Hans_Boehm/gc/ for the home page).

What you're describing isn't exactly garbage collection. GC is usually
dynamic, rather than static.

Dec 17 '06 #28

P: n/a
On Fri, 15 Dec 2006 13:40:18 GMT, rp*****@yahoo.com (Roland Pibinger) wrote:
On 15 Dec 2006 05:11:33 -0800, "Lew Pitcher" wrote:
>>Roland Pibinger wrote:
>>The compiler just needs to add the 'free' call(s) in the same scope
in which *alloc is called (in inverse order).

Nope. Not a good idea.
There are many examples where the results of malloc() are or can be
passed out of scope, to the next level higher. I certainly don't want
my compiler to throw away the deliberately malloc()ed memory that my
node allocation function in my binary tree builder grabbed. It is up
to the node deallocation function to do that.

Ok, then call those functions lmalloc ('local malloc') ... and
everything is clear. You can assign locally allocated memory to local
variables and pass it to other functions but you cannot return it or
assign it to non-local variables. In a sense alloca does something
similar (but only on the stack).
This doesn't really solve the problem Lew Pitcher described.

One of the features of the current malloc()/free() model is that you can
allocate an object deeply inside the call stack, i.e. when the program's
call stack looks like:

main()
copytree()
maketree()
makenode()
malloc()

Return the pointer to the malloc'd object all the way up to copytree(),
do some other unrelated work (i.e. sort the nodes of the tree), and then
free() the allocated memory in a different place, deeply inside another
call stack:

main()
savetree()
writenode()
deletenode()
free()

By forcing all free() operations to be always in the same scope of their
respective malloc() call, you cannot use this programming model.

Dec 27 '06 #29

This discussion thread is closed

Replies have been disabled for this discussion.