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

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

[W. Wesley Groleau (Wes)]

Robert Dewar says:

:> 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....

You are refuting a claim I didn't make.  My QUERY was, "Since Ada now
lets us customize garbage collection (or lack of) to each ADT, how many
_Ada_ designers would be willing to pay extra for a reliable transparent
global GC?"  I doubt that any would be willing to pay for one that is
unreliable or non-transparent.

Part of the Ada philosophy (at least for me) is that if something is a
requirement, I want to see it somewhere in code.  If it isn't a requirement,
I don't want it cluttering the code AND I don't want it interfering with
requirements (including cost and schedule requirements).

"see it somewhere in code" can be satisfied by adequate guarantees from
a vendor or from testing that the requirement is met.  Can obtaining those
guarantees be easier than properly engineering one's ADTs?  Is this another
hazard comparable to "reuse without review"?  (Please don't resurrect
Ariane 5 :-)

---------------------------------------------------------------------------
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

[Robert A Duff]

In article <9610171549.AA07433@most>,
W. Wesley Groleau (Wes) <wwgrol@PSESERV3.FW.HAC.COM> wrote:
>You are refuting a claim I didn't make.  My QUERY was, "Since Ada now
>lets us customize garbage collection (or lack of) to each ADT, ...

How do you mean?  GC is, in general, a global issue, and it's not easy
to customize it for particular types.  There are things you can do with
controlled types, but all the schemes I can think of have some major
drawbacks.  Can you explain in more detail what you mean?  (Note: In
most of the programs I write (compilers and the like) there are hundreds
of mutually recursive types -- that is, records containing pointers to
other records and such.)

>...how many
>_Ada_ designers would be willing to pay extra for a reliable transparent
>global GC?" ...

>...I doubt that any would be willing to pay for one that is
>unreliable or non-transparent.

Well, there are a lot of people making a lot of money selling unreliable
software, these days.  :-(

As for non-transparent, well, I want to have some hooks into the GC, so
that I can customize it for particular purposes.  For efficiency, if
nothing else.

>Part of the Ada philosophy (at least for me) is that if something is a
>requirement, I want to see it somewhere in code.  If it isn't a requirement,
>I don't want it cluttering the code AND I don't want it interfering with
>requirements (including cost and schedule requirements).

But memory management is an implementation detail -- it's not likely to
show up in the requirements.  Most programs shouldn't leak storage, or
dereference dangling pointers, despite the fact that the requirements
don't say anything about it.

- Bob

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

[W. Wesley Groleau (Wes)]

It looks like Jon Anthony attempted to answer my question
in a post that never got to me.  And if you were to believe Alta Vista
you'd think neither Jon nor I ever posted on the subject!

But I DID see Jon's
> Second, none of this [finalization] stuff covers all the cases.  ....
> 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.

Let me put my question another way:

What are the pros and cons of the following three choices?

Choice One (in the spec):
  Declare a data type.  Put a comment on it saying
  -- Make sure you put calls to the cleanup routines in in every place
  -- where an object of this type might leave scope.  Make sure you
  -- put an exception handler in every routine that declares one of these,
  -- or else ensure that no exception can occur.  And better guarantee that
  -- exceptions cannot occur in declarative regions.

Choice Two (in the spec):
  -- If you intend to use this data type, you had better ensure that your
  -- compiler has a good garbage collector, or get an add-on that can
  -- work with your compiler's allocation methods.

Choice Three (in the BODY):

   procedure Finalization (...) is
   -- this will ensure that cleanup cannot be forgotten.

What are the cases Finalization doesn't cover?  (Other than those the
programmer DECIDED not to apply it to.)

And what is so hard about "roll your own"?  After all this argument about
how and why this and that type of collector can bite you on the behind,
how can anyone complain that

   begin
     Free (Param);
   end Finalization;

is so difficult.  Sure, the compiler might fail to call it, but we have
better ways of dealing with naughty compilers than adding on outside tools
of arguable value.

---------------------------------------------------------------------------
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

[Michael F Brenner]

This argument that something is an implementation detail is used (often
by other people whose initials also happen to be RD). Why should that
invalidate the Requirement we have for those implementation details?
If we want Ada compilers to generate code that runs as fast as C code,
what is so wrong with that, particularly when the language has been 
designed to be highly optimizable. There has evolved a method of arguing 
down people who present their problems in this forum, which draws a magic
line as to what is a language requirement and what is an implementation
detail.   

I do not agree with where that line has been drawn. 

Let us start by defining an Ada compiler as a computer program that
translates Ada source code into object code (whether byte code, 
machine code, or an interpretive data structure which is not much 
more than annotated source code). 

The Requirements on this code fall into two categories: first, there
is a requirement to execute the object code in accordance with the
semantic meaning assigned by the reference manual with no errors such  
as memory leaks or sigsegv failures, and second, there is a Requirement
to meet the realtime expectations of the users. The first requirement
is of a different nature than the second, but is no more nor less 
important than the the second. If a compiler vendor places artificial
limitations on the capacity or the speed of the object code generated
by the compiler, users, such as myself will whine that we need more
capacity and speed. A valid answer to this need is not that we redefine
a compiler to not generate code, nor that speed is not a semantic 
requirement therefore it is not a requirement. In the original Rationale
efficiency of realtime embedded systems was The primary requirement 
of Ada and that efficiency was to be delivered in the most reliable 
fashion we could devise. The recent answers to all requests for 
efficiency on comp.lang.ada have lambasted the requestors with this
new-speak (that compilers are not translators and that efficiency 
is not a valid requirement). This has to stop. We have finished
defining the language, except for a very small number of mistakes
that have been discussed elsewhere in comp.lang.ada. IT IS TIME TO
DISCUSS HOW WE CAN GET THE EFFICIENCY NOW. Efficiency is not a game,
nor is it somebody's opinion, it is the primary factor in deciding
what language to use. Requests for efficiency, whether in tasking, 
garbage collection, unsigned numbers, in the code generated by
generic instantiations, or in dispatching should be taken seriously,
and recognized as a requirement on the same level as a semantic
requirement. When we revise the Ada Language Reference Manual next, it
should be fixed precisely in those places where more efficiency can
be put in without disturbing the reliability.
 
a requirement to do 

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

[Robert A Duff]

In article <54gb7a$nbh@linus.mitre.org>,
Michael F Brenner <mfb@mbunix.mitre.org> wrote:
>This argument that something is an implementation detail is used (often
>by other people whose initials also happen to be RD). Why should that
>invalidate the Requirement we have for those implementation details?

I (I think I'm the RD you're replying to) never meant to say that such
details are unimportant.  I meant to say that it goes without saying --
any program that leaks memory, or dereferences dangling pointers, has a
bug.  (Well, in some special circumstances, it's OK to leak memory.)
There's no need for the requirements document to say so, and, indeed,
most don't.  Similarly, no requirements document says "this program
shall not index arrays out of bounds."  It goes without saying -- that's
just a bug.  The arrays in a program are implementation details.

For the record: I agree that there are situations that are clearly bugs
in a given Ada compiler, but the Ada compiler obeys the Ada standard.
If an Ada compiler takes an hour to compile a 5-line package, that's a
bug, despite the fact that the RM doesn't say so.

>....When we revise the Ada Language Reference Manual next, it
>should be fixed precisely in those places where more efficiency can
>be put in without disturbing the reliability.

Don't hold your breath.  Do you know of *any* language standard that
addresses efficiency in any way?

I'm not trying to say efficiency if unimportant -- of course it is --
but I don't know of any feasible way to address it in a language
standard.

- Bob

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

[Larry Kilgallen]

In article <54gb7a$nbh@linus.mitre.org>, mfb@mbunix.mitre.org (Michael F Brenner) writes:
> This argument that something is an implementation detail is used (often
> by other people whose initials also happen to be RD). Why should that
> invalidate the Requirement we have for those implementation details?
> If we want Ada compilers to generate code that runs as fast as C code,
> what is so wrong with that, particularly when the language has been 
> designed to be highly optimizable. There has evolved a method of arguing 
> down people who present their problems in this forum, which draws a magic
> line as to what is a language requirement and what is an implementation
> detail.   
> 
> I do not agree with where that line has been drawn. 
> 
> Let us start by defining an Ada compiler as a computer program that
> translates Ada source code into object code (whether byte code, 
> machine code, or an interpretive data structure which is not much 
> more than annotated source code). 
> 
> The Requirements on this code fall into two categories: first, there
> is a requirement to execute the object code in accordance with the
> semantic meaning assigned by the reference manual with no errors such  
> as memory leaks or sigsegv failures, and second, there is a Requirement
> to meet the realtime expectations of the users.

I presume that your realtime expectations "requirement" is not based
on the fact that there is a realtime annex, or else you would have
listed other requirements.

There are many other requirements as strong as realtime expectations
and the other annexes which users have which are not codified.  Ease
of use is one, for example in the generation of clear and complete
error messages.  Many Ada compilers have built a tradition of very
precise error messages, and as much as those have saved me time, I
would hate to think they were the result of excessive deliberation
in a standards process. The legend as I heard it is that the compiler
I have used most got the idea from another compiler and put emphasis
on error message quality.

As people have learned from the Ada Mandate, rulemaking does not
always lead to the success for which one might hope.

I just got over a bit of sticker shock from someone's idea of a
price for an Ada compiler, and I would hate to think that any of
that price was due to a death-wish to be a pioneer in the area of
garbage collection.  Since nobody claims to have a working Ada 95
compiler which collects garbage, it sounds like an excellent research
project.   Even though Robert Dewer does not see it as cost-effective
for ACT, perhaps he will be accosted by some advanced student in need
of thesis work.  After several such students have tried at various
institutions, and some of them have succeeded, then implementors of
production compilers may wish to try their hand.  In the meantime
let them work on the trite possibilities which are fully understood
but not yet implemented, such as even better error messages, more
platforms, more annexes, etc.

Larry Kilgallen

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

[Jon S Anthony]

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

> Let me put my question another way:
> 
> What are the pros and cons of the following three choices?
> 
> Choice One (in the spec):
>   Declare a data type.  Put a comment on it saying
>   -- Make sure you put calls to the cleanup routines in in every place
>   -- where an object of this type might leave scope.  Make sure you
>   -- put an exception handler in every routine that declares one of these,
>   -- or else ensure that no exception can occur.  And better guarantee that
>   -- exceptions cannot occur in declarative regions.

Pro: Can be done at C level language constructs (simple RT impl. model)

Con: Low level => usually broken (i.e., unlikely that person can keep track
     of this level of bookkeeping for anything beyond a trivial program).
     That is, complex/complicated user (programmer) model.
   
     The sort of thing that generally results in a) leaks, b) dangling
     references.

     Requires a lot of manual futzing and checking (language offers no
     real help).  You're on your own.

     Also, just doesn't work in some situations (without
     amending the various "make sures")


> Choice Two (in the spec):
>   -- If you intend to use this data type, you had better ensure that your
>   -- compiler has a good garbage collector, or get an add-on that can
>   -- work with your compiler's allocation methods.

Forget the "add-on" - that will at best be a conservative collector.  For
the precise collector:

Pro: You need not worry about memory management at the programmer's level.
     Frees you, the human, to worry about more important things.

     Higher level of abstraction (simpler user model)

     More robust in non trivial programs since it does not rely on human
     bookkeeping

     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)

Con: Requires more of vendor => more $$ could be involved in purchase and
     support.  Of course the same is true for _ANY_ high level construct,
     such as tasking, generics, etc.  But I am more than willing to pay
     more for a language/impl that supports these because in the long run
     it is _CHEAPER_.

     Can potentially fool you into thinking that you don't need to know
     anything about what is going on at this level and thereby you could
     end up wondering why your stuff isn't working quite like you thought.


> Choice Three (in the BODY):
> 
>    procedure Finalization (...) is
>    -- this will ensure that cleanup cannot be forgotten.

Pro: Works better than nothing (which is choice one above...)

Con: Doesn't work everywhere

     Expensive (in time and space)

     Requires you to roll your own managers per type per application (but
     in those cases where it doesn't work, need to augment with other stuff
     - e.g. your own storage pools and management...)


> What are the cases Finalization doesn't cover?  (Other than those the
> programmer DECIDED not to apply it to.)

Lots's of places.  Finalization works pretty darn well for _stack_
allocated things, but pretty poorly (even not at all) for long lived
shared heap allocated things.  Since the latter are very important in
most large scale programs of any note, ...


> And what is so hard about "roll your own"?  After all this argument about
> how and why this and that type of collector can bite you on the behind,
> how can anyone complain that

What's so hard about rolling your own tasking model on top of the base
thread package of your OS?  What's so hard about rolling your own
polymorphic dispatching model on top of variant programming
constructs?  What's so hard about using the OS file system directory
structure for hierarchical subsystems?  You get the picture.  GC
really is this fundamental a construct.

Collectors won't bite you on the behind if they are precise and offered as
part of the total package from the vendor.


> is so difficult.  Sure, the compiler might fail to call it, but we have
> better ways of dealing with naughty compilers than adding on outside tools
> of arguable value.

It may fail to be called not because the compiler is wrong, but because
you Joe Programmer got the bookkeeping wrong.  Worse - it may be called
when it should NOT be called for the same reason.

/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)

[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

[Jon S Anthony]

In article <EACHUS.96Oct24211243@spectre.mitre.org> eachus@spectre.mitre.org (Robert I. Eachus) writes:

> 
> In article <JSA.96Oct22152111@alexandria> jsa@alexandria (Jon S Anthony) writes:
> 
>    > > Choice Two (in the spec): 
>    > >   -- If you intend to use this data type, you had better ensure
>    > >   -- that your compiler has a good garbage collector, or get an
>    > >   -- add-on that can work with your compiler's allocation
>    > >   -- methods.
> 
>    > Forget the "add-on" - that will at best be a conservative collector.  For
>    > the precise collector:
> 
>    > 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.

Nah, you're in the weeds  for several reasons.  Hans Bohem did a good job of
listing many.  No need to repeat them - just read them.


>   > > What are the cases Finalization doesn't cover?  (Other than those the
>   > > programmer DECIDED not to apply it to.)
> 
>   > Lots's of places.  Finalization works pretty darn well for _stack_
>   > allocated things, but pretty poorly (even not at all) for long lived
>   > shared heap allocated things.  Since the latter are very important in
>   > most large scale programs of any note, ...
> 
>     Let's take the absolute best example of a structure that "requires"
> garbage collection an arbitrary graph consisting of nodes with
> arbitrary numbers of edges, and cycles allowed.  Had to implement one
> of those recently, and the requirements allowed nodes to be moved from
> one graph to another.
>
>    The finalization routine took five lines, and neat trick was in the
> Adjust routine.

What "adjust" routine?  When you have limited types you don't even
_have_ adjust.  Besides, "adjusting" still reflects a value semantic
mentality and that is not always what is needed (in fact it is often
not what is desired).  Do you prevent a client from allocating one of
these nodes?  Assigning that access result to some access variable?
On the stack?  Or maybe in a field of a variable of another structured
type?  What about those references?  You can't have "controlled access
types".  Yes, you can hack a clumsy, heavy weight version which in the
end just kicks the problem up one level anyway.

I don't see the relevance of what you are trying to say here.

> From a garbage collection point of view it was "extra overhead" but

Yes.


> 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.)

What makes you think that is the only, let alone the best, option????


/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

[Robert I. Eachus]

In article <JSA.96Oct22152111@alexandria> jsa@alexandria (Jon S Anthony) writes:

   > > Choice Two (in the spec): 
   > >   -- If you intend to use this data type, you had better ensure
   > >   -- that your compiler has a good garbage collector, or get an
   > >   -- add-on that can work with your compiler's allocation
   > >   -- methods.

   > Forget the "add-on" - that will at best be a conservative collector.  For
   > the precise collector:

   > 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.

  > > Choice Three (in the BODY):
  > > 
  > >    procedure Finalization (...) is
  > >    -- this will ensure that cleanup cannot be forgotten.

  > Con: Doesn't work everywhere

  >	Expensive (in time and space)

  >	Requires you to roll your own managers per type per application (but
  >	in those cases where it doesn't work, need to augment with other stuff
  >     - e.g. your own storage pools and management...)

  > > What are the cases Finalization doesn't cover?  (Other than those the
  > > programmer DECIDED not to apply it to.)

  > Lots's of places.  Finalization works pretty darn well for _stack_
  > allocated things, but pretty poorly (even not at all) for long lived
  > shared heap allocated things.  Since the latter are very important in
  > most large scale programs of any note, ...

    Let's take the absolute best example of a structure that "requires"
garbage collection an arbitrary graph consisting of nodes with
arbitrary numbers of edges, and cycles allowed.  Had to implement one
of those recently, and the requirements allowed nodes to be moved from
one graph to another.

   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.)




--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

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