Garbage collection?

Garbage collection?

[titan.ksc.nasa.gov!mcroberts]

I've been looking at two different Ada textbooks which have
very different ideas about garbage collection.  The older
book says that a good Ada compiler should take care of it for
you and you should avoid unchecked_deallocation.  The newer
one says that you need to manage storage yourself using
unchecked_deallocation.  I'm curious as to the state of the
art in automated garbage collection.  I'm used to using 
Common Lisp on Symbolics or Unix platforms, and they use a
combination of temporal, incremental and full GCs.  I'm also
familiar with languages such as C++ where you have to manage
garbage collection yourself, but you can implement reference
counts and other sorts of schemes to simplify it.  Is this
something one needs to worry about when using solid production
quality Ada compilers, and is there any negative performance
impact if you don't clean up your own garbage.  In Lisp it is
usually better to let the system do it since it is highly
optimized and done mostly during page faults.

Re: Garbage collection?

[Rick Hudson]

>>>>> On 21 Apr 92 21:09:54 GMT, mcroberts@titan.ksc.nasa.gov said:

mcroberts> I've been looking at two different Ada textbooks which have
mcroberts> very different ideas about garbage collection.  The older
mcroberts> book says that a good Ada compiler should take care of it for
mcroberts> you and you should avoid unchecked_deallocation.  The newer
mcroberts> one says that you need to manage storage yourself using
mcroberts> unchecked_deallocation. I'm curious as to the state of the
mcroberts> art in automated garbage collection.  

The older book is correct. The language was designed to allow GC.
Unfortunately, the newer book reflects the (1992) reality of the situation.
Ada does have the advantage over C++ in that accurate (non-conservative)
collectors can be implemented for the language.  See our upcoming Sigplan
paper (referenced below) for a discussion of how to implement an accurate GC
for languages like Ada along with some of the costs.

@Unpublished{DMH91,
  author = 	 "Amer Diwan and J. Eliot B. Moss and Richard L. Hudson",
  title = 	 "Compiler Support for Garbage Collection in a Statically
  Typed Language",
  note = 	 "To appear in SIGPLAN PLDI",
  OPTcrossref =  "",
  OPTkey = 	 "",
  year = 	 1992,
  OPTmonth = 	 "",
  OPTannote = 	 ""
}
--

                Richard L. Hudson, Research Associate
                University Computing Services
                Lederle Graduate Research Center
                University of Massachusetts
                Amherst, MA  01003
                (413) 545-1220; Hudson@cs.umass.edu

Re: Garbage collection?

[Robert I. Eachus]

In article <1992Apr21.160955.2523@titan.ksc.nasa.gov> mcroberts@titan.ksc.nasa.
gov writes:

  > I'm curious as to the state of the art in automated garbage
  > collection.

   No Ada compiler I know of does complete garbage collection.  This
is not because it is too hard, but because the interaction of tasking
and garbage collection leads to unacceptable compromises.  Since in
good Ada compilers the only way to create garbage that needs
collection is with access types, the general wisdom in Ada currently
is that garbage collection is the resposibility of the application.
I'm not happy with that, but that is the way the culture has evolved.

   Is this something one needs to worry about when using solid
   production quality Ada compilers...

   Yes.

                                   ...and is there any negative
   performance impact if you don't clean up your own garbage.

   Very definitely.  An application which doesn't create much garbage
and doesn't need to run for long periods of time can ignore the
problem, but most real-time applications cannot.  Fortunately, the
type of garbage collection needed for most real-time applications is
easy to program in Ada.  However, the structures needed by many AI
applications are not easy to clean up after.  I've thought about
writing a more-or-less portable garbage collector which would only
need a few low-level routines rewritten to move it to a new
environment.  But it would be a lot of work, and the usual "solution"
to the problem in safety critical systems instead is to just forbid
access types.
--

					Robert I. Eachus

with STANDARD_DISCLAIMER;
use  STANDARD_DISCLAIMER;
function MESSAGE (TEXT: in CLEVER_IDEAS) return BETTER_IDEAS is...

Re: Garbage collection?

[dog.ee.lbl.gov!overload.lbl.gov!agate!spool.mu.edu!yale.edu!jvnc.net!darw]

>From article <1992Apr21.160955.2523@titan.ksc.nasa.gov>,
by mcroberts@titan.ksc.nasa.gov:
>                          I'm curious as to the state of the
> art in automated garbage collection.

Simula 67 (dating from roughly 1968 -- they were optimistic about their
release date) supported garbage collection in a language not radically
different from the Algol to Ada family.  That is, it was in the Algol 60
tradition, with strong typing, block structure, and records and pointers.
(All right, it was also object oriented, with classes and inheritance,
but that doesn't really make the problem any worse.)

I saw a benchmark result in the mid 1970's that showed that Simula 67 on
the IBM System 360 was faster than PL/I on the same machine, and that the
speed advantage was due, in part, to Simula's use of garbage collection.
It seems that Garbage collection allows programmers to ignore the problem
of keeping track of when to deallocate stuff, and this can save more CPU
cycles than are taken by the garbage collector.

Ada and Pascal can clearly be used with similar garbage collection
methodology.

The trouble is that garbage collection cannot yet be used in hard
real-time environments.  The algorithms available today are far better
than the simple mark-sweep algorithms of the 1960's, but even opportunistic
generational garbage collection doesn't guarantee a worst-case response
time per allocation, it only gives an excellent average and a minimum
number of annoying interruptions.

Since Ada is intended for embedded systems, and since many of these are
real-time systems, and since the designers of Ada wanted to maximize
portability of code, there are good reasons not to allow users to rely on
the availability of a garbage collector.  These reasons are not compelling,
however, and the designers of Ada knew it.

The formal definition of Ada allows implementors to provide a garbage
collector if they want to do so.  The problem is that few if any bother to
do it.  Early texts on Ada seem to have assumed that more implementations
would support garbage collection, but the marketplace today doesn't demand
it, so it's largely unavailable.  As a result, later texts include specific
coverage of unchecked deallocation because it is a practical necessity
under most implementations.
					Doug Jones
					jones@cs.uiowa.edu

Garbage Collection ???

[ldries46]

I am creating a program within GNAT Programming Studio in which I have to 
create A List of the model

edges  :  ptr_Node;
where ptr_Node is
.....
.....
next : ptr_edge;
end record;

This structure is called throughout my program extensively with no problems 
but within a declare begin ... end
part of the form

declare
   stold_Points : ptr_Node;
   old_Points : ptr_Node;
begin
     stold_Points := new Node;
      ...
      ...
end;

This program part is run within a while loop.

Now the following occurs:

I get a segmentation fault on line 196 within the program lines:

            edges := stedges;
            while edges /= NULL loop
                Edge_Force(edges);
line 196   edges := edges.next;
            end loop;
with the fault message:

Program received signal SIGSEGV, Segmentation fault.
0x0054694c in falling.falling_ball (file_name=..., version=...) at 
E:\ada\project\Cell_3D\Source Files\Falling.adb:196

At the point the program is stopped I get the following values printed

(gdb) print stedges
$9 = (access general.edge) 0x3e2dbf8

(gdb) print edges
$8 = (access general.edge) 0x0

The fault is the result of the last result that is clear edges = NULL when 
edges.next is called
but as the code of Edge_Force is

procedure Edge_Force(edge1 : ptr_Edge) is
   len : float;
begin
   len := Length(edge1.P1.pnt, edge1.P2.pnt) - edge1.l_init;
   if abs(len / edge1.l_init) < 0.00001 then
     len := 0.0;
   end if;
   edge1.force := edge1.k_s * len;
end Edge_Force;

I don't change the value of edges so as I read it edges could not be NULL at 
that point.

What also causes the changed value of edges within the loop. Can it be some 
garbage problem.
At the moment the fault occurs the outer loop has run for at least serveral 
hundred times

L. Dries

Re: Garbage Collection ???

[Dmitry A. Kazakov]

On Fri, 13 Apr 2012 14:14:43 +0200, ldries46 wrote:

> What also causes the changed value of edges within the loop. Can it be some 
> garbage problem.

(Fortunately, Ada does not have mandated GC). Most likely you have a
dangling pointer somewhere.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Garbage Collection ???

[ldries46]

I have been trying to find the place where a faulty pointer could have been 
introduced and I come to the conclusion that the return of a procedure in 
the place.
I did position some variables (edge_debug1 till edge_debug4) to be filled 
with the value of the original pointer at various places in and around the 
procedure Edge_Force and printed them after the breakpoint.
The code there is now:

while edges /= NULL loop
   edge_debug3 := edges;
   Edge_Force(edges);
   edge_debug4 := edges;
   edges := edges.next;
end loop;

where Edge_Force code is:

procedure Edge_Force(edge1 : ptr_Edge) is
   len : float;
begin
   edge_debug1 := edge1;
   len := Length(edge1.P1.pnt, edge1.P2.pnt) - edge1.l_init;
   if abs(len / edge1.l_init) < 0.00001 then
     len := 0.0;
   end if;
   edge1.force := edge1.k_s * len;
   edge_debug2 := edge1;
end Edge_Force;

(gdb) print stedges
$43 = (access general.edge) 0x3e0d568

(gdb) print edges
$45 = (access general.edge) 0x0

(gdb) print edge_debug3
$48 = (access general.edge) 0x3db8200

(gdb) print edge_debug1
$51 = (access general.edge) 0x3db8200

(gdb) print edge_debug2
$53 = (access general.edge) 0x3db8200

(gdb) print edge_debug4
$55 = (access general.edge) 0x0
It can be seen that only the end of the procedure Edge_Force is between the 
creation of edge_debug2 and edge_debug4
The reason that I originally thought about Garbage collection is that I 
imagined that perhaps use of too much memory could be the reason.

Regards,
L. Dries

"Dmitry A. Kazakov"  schreef in bericht 
news:5o86o2smbjpz.17l849bmku28v$.dlg@40tude.net...

On Fri, 13 Apr 2012 14:14:43 +0200, ldries46 wrote:

> What also causes the changed value of edges within the loop. Can it be 
> some
> garbage problem.

(Fortunately, Ada does not have mandated GC). Most likely you have a
dangling pointer somewhere.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de 

Re: Garbage Collection ???

[Dmitry A. Kazakov]

On Fri, 13 Apr 2012 21:27:23 +0200, ldries46 wrote:

> I have been trying to find the place where a faulty pointer could have been 
> introduced and I come to the conclusion that the return of a procedure in 
> the place.

Note that pointers are most likely passed by value. This means that the way
you are debugging it does not make much sense. Furthermore, dangling
pointers usually manifest themselves after corrupting the program state
beyond any recognition. Thus the observed effect is a consequence of a bug
many source lines and executed instructions away.

You may try to use the GNAT Debug Pool to locate the problem:

http://gcc.gnu.org/onlinedocs/gnat_ugn_unw/The-GNAT-Debug-Pool-Facility.html

Or you may trace all allocations, deallocations, dereferences of the
pointer type. Put the trace into a DB or Excel, sort it by the address key
in order to determine the first place where some pointer gets dangled.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Garbage Collection ???

[Brian Drummond]

On Fri, 13 Apr 2012 21:27:23 +0200, ldries46 wrote:

> I have been trying to find the place where a faulty pointer could have
> been introduced and I come to the conclusion that the return of a
> procedure in the place.
> I did position some variables (edge_debug1 till edge_debug4) to be
> filled with the value of the original pointer at various places 

I would declare these variables as not null access whatever, to get an 
exception on assignment to them, rather than waiting until the error 
manifests as a segv. (Do you have a lot of checks turned off, so that it 
doesn't raise Storage_Error)?

- Brian

Re: Garbage Collection ???

[ldries46]

I do have all errors turned on.
As I am using linked lists the most easy way to check for the last item is 
to check on NULL in the next part.
It should while debugging also generate an error if I have made an error.

At this moment I found a typing error in some other part of the program 
which is used in a Task using OpenGL.
It seems that that was the error.

"Brian Drummond"  schreef in bericht news:jmaai4$aga$1@dont-email.me...

On Fri, 13 Apr 2012 21:27:23 +0200, ldries46 wrote:

> I have been trying to find the place where a faulty pointer could have
> been introduced and I come to the conclusion that the return of a
> procedure in the place.
> I did position some variables (edge_debug1 till edge_debug4) to be
> filled with the value of the original pointer at various places

I would declare these variables as not null access whatever, to get an
exception on assignment to them, rather than waiting until the error
manifests as a segv. (Do you have a lot of checks turned off, so that it
doesn't raise Storage_Error)?

- Brian 

Re: Garbage Collection ???

[Robert A Duff]

"ldries46" <bertus.dries@planet.nl> writes:

> I would declare these variables as not null access whatever, ...

In Ada 2012, you can say:

    type T_Ptr_Opt is access all T;
    subtype T_Ptr is T_Ptr_Opt with
        Dynamic_Predicate => T_Ptr /= null;

Or in GNAT, "Predicate =>" instead of "Dynamic_Predicate =>".

- Bob

Re: Garbage Collection ???

[Julian Leyh]

Am Samstag, 14. April 2012 20:21:17 UTC+2 schrieb Robert A Duff:
> In Ada 2012, you can say:
> 
>     type T_Ptr_Opt is access all T;
>     subtype T_Ptr is T_Ptr_Opt with
>         Dynamic_Predicate => T_Ptr /= null;

In Ada 2005, you can already say:

    type T_Ptr_Opt is access all T;
    subtype T_Ptr is not null T_Ptr_Opt;

Re: Garbage Collection ???

[Robert A Duff]

Julian Leyh <julian@vgai.de> writes:

> Am Samstag, 14. April 2012 20:21:17 UTC+2 schrieb Robert A Duff:
>> In Ada 2012, you can say:
>> 
>>     type T_Ptr_Opt is access all T;
>>     subtype T_Ptr is T_Ptr_Opt with
>>         Dynamic_Predicate => T_Ptr /= null;
>
> In Ada 2005, you can already say:
>
>     type T_Ptr_Opt is access all T;
>     subtype T_Ptr is not null T_Ptr_Opt;

Right, but that's less useful, because it forces you
to initialize your variables (e.g. record components)
before you're ready to.

- Bob

Re: Garbage Collection ???

[Randy Brukardt]

"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message 
news:wcc4nsf4wm4.fsf@shell01.TheWorld.com...
> Julian Leyh <julian@vgai.de> writes:
>
>> Am Samstag, 14. April 2012 20:21:17 UTC+2 schrieb Robert A Duff:
>>> In Ada 2012, you can say:
>>>
>>>     type T_Ptr_Opt is access all T;
>>>     subtype T_Ptr is T_Ptr_Opt with
>>>         Dynamic_Predicate => T_Ptr /= null;
>>
>> In Ada 2005, you can already say:
>>
>>     type T_Ptr_Opt is access all T;
>>     subtype T_Ptr is not null T_Ptr_Opt;
>
> Right, but that's less useful, because it forces you
> to initialize your variables (e.g. record components)
> before you're ready to.

I don't think that's really true, since the rule that you're referring to 
applies if *any* components are initialized. So while it is true (but a bad 
idea for access types, IMHO) for stand-alone objects, depending on it is 
iffy at best in records.

In all honesty, I think the rule that makes these work different is just a 
bug in Ada 2012. The rule *I* was thinking about only applied to things that 
aren't initialized at all (i.e. scalars), not to things that are initialized 
automatically (access types and Default_Value aspects). In the latter case, 
you can use the object immediately and *never* initialize it -- having the 
predicate not enforced means that it cannot ever be trusted on such objects. 
That seems like a bad way to go (and different from constraints).

Thus, I think the current rule (3.2.4(31/3)) is OK for composite types, but 
it is wrong for elementary types when those are automatically initialized.

(And a null-excluding component - by any means - is almost never a good 
idea. You always need a "nothing/unknown" indicator. Null-exclusions are 
almost exclusively useful for parameters, where you don't need "nothing" 
simply because you don't make the call in that case.)

                                Randy.

Re: Garbage Collection ???

[Dmitry A. Kazakov]

On Thu, 19 Apr 2012 15:26:03 -0500, Randy Brukardt wrote:

> (And a null-excluding component - by any means - is almost never a good 
> idea.

The idea is good, bad is lthe ack of means to initialize such components
properly. You know what I mean. (:-))

> You always need a "nothing/unknown" indicator.

I am using a scheme when non-null pointer components are initialized to a
stock object. It works, but becomes very uncomfortable when the record
itself is in a generic and the target type is tagged. I need to derive not
only the type itself, but also the stock object type, override its
operations to null/alarm, create the stock singleton etc.

> Null-exclusions are 
> almost exclusively useful for parameters, where you don't need "nothing" 
> simply because you don't make the call in that case.)

and access discriminants, certainly.

However both cases do not feel good. I mean why there should be a pointer?
Is it always a reference semantics? Frequently it is not. But even if the
semantics is indeed referential, why explicit pointer?

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Garbage Collection ???

[Randy Brukardt]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message 
news:itjg3eh0o4s8.rm273bcoi1tb$.dlg@40tude.net...
> On Thu, 19 Apr 2012 15:26:03 -0500, Randy Brukardt wrote:
...
>> Null-exclusions are
>> almost exclusively useful for parameters, where you don't need "nothing"
>> simply because you don't make the call in that case.)
>
> and access discriminants, certainly.
>
> However both cases do not feel good. I mean why there should be a pointer?
> Is it always a reference semantics? Frequently it is not. But even if the
> semantics is indeed referential, why explicit pointer?

I agree in general. Especially for Ada 2012, where you can used "aliased" to 
make any parameter of any type pass-by-reference.

The usual reason to pass a pointer is that you already have one for some 
other reason. That's typical in data structures, for instance (remember that 
Ada.Containers has Cursor, which is just like an access type except isn't 
one explicitly).

                                     Randy.