Question about garbage collection

Question about garbage collection

[Centaury]

One question about access type garbage collection.
I understand that when an access object is no longer pointed at by an access
variable, the space taken by object would usually be reclaimed.
One question. . if the object itself is a record that has an access type in
it, and that object is pointing at another object, but not pointed at; would
it be considered lost and would the space be reclaimed??

Let me put it in illustration:

head --> ("myname",link) --> ("yourname", link) --> null
                ^
                |
                |
              ("hisname", link) -->null

will the space resided by ("hisname", link) be recovered by garbage
collector??

Regards,
Centaury

Re: Question about garbage collection

[Matthew Heaney]

In article <6h851g$sq$1@news.tm.net.my>, "Centaury" <utopian@tm.net.my> wrote:

>One question about access type garbage collection.
>I understand that when an access object is no longer pointed at by an access
>variable, the space taken by object would usually be reclaimed.
>One question. . if the object itself is a record that has an access type in
>it, and that object is pointing at another object, but not pointed at; would
>it be considered lost and would the space be reclaimed??
>
>Let me put it in illustration:
>
>head --> ("myname",link) --> ("yourname", link) --> null
>                ^
>                |
>                |
>              ("hisname", link) -->null
>
>will the space resided by ("hisname", link) be recovered by garbage
>collector??

Ada the language is designed to permit inclusion of a garbage collection,
but few implementations of Ada have a garbage collector.  (The only one I
know about is the AppletMagic tool from Intermetrics.)

So, reclaimation of objects on the heap is not done automatically. 
(However, objects on the stack are reclaimed automatically, as usual.)

In your example, none of the objects on the heap will get reclaimed
automatically, although I don't completely understand your example.  Here's
another one:

type Integer_Access is access all Integer;

procedure Allocate is
   IP : constant Integer_Access := new Integer;
begin
  null;
end;

When you exit the scope of Allocate, you'll have generated some garbage,
because you allocated an Integer object on the heap, and there aren't any
access objects designating the object.

Re: Question about garbage collection

[Ed Falis]

Matthew Heaney wrote in article ...

>>Ada the language is designed to permit inclusion of a garbage collection,
>but few implementations of Ada have a garbage collector.  (The only one I
>know about is the AppletMagic tool from Intermetrics.)

ObjectAda for Windows and UNIX are compatible with Geodesic Systems' Great
Circle gc.

Ed Falis
Aonix

Re: Question about garbage collection

[Robert Dewar]

Ed says

<<ObjectAda for Windows and UNIX are compatible with Geodesic Systems' Great
Circle gc.
>>

I assume this is a conservative garbage collector. This is not the same as
true GC, but is often quite effective. I would guess most Ada compilers would
be compatible with a number of packages of this type. Basically any compiler
that uses malloc and free in a conventional manner wlil be compatible (the
use of certain techniques like virtual origins can mess things up). People
have used a number of different conservative collectors with GNAT successfully.

THe conservative collectors work by not compacting memory, and by holding onto
memory if any pointer *might* (rather than does) reference a block (e.g. if
an integer value just happens to match the address of a block, then the block may be
preserved.

True garbage collection has to be effectively integrated into the compiler,
since it must know the data types of everything. This is quite tricky in the
presence of variant records and class wide types.

It would be a nice project to try to add true GC to GNAT, but no one has
tried this yet that I am aware of. It is not impossi ble to do (the GCC
Modula 3 compiler has true GC).

Re: Question about garbage collection

[Fergus Henderson]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

>Ed says
>
><<ObjectAda for Windows and UNIX are compatible with Geodesic Systems' Great
>Circle gc.
>>>
>
>I assume this is a conservative garbage collector. This is not the same as
>true GC, but is often quite effective.

Damning with faint praise?

I've heard that Ada is not a true programming language,
but is often quite effective. ;-)

--
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3        |     -- the last words of T. S. Garp.

Re: Question about garbage collection

[Robert Dewar]

Fergus says

<<>I assume this is a conservative garbage collector. This is not the same as
>true GC, but is often quite effective.

Damning with faint praise?
>>


No, I did not mean to be that negative at all. I meant it when I said this
is often quite effective. It is easy to construct cases where it fails
completely (e.g. a circular structure that in its entirety could be
collected), but in practice, it works pretty well a lot of the time,
and in an application where the only penalty for not collecting perfectly
is performance rather than malfunction, conservative garbage collection
is attractive precisely because it is simple, reliable, and does NOT
require all sorts of complexity added to the compiler.

Re: Question about garbage collection

[raw]

In article <dewar.893122395@merv>,
  dewar@merv.cs.nyu.edu (Robert Dewar) wrote
about conservative garbage collectors:
>
> .... It is easy to construct cases where it fails
> completely (e.g. a circular structure that in its entirety could be
> collected), ....

This would be an example where reference counting fails.
Conservative garbage collectors could remove such a structure
unless some bit pattern somewhere accessible could be a
pointer to some part of the structure.

--
MJSR

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading

Re: Question about garbage collection

[Robert Dewar]

<<Probably.  I believe Robert Dewar doesn't much like so-called
"conservative" gc.  I tend to agree -- it seems like a hack that's
required for languages like C, which are not designed to make gc easy.
And for compilers designed without gc in mind (whether or not the
language is).  And it makes me uneasy that memory can't be compacted.
>>

I never said that! In fact I find the conservative GC approach a clever one,
but it is important not to confuse it with real GC, such as is found in a
typical Modula-3, Algol-68, SNOBOL4, LISP or Java system.

With true GC, you have an invariant that after a collection, an object is
not present if it is not referenced, and you can analyze worst case
storage requirements on this basis. Obviously no such analysis is possible
with conservative GC.

But as I said before, if the primary reason for GC is to improve performance
by reducing memory requirements, then conservative GC is a cheap way to 
achieve this goal.

Whether it is a hack is a point of view. THe point is that the constraints
on the use of malloc and free are pretty simple to state, and the collector
itself is fairly simple, so this approach has the advantage of avoiding a
lot of the implementaiton complexity that is common in trying to provide
true GC for high level languages.

Re: Question about garbage collection

[William Tanksley]

In article <dewar.893163406@merv> dewar@merv.cs.nyu.edu (Robert Dewar) writes:

><<Probably.  I believe Robert Dewar doesn't much like so-called
>"conservative" gc.  I tend to agree -- it seems like a hack that's
>required for languages like C, which are not designed to make gc easy.
>And for compilers designed without gc in mind (whether or not the
>language is).  And it makes me uneasy that memory can't be compacted.
>>>

>I never said that! In fact I find the conservative GC approach a clever one,
>but it is important not to confuse it with real GC, such as is found in a
>typical Modula-3, Algol-68, SNOBOL4, LISP or Java system.

>With true GC, you have an invariant that after a collection, an object is
>not present if it is not referenced, and you can analyze worst case
>storage requirements on this basis. Obviously no such analysis is possible
>with conservative GC.

I don't really care for this definition.  It omits the possibility of
generational or otherwise incremental GC.  These are both very powerful
and useful GC methods.

>But as I said before, if the primary reason for GC is to improve performance
>by reducing memory requirements, then conservative GC is a cheap way to 
>achieve this goal.

In the same way that any heuristic algorithm can achieve its goal --
usually outperforming the exact algorithm by an amazing amount.

Honestly, I think that talking about 'true' GC is strongly misleading.  I
could understand 'strong' GC and 'weak' GC, or 'exact' GC and 'heuristic'
GC, but 'true' and 'false'?  Whew.

Shouldn't be used.  Unless, of course, one is comparing reference counting
to GC...  :-)  Even in a conservative GC, garbage will always _eventually_
be collected, and is never lost.  In reference counting garbage can be
lost.

-Billy

Re: Question about garbage collection

[Robert Dewar]

Billy said

<<Shouldn't be used.  Unless, of course, one is comparing reference counting
to GC...  :-)  Even in a conservative GC, garbage will always _eventually_
be collected, and is never lost.  In reference counting garbage can be
lost.
>>

Obviously we are not agreeing on terminology here. I am using 
conservative GC to refer to the technique where you hold on to something
if there is anything that *looks like* a retaining address in some other
live block. Obviously with this definition you can hold on to arbitrary
amounts of garbage for arbtrarily long.

Re: Question about garbage collection

[Robert Dewar]

Bob Duff said

<<I agree.

All gc's are necessarily conservative, in that they don't always collect
all memory the program will never use again.  To be perfect, the gc
would need to predict the future, which is of course impossible.
>>

I did not mean to be contentious in using the word true, so let's use the
word octopus instead

I define octopus GC (OGC for short from now on)
to be a scheme in which memory is only retained if
there is a live pointer through which some future execution path of
the program might access the memory, and I specificaly exclude the notion
of static or dynamic analysis of future possible behavior.

So a block is live if it is a root, or, recursively if it is referenced
by a pointer in a live block.

OGC is for example implemented in typical SNOBOL4 and Algol-68 compilers.

The point about OGC is that you can analyze maximum memory usage patterns
of your program, just as you can in a program in which all memory allocation
is explicit.

The issue of compaction is enirely orthogonal. One can have compaction in
malloc/free regimes, or compaction in GC regimes. It tends to be the case
that compaction goes with GC, but that is by no means fundamental in either
direction.

If there is no compaction, then your analysis must take into account
fragnmentation effects in either case.

Bob said

<<Methinks the primary reason for GC is to avoid dangling pointers.
And the secondary reason is to avoid memory leaks.>>

That's an odd way of putting it, but I see what you mean. Obviously it is
possible to avoid both DP's and ML's with a conventional malloc/free regime.
Apparently what you are saying is that you would prefer to be at the mercy
of bugs in the runtime GC rather than bugs in your own code :-)

With regard to avoiding ML's, conservative garbage collection is NOT
guaranteed to be effective. Once there is one uncollected garbage block,
it can be the source of bogus roots to other uncollected garnage blocks,
and this process can recur without limit. Yes, it is unlikely to do so,
but if you want to guarantee absence from ML's, conservative GC is not
attractive. OGC on the other hand allows a relatively simple high level
analysis.

Re: Question about garbage collection

[Robert Dewar]

Bob Duff said

<<The literature on so-called conservative GC is full of tricks to make
the probability of false-rentention lower, such as black-listing.  But
it still makes me nervous.  On the other hand, octopus GC without
compaction (or manual memory management without compaction) can cause
trouble, too, unless you're dealing with fixed-size blocks.  There's no
silver bullet -- memory leaks are possible no matter what.
>>

I disagree, it is quite possible to put bounds on possible 
fragmentation effects ....