Garbage collection (was a spinoff of a spinoff of a GA diatribe)

Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[W. Wesley Groleau (Wes)]

It seems to me that auto-GC is no longer worth arguing about
with regard to Ada.

Stack objects are collected as a side effect of the call stack mechanism.

Implementations that transparently put "stack" variables on the heap
usually automatically deallocate at end of scope.

Explicit use of the heap for non-composite objects is not often done--why
would you?

And with composites, the provider of the data type has the complete freedom
of choice to extend a controlled type with GC, extend a controlled type
without GC, or not use a controlled type.

So, compared to the above, how big is the payoff of having GC imposed on
you by the implementation?

---------------------------------------------------------------------------
W. Wesley Groleau (Wes)                                Office: 219-429-4923
Hughes Defense Communications (MS 10-40)                 Home: 219-471-7206
Fort Wayne,  IN   46808                  (Unix): wwgrol@pseserv3.fw.hac.com
---------------------------------------------------------------------------

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Jon S Anthony]

In article <9610152135.AA13753@most> "W. Wesley Groleau (Wes)" <wwgrol@PSESERV3.FW.HAC.COM> writes:

> And with composites, the provider of the data type has the complete freedom
> of choice to extend a controlled type with GC, extend a controlled type
> without GC, or not use a controlled type.

This just isn't accurate.  Sure, you can go a reasonable way with
this.  But finalization stuff just doesn't catch many typical cases
and it is _way_ expensive.  Also, you have to put in all the effort
for something which would be directly useable.

Actually, I've found that user defined storage pools are much more
important in this context.


> So, compared to the above, how big is the payoff of having GC imposed on
> you by the implementation?

Big.


/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Robert Dewar]

Wes says

"And with composites, the provider of the data type has the complete freedom
of choice to extend a controlled type with GC, extend a controlled type
without GC, or not use a controlled type.

So, compared to the above, how big is the payoff of having GC imposed on
you by the implementation?"


I don't think it is quite that simple. There is nothing to prevent a
compiler having a temporary copy of a pointer to some controlled object
in a register if this would not normally be detectable by as-if semantics.
Perhaps one can do a simple collector, but certainly a compacting collector
raises question marks.

Even the simple collector is not so simple as far as we can tell. If someone
thinks it is trivial, and would like to contribute a garbage collected pool
that really works to the Ada community, that would be very welcome!

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Robert Dewar]

Jon says

"This just isn't accurate.  Sure, you can go a reasonable way with
this.  But finalization stuff just doesn't catch many typical cases
and it is _way_ expensive.  Also, you have to put in all the effort
for something which would be directly useable.
"

First, it is not finalization but adjust that is the critical function.
But in any case the above claim is technically incomprehensible, please
elucidate.

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Jon S Anthony]

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

> Jon says
> 
> "This just isn't accurate.  Sure, you can go a reasonable way with
> this.  But finalization stuff just doesn't catch many typical cases
> and it is _way_ expensive.  Also, you have to put in all the effort
> for something which would be directly useable.
> "
> 
> First, it is not finalization but adjust that is the critical function.
> But in any case the above claim is technically incomprehensible, please
> elucidate.

I meant "finalization stuff" as in Ada.Finalization stuff.  But
actually, finalization in many cases is much more critical (especially
when you are using limited types where there isn't any adjust
anyway!!!)  So, I guess I would disagree with you anyway.

Second, none of this stuff covers all the cases.  It just plain
doesn't.  And, even if it were to work for the particulars of a
specific application, you still have to go and roll your own stuff and
make sure it is all correct and whatnot.  None of this is particularly
incomprehensible.

/Jon



-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Robert Dewar]

Michael thinks that performance rquirements should be on the same
level as semantic requirements. This is not an unusual viewpoint,
but I think no one has the foggiest idea how to actually proceed
to do something useful along these lines. Michael, can you point
to an example of what you mean, or is this entirely fantasy at
this stage?

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Richard A. O'Keefe]

"W. Wesley Groleau (Wes)" <wwgrol@PSESERV3.FW.HAC.COM> writes:
>Stack objects are collected as a side effect of the call stack mechanism.

Ok.

>Implementations that transparently put "stack" variables on the heap
>usually automatically deallocate at end of scope.

Ok.

>Explicit use of the heap for non-composite objects is not often done--why
>would you?

Because you don't *know* it's non-composite.
Ada supports information hiding, remember?

>And with composites, the provider of the data type has the complete freedom
>of choice to extend a controlled type with GC, extend a controlled type
>without GC, or not use a controlled type.

Once again, the problem is information hiding, only this time it goes
the other way.  Now the problem is that the provider of the data type
has no idea what the client will want to do with it.  You cannot, for
example, decide to "not use a controlled type" without thereby demanding
that the client accept responsibility for manual mangement.  And if the
client is a generic package receiving this type as a parameter, the
client doesn't *know* whether it is required to do manual management
(last choice) or forbidden to (first choice).

>So, compared to the above, how big is the payoff of having GC imposed on
>you by the implementation?

Fighting words.  Nobody in this thread has been arguing that Ada ought
to *impose* GC on anyone, only that it would be better if it were not
the case in practice that native-code Ada compilers *deny* it to
everyone.

As far as I am concerned, better support for information hiding is not
the least of the benefits of automatic storage management.

-- 
Mixed Member Proportional---a *great* way to vote!
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Mark A Biggar]

In article <54kk6g$is6$1@goanna.cs.rmit.EDU.AU> ok@goanna.cs.rmit.EDU.AU (Richard A. O'Keefe) writes:
>"W. Wesley Groleau (Wes)" <wwgrol@PSESERV3.FW.HAC.COM> writes:
>>Explicit use of the heap for non-composite objects is not often done--why
>>would you?
>
>Because you don't *know* it's non-composite.
>Ada supports information hiding, remember?

Would not a simple hueristic like "if its 'SIZE < 64 put it on the stack,
otherwise the heap" handle this problem reasonably well?

--
Mark Biggar
mab@wdl.lmco.com

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Larry Kilgallen]

In article <54lg65$5lc@wdl1.wdl.lmco.com>, mab@dst17.wdl.loral.com (Mark A Biggar) writes:
> In article <54kk6g$is6$1@goanna.cs.rmit.EDU.AU> ok@goanna.cs.rmit.EDU.AU (Richard A. O'Keefe) writes:
>>"W. Wesley Groleau (Wes)" <wwgrol@PSESERV3.FW.HAC.COM> writes:
>>>Explicit use of the heap for non-composite objects is not often done--why
>>>would you?
>>
>>Because you don't *know* it's non-composite.
>>Ada supports information hiding, remember?
> 
> Would not a simple hueristic like "if its 'SIZE < 64 put it on the stack,
> otherwise the heap" handle this problem reasonably well?

Perhaps I have lost context, but preventing objects whose size is known
at subprogram invocation time from being on the stack just because
their size is greater than 64 bits seems like a great way to waste
both CPU cycles and locality of reference for memory.  It may not
matter in the embedded business, but some of us use virtual memory.
Stack storage is our friend, performance-wise, and cache seems a wash
between stack and heap.

Larry Kilgallen

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Hans-Juergen Boehm]

Robert I. Eachus wrote:
> 
> In article <JSA.96Oct22152111@alexandria> jsa@alexandria (Jon S Anthony) writes:
> 
>    > Pro: ...
>    >    Faster - allocations can be _much_ faster and collections can be
>    >    much more efficient than good ol' "free".
> 
>    >    Works across the board (no need for special casing various situations)
> 
>    You must have been smoking some good stuff.  Precise collectors can
> do the later, but never the former. Think for a second, any reclamation
> the garbage collector can do, the free routine can do as well, without
> the memory scan for live references.
> 
This is wrong for many reasons:

1. Deallocating many objects at once is much faster than deallocating
them one at a time in sequence.  Free list headers are already in
registers, etc.

2. In a multithreaded environment with a single heap, the collector has
to perform one lack acquisition/release per roundtrip.  Explicit
deallocation needs 2.

3. "Precise" collectors can arrange to allocate from contiguous memory
which may be much cheaper.

4. It ignores all bookkeeping costs (e.g. reference counts) required for
manual deallocation.  These can easily dominate.

5. Certain algorithms require SUBSTANTIALLY more locking without GC.

In fact even our conservative collector often beats C malloc/free for
very small objects.  Please feel free to try the experiment, especially
before posting remarks like the above.

May I also suggest a scan of the recent literature?  If you're
interested in conservative collection, you might start with

http://reality.sgi.com/employees/boehm_mti/gc.html

It discusses some of these issues and points to some more general
standard references.


-- 
Standard disclaimer ...
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Brian R. Hanson]

Robert I. Eachus wrote:

>    The finalization routine took five lines, and neat trick was in the
> Adjust routine.  On assignment, a node (and all the nodes reached from
> it) was given a new generation number (always incremented), positive
> for the node assigned, and negated for all nodes reachable from it.
> From a garbage collection point of view it was "extra overhead" but it
> allowed me to do other operations such as reachability more
> efficiently.  (You can't reach a node with a lower absolute generation
> number.  The biggest win is that you only have to check against nodes
> you have visited before with the current generation number.  Beats
> marking and unmarking and allows more than one such operation to be
> conducted simultaneously.)

Have you read the paper on "The GNAT Implementation of controlled
types"?  After looking at this one could argue that GC could easily 
more efficient if you could avoid using controlled types.

-- Brian Hanson
-- brh@cray.com

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Robert A Duff]

In article <32704FD9.41C6@mti.sgi.com>,
Hans-Juergen Boehm  <boehm@mti.sgi.com> wrote:
>5. Certain algorithms require SUBSTANTIALLY more locking without GC.

Could you please give an example of that?

- Bob

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Hans-Juergen Boehm]

Robert A Duff wrote:
> 
> In article <32704FD9.41C6@mti.sgi.com>,
> Hans-Juergen Boehm  <boehm@mti.sgi.com> wrote:
> >5. Certain algorithms require SUBSTANTIALLY more locking without GC.
> 
> Could you please give an example of that?
> 
> - Bob

Sure.  Look at 

http://reality.sgi.com/employees/boehm_mti/example.html

The basic problem is that (frequent)read operations from a (software)
cache may need to acquire a lock in order to guard against (infrequent)
deallocation by a concurrent cache update.  In the GC case the update
can atomically replace a pointer and drop the old entry.  Reads from the
old entry will continue to succeed.

-- 
Hans-Juergen Boehm
boehm@mti.sgi.com

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Robert Dewar]

Someone (I lost track) gave as an advantage of garbage collection:

>    > Pro: ...
>    >  Faster - allocations can be _much_ faster and collections can be
>    >  much more efficient than good ol' "free".


I agree on the allocation, but the free claim is dubious, it depends on
a lot of factors. A true GC, as opposed to a conservative GC, can be
made to run in time proportional to the amount of non-garbage (see for
example the description of the SPITBOL collector in SP&E 1977 article
by Dewar and McCann), so if you have a LOT of garbage this can be true.

But if you are doing lots of GC's then you can end up spending a lot of
time freeing a little stuff (ttrue of conservative GC as well of course).

On the other hand, it is quite possible to make free quite efficient.
I wrote the collector for the x86 Alsys compiler (I don't know if the
TSP ObjectAda still uses it or not), and it had the property that
free was a single instruction that was generated in line.

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Robert Dewar]

iJon said

"Well, 1) I used "can" specifically because I didn't want to assert
"are".  2) If you never need to collect, you will not even execute 1
instruction the entire run (let alone 1 for each free).  3) You can
write such very efficient "free"s even within the language - just roll
your own allocator (which is what I believe happens in real-time
contexts actually requiring "heap" style allocation).  4) we were not
talking about these sort of special "free"s..."

What do you mean "special frees", I was talking about the absolutely
standard free routine, accessed by the built-in routine unchecked_deallocation
in the Alsys compiler, not something I added on (Jon, perhaps you don't
know, but I worked for years for Alsys, and quite a bit of the x86 (x = 2 and
3) runtime work was my code, including the allocator!)

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Jon S Anthony]

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

> Someone (I lost track) gave as an advantage of garbage collection:
> 
> >    > Pro: ...
> >    >  Faster - allocations can be _much_ faster and collections can be
> >    >  much more efficient than good ol' "free".

That would be me...


> I agree on the allocation, but the free claim is dubious, it depends on
> a lot of factors. A true GC, as opposed to a conservative GC, can be
> made to run in time proportional to the amount of non-garbage (see for
> example the description of the SPITBOL collector in SP&E 1977 article
> by Dewar and McCann), so if you have a LOT of garbage this can be true.

Actually, you can do much better in practice if you use a generational
scheme (where you don't waste time on stuff that will typically not
become garbage).  So, even if you don't have a lot of garbage, and
have a lot of non-garbage, this can be true (it really depends more on
how much "quickly [but not instantly] dying" things you generate - not
the total amount of non-dying things...)


> But if you are doing lots of GC's then you can end up spending a lot of
> time freeing a little stuff (ttrue of conservative GC as well of course).

This is not particularly accurate in the context of generational
schemes.


> On the other hand, it is quite possible to make free quite efficient.
> I wrote the collector for the x86 Alsys compiler (I don't know if the
> TSP ObjectAda still uses it or not), and it had the property that
> free was a single instruction that was generated in line.

Well, 1) I used "can" specifically because I didn't want to assert
"are".  2) If you never need to collect, you will not even execute 1
instruction the entire run (let alone 1 for each free).  3) You can
write such very efficient "free"s even within the language - just roll
your own allocator (which is what I believe happens in real-time
contexts actually requiring "heap" style allocation).  4) we were not
talking about these sort of special "free"s...

/Jon

-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com

Re: Garbage collection (was a spinoff of a spinoff of a GA diatribe)

[Jon S Anthony]

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

> iJon said
>...
> contexts actually requiring "heap" style allocation).  4) we were not
> talking about these sort of special "free"s..."
>
> What do you mean "special frees", I was talking about the absolutely
> standard free routine, accessed by the built-in routine
> unchecked_deallocation in the Alsys compiler, not something I added

My mistake.  I erroneously was in the context of an implementation
just utilizing off the shelf RTL stuff from the typical OS (UNI*,
Windoze, etc.)  You are of course correct that there would be nothing
"special" here if it was just out of the box with the implementation.
Sorry.


> on (Jon, perhaps you don't know, but I worked for years for Alsys,
> and quite a bit of the x86 (x = 2 and 3) runtime work was my code,
> including the allocator!)

And given your other work (that I do know something of), I am sure it
was exceptionally good stuff!  Actually, I had heard something about
your work there somewhere, but I can't recall when, where, the
context, etc...  I guess I'm getting old... :-|

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
jsa@organon.com