Boehm-Demers-Weiser conservative garbage collector and GNAT

Boehm-Demers-Weiser conservative garbage collector and GNAT

[Martin Krischik]

Hello,

I am wondering if it is possible to implement a storage pool using  the
Boehm-Demers-Weiser conservative garbage collector in GNAT.

But before I waste to much time I would like to know if anybody ever tried
that before?

Or does anybody know any reasons why this might be doomed?

With Regards

Martin

For details on Boehm-Demers-Weiser conservative garbage collector see:

http://www.hpl.hp.com/personal/Hans_Boehm/gc/index.html

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Ludovic Brenta]

Martin Krischik <krischik@users.sourceforge.net> writes:

> Hello,
> 
> I am wondering if it is possible to implement a storage pool using  the
> Boehm-Demers-Weiser conservative garbage collector in GNAT.
> 
> But before I waste to much time I would like to know if anybody ever tried
> that before?
> 
> Or does anybody know any reasons why this might be doomed?
> 
> With Regards
> 
> Martin
> 
> For details on Boehm-Demers-Weiser conservative garbage collector see:
> 
> http://www.hpl.hp.com/personal/Hans_Boehm/gc/index.html

The web page you mention says that GCC contains a version of this
garbage collector.  I understand this has been introduced in GCC 3.0.
So, to me, there appears to be three approaches to "implement a
storage pool using the Boehm-Demers-Weiser conservative garbage
collector in GNAT":

- Re-implement the GC in Ada, as an external library, so that all Ada
  programs can use it (even non-GNAT ones if the code is portable).

- Write a thick Ada binding to the C garbage collector, with the same
  end result as above, but requiring an additional library at link
  time.

- Modify libgnat and libgnarl in GCC 3.3 with a new storage pool that
  uses the copy of the GC that is in GCC 3.3; this would make the GC
  available only to GCC 3.3 applications.

Which were you thinking about?

-- 
Ludovic Brenta.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Preben Randhol]

Ludovic Brenta wrote:
> - Write a thick Ada binding to the C garbage collector, with the same
>   end result as above, but requiring an additional library at link
>   time.

Does this make sense? To rely on C to do the garbage collection of Ada ?

Preben
-- 
This is Ada95 land. On quiet nights you can hear C programmers debug.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Ludovic Brenta]

Preben Randhol <randhol+abuse@pvv.org> writes:

> Ludovic Brenta wrote:
> > - Write a thick Ada binding to the C garbage collector, with the same
> >   end result as above, but requiring an additional library at link
> >   time.
> 
> Does this make sense? To rely on C to do the garbage collection of Ada ?

Well, the garbage collector itself is language-independent, so it
would work even on Ada objects.  Indeed, it is already being used for
the Java and Objective C runtimes of GCC.  It supports finalisation of
objects at collection time, so it could even work for Ada's controlled
types.

There would be benefits to this approach: less work (no
reimplementation); and benefit from future updates to the GC.  The
downside, of course, is the increased complexity of the build
configuration for client programs, and the necessity to keep the thick
binding in sync with the GC library.  The latter depends on how stable
the public interface to the library is.

Note that the third approach I mentioned (use the GC that is in GCC
from within libgnat and libgnarl) differs only slightly, and has other
benefits and drawbacks.  For example:

+ the Ada runtime could also use the GC for itself, in addition to
  providing it to clients.

+ Keeping the GC and the Ada runtime in sync would be facilitated by
  the fact that both are in the GCC source tree; besides, the Boehm GC
  in GCC probably changes slowly since so much code already depends on
  it.

+ configuration management simplified to the extreme: to clients, the
  GC would just be part of the runtime provided by the compiler.

- Only available to people using GCC 3.3 as their compiler, as opposed
  to GNAT 3.15p.

I'm still curious to know what Martin's preferred approach is.

-- 
Ludovic Brenta.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Preben Randhol]

Ludovic Brenta wrote:
> - Only available to people using GCC 3.3 as their compiler, as opposed
>   to GNAT 3.15p.

Which would mean that code written with a GC present won't work well
compiled with other compilers? I mean if you never use Free yourself.

Preben
-- 
Ada95 is good for you.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Ludovic Brenta]

Preben Randhol <randhol+abuse@pvv.org> writes:

> Ludovic Brenta wrote:
> > - Only available to people using GCC 3.3 as their compiler, as opposed
> >   to GNAT 3.15p.
> 
> Which would mean that code written with a GC present won't work well
> compiled with other compilers? I mean if you never use Free yourself.

Correct, but this IMHO would the programmer's fault, not GCC's.  The
ARM (13.11.1) says that implementations may provide GC at their
option; I suppose that portable programs must be aware of this and
always use Free, no matter what, in order to work on all
implementations.  It is trivial for a GC-enabled implementation to
provide a no-op version of Free.  Also, appropriate use of pragma
Controlled could be required.

-- 
Ludovic Brenta.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Larry Kilgallen]

In article <slrnbeu1ht.big.randhol+abuse@kiuk0152.chembio.ntnu.no>, Preben Randhol <randhol+abuse@pvv.org> writes:
> Ludovic Brenta wrote:
>> Correct, but this IMHO would the programmer's fault, not GCC's.  The
>> ARM (13.11.1) says that implementations may provide GC at their
>> option; I suppose that portable programs must be aware of this and
>> always use Free, no matter what, in order to work on all
>> implementations.  It is trivial for a GC-enabled implementation to
>> provide a no-op version of Free.  Also, appropriate use of pragma
>> Controlled could be required.
> 
> So in effect the GC would only be a bonus to prevent memory leaks due to
> errors in the program?

It would be a way to spend overhead to make up for a lack of cleanup
in the programming.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Preben Randhol]

Larry Kilgallen wrote:
> It would be a way to spend overhead to make up for a lack of cleanup
> in the programming.

Exactly. So one would need to have GC in all implementations in order to
have any real use for it IMHO. As one then can start with more sloppy
coding [*].

[*] In the sense that you don't worry abut what happens to your
allocations.
-- 
Preben Randhol ---------------- http://www.pvv.org/~randhol/ --
"Violence is the last refuge of the incompetent", Isaac Asimov

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Ludovic Brenta]

Preben Randhol <randhol+abuse@pvv.org> writes:

> Larry Kilgallen wrote:
> > It would be a way to spend overhead to make up for a lack of cleanup
> > in the programming.
> 
> Exactly. So one would need to have GC in all implementations in order to
> have any real use for it IMHO. As one then can start with more sloppy
> coding [*].
> 
> [*] In the sense that you don't worry abut what happens to your
> allocations.

Yes.  I've never really liked GC myself, but the paper that Martin
mentions says that programmers spend up to 30% of their time doing
(and debugging) memory management, and that perhaps this 30% could be
better spent elsewhere.

This at the expense of some performance [1] and portability.  It's a
trade-off that many people may find appealing, so, I can see a point
of providing it for those who want it.  Of course, I suppose using the
GC would be optional, even if GCC or GNAT did provide it.  I tend to
think that choice is almost always a good thing.

[1] According to the paper, Boehm's GC has pretty good performance,
but GCC's compilation speed has suffered from its introduction.  Also,
in most Java virtual machines, the GC is a well-known source of
unpredictability in the performance of applications.

(the original paper also says the GC is a good debugging tool that
aids in finding memory leaks; but, of course, GNAT already has a debug
storage pool, so I don't think this is the reason Martin wants to
provide GC).

-- 
Ludovic Brenta.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Preben Randhol]

Ludovic Brenta wrote:
> 
> Yes.  I've never really liked GC myself, but the paper that Martin
> mentions says that programmers spend up to 30% of their time doing
> (and debugging) memory management, and that perhaps this 30% could be
> better spent elsewhere.

Yes this is true, but ... (se below)

> This at the expense of some performance [1] and portability.  It's a

the problem is that one would probably spend >> 30% trying to port
the code to a non GC environment if one only have it for some compilers.

-- 
�It's probably worth pointing out that  C's pointer arithmetic  is not
 only dangerous, and a significant source of errors, but it also makes
 programs run slower.�
               - James Kanze on comp.lang.ada,comp.lang.c++.moderated

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Larry Kilgallen]

In article <rw27k7k7rgo.fsf@lbrenta.corp.emc.com>, Ludovic Brenta <ludovic.brenta@insalien.org> writes:

> Yes.  I've never really liked GC myself, but the paper that Martin
> mentions says that programmers spend up to 30% of their time doing
> (and debugging) memory management, and that perhaps this 30% could be
> better spent elsewhere.

Does that paper say _Ada_ programmers spend that much time ?

If so, then programmers for some other languages must spend 110% of their
time debugging memory managment issues.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Ludovic Brenta]

Kilgallen@SpamCop.net (Larry Kilgallen) writes:

> Ludovic Brenta <ludovic.brenta@insalien.org> writes:
> 
> > Yes.  I've never really liked GC myself, but the paper that Martin
> > mentions says that programmers spend up to 30% of their time doing
> > (and debugging) memory management, and that perhaps this 30% could be
> > better spent elsewhere.
> 
> Does that paper say _Ada_ programmers spend that much time ?
> 
> If so, then programmers for some other languages must spend 110% of their
> time debugging memory managment issues.

The paper concentrates on C and C++.  While I agree that Ada
programmers tend to do less dynamic memory allocation than C/C++
people, large programs will usually have to do some.  Think about
containers.  I'd be interested to know what your personal experience
is.  I'd expect you spend less than 30% of your time but more than 0%
doing memory management.  Of course, if you only ever allocate on the
stack and never on the heap (explicitly, that is), then you have no
need for a garbage collector since you don't create any garbage :)

Other opinions? Stories of shared memory, reference counters,
automatic pointers? I'm curious.

-- 
Ludovic Brenta.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Stephen Leake]

Ludovic Brenta <ludovic.brenta@insalien.org> writes:

> The paper concentrates on C and C++.  While I agree that Ada
> programmers tend to do less dynamic memory allocation than C/C++
> people, large programs will usually have to do some.  Think about
> containers.  I'd be interested to know what your personal experience
> is.  I'd expect you spend less than 30% of your time but more than 0%
> doing memory management.  Of course, if you only ever allocate on the
> stack and never on the heap (explicitly, that is), then you have no
> need for a garbage collector since you don't create any garbage :)

I wrote a container library that does all the memory management I
need. I tested it thoroughly, and now I use it. So I had some initial
investment, but now I spend 0% of my time "doing memory management". 

I believe that is the "Ada way".

Hmm. Except when I'm forced to use someone else's code, that doesn't
use my (or any) container library. Then I have to fix it.

-- 
-- Stephe

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Marin David Condic]

So we need a standard container library, right? ;-)

MDC

Stephen Leake wrote:
> 
> Hmm. Except when I'm forced to use someone else's code, that doesn't
> use my (or any) container library. Then I have to fix it.
> 


-- 
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jast.mil/

Send Replies To: m c o n d i c @ a c m . o r g

     "In general the art of government consists in taking as
     much money as possible from one class of citizens to give
     to the other."

         --  Voltaire
======================================================================

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Stephen Leake]

Marin David Condic <nobody@noplace.com> writes:

> So we need a standard container library, right? ;-)

Yes. But I already have one :)

-- 
-- Stephe

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Marin David Condic]

Standards are such a wonderful thing that everyone should have one of 
their very own! :-)

I have my own library of containers, utilities, math functions, TCP/IP 
communications, etc. It creates a lot of leverage for development and, 
because it gets used a lot, it is pretty darned reliable. Most 
programmers have such a bag of tricks. I'd like to see Ada collect up 
most of those tricks into one place and share the leverage with everyone.

MDC

Stephen Leake wrote:
> Marin David Condic <nobody@noplace.com> writes:
> 
> 
>>So we need a standard container library, right? ;-)
> 
> 
> Yes. But I already have one :)
> 


-- 
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jast.mil/

Send Replies To: m c o n d i c @ a c m . o r g

     "In general the art of government consists in taking as
     much money as possible from one class of citizens to give
     to the other."

         --  Voltaire
======================================================================

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Preben Randhol]

Marin David Condic wrote:
> Standards are such a wonderful thing that everyone should have one of 
> their very own! :-)
> 
> I have my own library of containers, utilities, math functions, TCP/IP 
> communications, etc. It creates a lot of leverage for development and, 
> because it gets used a lot, it is pretty darned reliable. Most 
> programmers have such a bag of tricks. I'd like to see Ada collect up 
> most of those tricks into one place and share the leverage with everyone.

Something like the vim repository perhaps? => http://vim.sf.net/

-- 
�It's probably worth pointing out that  C's pointer arithmetic  is not
 only dangerous, and a significant source of errors, but it also makes
 programs run slower.�
               - James Kanze on comp.lang.ada,comp.lang.c++.moderated

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Marin David Condic]

I looked at the website briefly and am not sure what you mean in this 
context. This appears to be a text editor similar to VI. Are you 
suggesting the project as a model of how to collectively develop an Ada 
library or does it have some collection of useful software tools?

My thinking is that Ada could benefit from having a library similar to 
Java or the MFC - only perhaps bigger and better. (Much of the MFC, for 
example, is dedicated to filling in weaknesses within C++ that Ada 
doesn't share, so Ada could spend more time on other matters.) We've 
talked container libraries here before and that may make it into the 
standard - but I've expressed my doubts as to the wisdom of expecting 
the standard to react to every need. I'd like to see a "standard" 
library that went well beyond just containers. But it takes some 
willingness on the part of the whole community to buy into one 
particular library as "The Library" and I don't see that happening at 
the moment.

MDC

Preben Randhol wrote:
> 
> Something like the vim repository perhaps? => http://vim.sf.net/
> 


-- 
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jast.mil/

Send Replies To: m c o n d i c @ a c m . o r g

     "In general the art of government consists in taking as
     much money as possible from one class of citizens to give
     to the other."

         --  Voltaire
======================================================================

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Florian Weimer]

Stephen Leake <Stephe.Leake@nasa.gov> writes:

> I wrote a container library that does all the memory management I
> need.

How do you prevent client code from keeping references to objects in
the container at the point of its finalization?  Is erroneous
execution a possibility?

I don't think memory leaks are the most severe problem, dangling
references are.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Stephen Leake]

Florian Weimer <fw@deneb.enyo.de> writes:

> Stephen Leake <Stephe.Leake@nasa.gov> writes:
> 
> > I wrote a container library that does all the memory management I
> > need.
> 
> How do you prevent client code from keeping references to objects in
> the container at the point of its finalization?  

My library does allow this. It is not a bullet-proof, "assume the
client is an idiot" library.

See the discussion on Grace lists for some reasons why.

however, I normally code my apps so the container is always active;
it's created when the app starts, and is one of the last things
finalized when the app is shutting down.

> Is erroneous execution a possibility?

Yes, in the sense that Ada + my library allows it.

> I don't think memory leaks are the most severe problem, dangling
> references are.

Yes. 

However, note that I said "all the memory management I need", not "all
the memory protection a novice needs". Some small amount of discipline
is expected on the part of the client; the goal is to get a good
balance between container efficiency and protection against bugs.

Now someone will say "C struck a better balance"; more power to them
:).

The issue of whether garbage collection is a good thing for novice
programmers is an interesting one. My initial take would still be "no
- don't let them get used to the crutch". But I'm willing to be
convinced.

-- 
-- Stephe

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Vinzent Hoefler]

Stephen Leake wrote:

>The issue of whether garbage collection is a good thing for novice
>programmers is an interesting one. My initial take would still be "no
>- don't let them get used to the crutch". But I'm willing to be
>convinced.

I don't know about you, but someone should have very good arguments to
convince *me*. ;)


Vinzent.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Marin David Condic]

The thing I don't get is why this whole issue of garbage collection 
seems to periodically poke up in the first place. In the applications I 
have been involved with that did any form of dynamic allocation to begin 
with, we typically implemented some low-level data structures (lists, 
stacks, queues, whatever) and got those working reliably and then never 
dealt with it again. Secondly, they usually used Unchecked_Deallocation 
which was either properly supported such that memory got returned to the 
OS or it never seemed to have an effect with respect to memory leaks. 
Thirdly, nobody seems to be in such dire need of it that they are 
willing to pay anyone to create it in their compilers or we'd see it 
implemented somewhere. Finally, if we were to get a standard library of 
some sort that created/managed the customary containers one would 
expect, it would seem that they should not leak memory, much as dynamic 
strings in Ada manage to do their job without leaking memory.

Maybe we could put this one to rest permanently by getting some kind of 
general consensus that Ada just plain doesn't need it. Or by claiming 
that "Any *Competent* Ada Programmer" doesn't let memory leak. :-)

MDC

Larry Kilgallen wrote:
> 
> 
> Does that paper say _Ada_ programmers spend that much time ?
> 
> If so, then programmers for some other languages must spend 110% of their
> time debugging memory managment issues.


-- 
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jast.mil/

Send Replies To: m c o n d i c @ a c m . o r g

     "In general the art of government consists in taking as
     much money as possible from one class of citizens to give
     to the other."

         --  Voltaire
======================================================================

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Larry Kilgallen]

In article <rw2wufk67oa.fsf@lbrenta.corp.emc.com>, Ludovic Brenta <ludovic.brenta@insalien.org> writes:
> Kilgallen@SpamCop.net (Larry Kilgallen) writes:
> 
>> Ludovic Brenta <ludovic.brenta@insalien.org> writes:
>> 
>> > Yes.  I've never really liked GC myself, but the paper that Martin
>> > mentions says that programmers spend up to 30% of their time doing
>> > (and debugging) memory management, and that perhaps this 30% could be
>> > better spent elsewhere.
>> 
>> Does that paper say _Ada_ programmers spend that much time ?
>> 
>> If so, then programmers for some other languages must spend 110% of their
>> time debugging memory managment issues.
> 
> The paper concentrates on C and C++.  While I agree that Ada
> programmers tend to do less dynamic memory allocation than C/C++
> people, large programs will usually have to do some.  Think about
> containers.  I'd be interested to know what your personal experience
> is.  I'd expect you spend less than 30% of your time but more than 0%
> doing memory management.  Of course, if you only ever allocate on the
> stack and never on the heap (explicitly, that is), then you have no
> need for a garbage collector since you don't create any garbage :)

The last major program I wrote was designed to minimize the amount
of explicit memory allocation (using Ada83).  There were one or two
chains of records that had to be cleaned up in between major groups
of user commands.

There was a "lot" of stack-based memory used.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Ludovic Brenta]

Kilgallen@SpamCop.net (Larry Kilgallen) writes:

> The last major program I wrote was designed to minimize the amount
> of explicit memory allocation (using Ada83).  There were one or two
> chains of records that had to be cleaned up in between major groups
> of user commands.
> 
> There was a "lot" of stack-based memory used.

Interesting.  Did you encounter special difficulties designing your
program with this particular goal in mind?  Like for example
limitations on the size of the stack, or problems sharing objects
between threads?

-- 
Ludovic Brenta.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Larry Kilgallen]

In article <rw2u1ao4rgc.fsf@lbrenta.corp.emc.com>, Ludovic Brenta <ludovic.brenta@insalien.org> writes:
> Kilgallen@SpamCop.net (Larry Kilgallen) writes:
> 
>> The last major program I wrote was designed to minimize the amount
>> of explicit memory allocation (using Ada83).  There were one or two
>> chains of records that had to be cleaned up in between major groups
>> of user commands.
>> 
>> There was a "lot" of stack-based memory used.
> 
> Interesting.  Did you encounter special difficulties designing your
> program with this particular goal in mind?  Like for example
> limitations on the size of the stack, or problems sharing objects
> between threads?

This was not a multi-threaded application, and the primary stack size
is limited only by a general operating system quota that also affects
heap size

	Heap + Stack < Limit

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Larry Kilgallen]

In article <3EEF60F2.5070100@noplace.com>, Marin David Condic <nobody@noplace.com> writes:

> Larry Kilgallen wrote:
>> 
>> 
>> Does that paper say _Ada_ programmers spend that much time ?
>> 
>> If so, then programmers for some other languages must spend 110% of their
>> time debugging memory managment issues.

> Maybe we could put this one to rest permanently by getting some kind of 
> general consensus that Ada just plain doesn't need it. Or by claiming 
> that "Any *Competent* Ada Programmer" doesn't let memory leak. :-)

Garbage collection is important to particular problem domains like AI.
People who need it do not appear to be a significant portion of the
Ada-using public.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Marin David Condic]

And putting it in is not really likely to get them to abandon whatever 
they are already using and start using Ada. We aren't going to make 
*everyone* happy, so perhaps picking carefully who we should urinate-off 
is the wiser course of action. Adding GC to get the AI crowd would 
likely upset more people than it made happy.

MDC

Larry Kilgallen wrote:
> 
> 
> Garbage collection is important to particular problem domains like AI.
> People who need it do not appear to be a significant portion of the
> Ada-using public.


-- 
======================================================================
Marin David Condic
I work for: http://www.belcan.com/
My project is: http://www.jast.mil/

Send Replies To: m c o n d i c @ a c m . o r g

     "In general the art of government consists in taking as
     much money as possible from one class of citizens to give
     to the other."

         --  Voltaire
======================================================================

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Robert I. Eachus]

Larry Kilgallen wrote:

> Garbage collection is important to particular problem domains like AI.
> People who need it do not appear to be a significant portion of the
> Ada-using public.

This is just plain wrong.  There may be some portion of the general 
programming world that needs a generalized garbage collector.  But AI is 
not it.  I wrote a reference counting package in Ada for an AI project 
that thought they needed a garbage collector that would run in a 
background task so that their code was not subject to garbage collection 
delays at arbitrary places.  I showed that the requirements for the GC 
they were asking for couldn't be met that way but a one page package 
could do exactly what they needed via reference counts.

Yes, I know that "ordinary" reference counting can't deal with circular 
chains.  But  it turned out that for their data, there was an easy way 
to deal with that issue, using that low priority task they wanted.  This 
was a data fusion AI for a radar net.  In theory circular references 
could occur and result in garbage that required that background task to 
collect it.  But the system was nicely instrumented, and during the 
entire formal qualifaction period the background task collect zero 
objects. Several hundred million of course were dealt with in real-time 
with guaranteed behavior.

The system had I think, 20,000 potential objects in the pool (all were 
fixed size). The maximum reached during the qual testing was seven 
thousand something with a set of test data from the LA area.  Oh, and 
the code was around four pages, one for the package spec, two for the 
body, plus one for the background task.  The way it worked was that 
every every pointer object contained a level which was in some sense how 
far it was from the root pointer.

Every data object contained two values, the object's level, the count of 
pointers from objects at the next higher level.  If an object was 
pointed to by a new reference from a higher level object, its level was 
raised, and a treewalk was done by the background task to reset the 
levels of other objects.  If you think about it for a minute you will 
see that hoisting a object sets the count of pointers from higher levels 
to one.  If an object reached a reference count of zero, it was put on a 
list to be potentially discarded.  Well, actually there was a global 
flag. If it was set to false, there were no objects in the treewalk, and 
garbage could be discarded immediately.  If it was true, the backgound 
task was doing a treewalk, and objects had to be put on a potential 
holding list.

In practice, in this application the flag was almost never true. 
Setting it to true occured only during a rendezvous between the two 
tasks.  Setting it to false was not a synchronizing event.  It would 
probably be easier to recreate the code than describe it.

So to sum up:

1) In Ada, any thought that you need garbage collection indicates you 
should be using a container class.

2) Writing the container class in Ada is a pretty simple job, if one 
doesn't already exist.

3) No container class needs to have "full" garbage collection provided 
by the environment.

4) Unchecked_Deallocation means that the designer of the container class 
does the checking, and usually provides--if necessary--a Free operation 
that does the right thing. Whatever that may be.

5) For most programers, learning when to use Ada.Strings.Unbounded is 
the closest they will ever come to garbage collection.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Jean-Pierre Rosen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1369 bytes --]


"Larry Kilgallen" <Kilgallen@SpamCop.net> a �crit dans le message de news:vDKsCwFxWhWJ@eisner.encompasserve.org...
> Garbage collection is important to particular problem domains like AI.
> People who need it do not appear to be a significant portion of the
> Ada-using public.

No. Garbage collection is important to particular programming language.
More specifically, if you have a language that does not allow returning objects of
statically unknown size on the stack, then if you need the feature, the "server" will
need to allocate the value (and return a pointer), and the "client" will be responsible
for deallocation. In this case, proper deallocation is generally difficult to do properly,
and having a GC can help.

In Ada, we do return any value on the stack, so this need disappears. As for containers
etc., it is best to hide the (pointer) implementation, and have all collection inside the
container package. You don't need GC for that.

Regarding the initial remark: most people doing AI use these poor languages that
can return only very limited types on the stack; Therefore, they think that GC is
mandatory.

But from personal experience, I was always satisfied with at most finalizable type.

-- 
---------------------------------------------------------
           J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Martin Krischik]

Preben Randhol wrote:

> Ludovic Brenta wrote:
>> - Only available to people using GCC 3.3 as their compiler, as opposed
>>   to GNAT 3.15p.
 
> Which would mean that code written with a GC present won't work well
> compiled with other compilers? I mean if you never use Free yourself.

I only know one Ada compiler suitable for OpenSource development.

But speaking about compatiblity: Can somebody point me to the releveant page
with regards to garbage collectors in Ada200y.

With Regards

Martin

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Martin Krischik]

Ludovic Brenta wrote:

> Martin Krischik <krischik@users.sourceforge.net> writes:
 
>> For details on Boehm-Demers-Weiser conservative garbage collector see:
 
>> http://www.hpl.hp.com/personal/Hans_Boehm/gc/index.html
> 
> The web page you mention says that GCC contains a version of this
> garbage collector.  I understand this has been introduced in GCC 3.0.

You can compile the libgc.a with GCC 2.8+ as well. You just have to do it
yourself then.

> So, to me, there appears to be three approaches to "implement a
> storage pool using the Boehm-Demers-Weiser conservative garbage
> collector in GNAT":

> - Re-implement the GC in Ada, as an external library, so that all Ada
>   programs can use it (even non-GNAT ones if the code is portable).

That would be to much work for a one man project.

> - Write a thick Ada binding to the C garbage collector, with the same
>   end result as above, but requiring an additional library at link
>   time.

That is indeed my plan. 

> - Modify libgnat and libgnarl in GCC 3.3 with a new storage pool that
>   uses the copy of the GC that is in GCC 3.3; this would make the GC
>   available only to GCC 3.3 applications.

That would be cool since all librarys would become garbage collected. And
the Garbage_Collected flag in System.Parameters even suggest that GNAT can
work with a garbage collector. However I would need help from someone who
knows how to patch GNAT. 

Also I would not start patching GCC 3.3 before the GCC 3.3 bug I have in the
pipeline is solved.

With Regards

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Florian Weimer]

Martin Krischik <krischik@users.sourceforge.net> writes:

> I am wondering if it is possible to implement a storage pool using
> the Boehm-Demers-Weiser conservative garbage collector in GNAT.

There are a few pitfalls.  For example, objects with a controlled
component are always reachable from the collector's point of view, so
they can never be collected (in fact, the Ada semantics of
finalization mandate this behavior).  Furthermore, the collector can
hugely benefit from very basic type information (proper flagging of
pointer-free objects and objects without aliased components).

However, the real killer for the storage pool approach is the fact
that the collector will neither track properly the root set, nor task
creation.  You can solve the first problem with a custom
implementation of System.Memory (allocating all objects using the
collector); some more run-time library tweaking can solve the second.

(However, I still don't know if Boehm-Demers-Weiser collector is
actually compatible with GNAT's tasking implementation.)

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Martin Krischik]

Florian Weimer wrote:

> Martin Krischik <krischik@users.sourceforge.net> writes:
> 
>> I am wondering if it is possible to implement a storage pool using
>> the Boehm-Demers-Weiser conservative garbage collector in GNAT.
> 
> There are a few pitfalls.  For example, objects with a controlled
> component are always reachable from the collector's point of view, so
> they can never be collected (in fact, the Ada semantics of
> finalization mandate this behavior).  Furthermore, the collector can
> hugely benefit from very basic type information (proper flagging of
> pointer-free objects and objects without aliased components).

The Boehm-Demers-Weiser conservative garbage collector has atomic memory
which must be pointer free. But this is used only for performance
improvemend.

> However, the real killer for the storage pool approach is the fact
> that the collector will neither track properly the root set, nor task
> creation.  You can solve the first problem with a custom
> implementation of System.Memory (allocating all objects using the
> collector); some more run-time library tweaking can solve the second.

Current status is that I implemented the thin and thick bindung to the
collector and added the collector to my Trace class. Trace is used in any
class and task so it a good test. But I will add further tests.

> (However, I still don't know if Boehm-Demers-Weiser collector is
> actually compatible with GNAT's tasking implementation.)

All seem to work with OS/2. I havn't had time for testing Linux. The mingw
used with GNAT 3.15 Windows does not support all the signaling needed so I
can't link libgc.a into the test programs.

Any help is still be appreciated.

With Regards

Martin.

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Florian Weimer]

Martin Krischik <krischik@users.sourceforge.net> writes:

> The Boehm-Demers-Weiser conservative garbage collector has atomic
> memory which must be pointer free. But this is used only for
> performance improvemend.

Flagging atomic memory (and memory without internal access points) is
crucial if you allocate large data structures (and cannot use the
generational collector for some reason).

> Current status is that I implemented the thin and thick bindung to the
> collector and added the collector to my Trace class. Trace is used in any
> class and task so it a good test. But I will add further tests.

Interesting.  A project of mine which is still under development
changes GNAT itself to support the Boehm-Demers-Weiser collector:

  <http://www.enyo.de/fw/software/gnat-gc/>

The project is not finished, but I think I've implemented the most
complicated things.

Re: Boehm-Demers-Weiser conservative garbage collector and GNAT

[Martin Krischik]

Florian Weimer wrote:

> Martin Krischik <krischik@users.sourceforge.net> writes:
 
>> The Boehm-Demers-Weiser conservative garbage collector has atomic
>> memory which must be pointer free. But this is used only for
>> performance improvemend.
 
> Flagging atomic memory (and memory without internal access points) is
> crucial if you allocate large data structures (and cannot use the
> generational collector for some reason).

I think so too.
 
>> Current status is that I implemented the thin and thick bindung to the
>> collector and added the collector to my Trace class. Trace is used in any
>> class and task so it a good test. But I will add further tests.
> 
> Interesting.  A project of mine which is still under development
> changes GNAT itself to support the Boehm-Demers-Weiser collector:

Damm. I made the initial post to prevent duplicate development and now it
happend anyway. But prehaps is not to late to join forces.

>   <http://www.enyo.de/fw/software/gnat-gc/>

I have a look at it.

> The project is not finished, but I think I've implemented the most
> complicated things.

Well, I am almost finished but I need some more testing. Of course it is
easier for me since the programer need to specify the right Storage_Pool
for each access when the garbage collector is implemented outside the
compiler environment.

With Regards.

Martin
-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com