Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Henry G. Baker]

In article <D06r8x.JBy@inmet.camb.inmet.com> mg@asp.camb.inmet.com (Mitch Gart) writes:
>then RC sounds like a reasonable memory reclamation scheme for Ada.

You should be prepared for huge overheads when updating reference
counts on shared objects in a multiple-threaded (multiple-tasked)
program.  (Not that GC in such an environment is all that easy, but RC
is no panacea either.)

Henry Baker
Read (192.100.81.1) ftp.netcom.com:/pub/hb/hbaker/README for ftp-able papers.
WWW archive: ftp://ftp.netcom.com/pub/hb/hbaker/home.html
************* Note change of address ^^^        ^^^^

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Robert Firth]

In article <hbakerD07221.1C0@netcom.com> hbaker@netcom.com (Henry G. Baker) writes:

>You should be prepared for huge overheads when updating reference
>counts on shared objects in a multiple-threaded (multiple-tasked)
>program.

Not necessarily.  The PE3200, for example, has an "add to memory"
insturction that seems tailor made for this problem.

	AM reg, mem

In practice, the constants +1 and -1 were so often used as the
addend that I simply had the compiler permanently allocate two
registers to them, so any reference counting became a single
atomic instruction.

Well, things are now riscier.  So here's another way: make the
reference counting a sequence of instructions:

	L reg, mem
	AI reg, 1
	S reg, mem

In the task context switch, check whether you interrupted that
sequence *and the memory address points into the shared heap*
(trivial on a risc machine with essentially one memory address
mode), and simply slave whatever didn't get done.  On some
machines, it may be cheaper always to slave rather than even
bother checking the address.

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Robert Dewar]

CISC instructions like add to memory usually are inefficient, of course in
the context of a CISC machine, they may be no more inefficient than any
other instructions on the machine, but I think you will find that most
machines having add to memory cannot execute this operation any faster
than a modern RISC can get the same effect with a sequence of instructions.

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Rick Busdiecker]

In article <D06r8x.JBy@inmet.camb.inmet.com> mg@asp.camb.inmet.com (Mitch Gart) writes:

   In Lisp everything is a pointer.

Ugh.  This statement is simply false.  You *could* implement a lisp
that way, but it would be a bad idea.

Which data types are direct or indirect and when data is boxed or
unboxed varies across implementations, but in any real lisp
implementation, considerable effort is made to manipulate certain
classes of data (numbers, for example) directly rather than indirectly
through a pointer.

   If the following points are true about a reference counting scheme:

   - protects against memory leaks
   - predictable, guaranteed to not stop a program while doing GC
   - costs a bit, in proportion to how heavily pointers are used,
     but the cost is predictable
   - relatively simple to implement

   then RC sounds like a reasonable memory reclamation scheme for Ada.

Yes, if those points were true of RC then it would be a reasonable
scheme.

--
Rick Busdiecker <rfb@lehman.com>      Please do not send electronic junk mail!
  Lehman Brothers Inc.
  3 World Financial Center  "The more laws and order are made prominent, the
  New York, NY  10285-1100   more thieves and robbers there will be." --Lao Tzu

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[R. William Beckwith]

F.Y.I.:

Our Fresco/Corba/Ada 95 implementation currently uses reference
counting.  I am planning to implement garbage collection in
Ada 95 when I get an Ada 95 compiler that has the memory pools
implemented.

I will generate some specific benchmark numbers on RCing
v.s. GC method 1 v.s. GC method 2...  I'll post the results
when I get them.

Fresco obviously is heavily tilted towards the GUI domain.
Since many applications are GUI bound the numbers may be
of general use.

... Bill

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[R. William Beckwith]

Kevin Warne (kevinw@whistler.com) wrote:

: Depending on the number of inc/decs, the cost of RCing can be very
: significant.  A single inc + dec that hits on-chip cache would 
: take 6 cycles.  Multiply by the avg. number of inc/decs taken
: per object and the cost and percentage of cache misses and I think
: you'll find the incrementing and decrementing operations are 
: consequential after all.

An incr/decr only occurs when there is a change to the graph of
objects.  If the graph does not change, then there is not need
to incr/decr the counts.

Paul Wilson's RT, generational, incremental GC'tor causes work
when the graph of objects is changed (write barrier).  Surely,
the color changes required with a graph change can be as fast
as a simple incr/decr operation.

Maybe my perspective is skewed because I have been RC'ing in Ada 9X.
I realize that C++ calls a copy constructor if you pass an object
as an argument by value.  But I was under the assumption that every
C++ RC'ing implementation worth its salt would require that the
reference objects are passed by reference (&).

The other trick about RC'ing is that you don't have to keep the
counts in the objects, you can keep them all in the same data
structure so that you pages are unnecessarily dirtied.

... Bill

------------------------------------------------------
e-mail: Bill.Beckwith@ois.com        |    Team Ada
Objective Interface Systems, Inc.    | dist, full O-O
1895 Preston White Drive, Suite 250  | multithreading
Reston, VA  22091-5448  U.S.A.       |    built in

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Henry G. Baker]

In article <3bg6ci$18k@gamma.ois.com> beckwb@ois.com (R. William Beckwith) writes:
>An incr/decr only occurs when there is a change to the graph of
>objects.  If the graph does not change, then there is not need
>to incr/decr the counts.

This is fine, so long as every object is 'nailed down' directly or
indirectly to a root somewhere.  A problem occurs with newly allocated
objects that someone forgets to nail down, or forgets to deallocate it
after deciding _not_ to keep it.  A similar problem occurs when an
object is being destroyed, and it has been unhooked, but due to some
condition -- e.g., an error -- the program forgets to deallocate it.

An analogous situation happens in some GC systems -- e.g., Kyoto
Common Lisp.  If a compiled function returns a newly allocated object
which is then used as an argument to another compiled function which
then allocates storage, the GC can recycle the object, because it was
never 'nailed down' -- e.g., by storing a reference to it in the
run-time stack.  For this reason, one must used 'object' declarations
with some care in compiled code.

Henry Baker
Read (192.100.81.1) ftp.netcom.com:/pub/hb/hbaker/README for ftp-able papers.
WWW archive: ftp://ftp.netcom.com/pub/hb/hbaker/home.html
************* Note change of address ^^^        ^^^^

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[David Weller]

In article <DAG.94Nov30090717@bellman.control.lth.se>,
Dag Bruck <dag@control.lth.se> wrote:
>I was under the impression that the user cannot define the assignment
>operator in Ada.  If so, how can you implement safe RC except by going
>through a private type?

That's incorrect.  Assignment operations can be redefined in Ada,
provided the type is derived from the Controlled class.  Implicit
initialization, assignment, and finalization mayy be overidden by the
user.

Redefinition of assignment in Ada94, however, is more restrictive
than in C++, since the type tags of both the left and right must be
equal.


-- 
Proud (and vocal) member of Team Ada! (and Team OS/2)        ||This is not your
   	      Ada -- Very Cool.  Doesn't Suck.               ||  father's Ada 
For all sorts of interesting Ada tidbits, run the command:   ||________________
"finger dweller@starbase.neosoft.com | more" (or e-mail with "finger" as subj.)
	|"Quitting C++ isn't so difficult, provided you show as much |
	|	persistence stopping as you did starting." dweller   |

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Erik Naggum]

[David Weller]

|   Redefinition of assignment in Ada94, however, is more restrictive
|   than in C++, since the type tags of both the left and right must be
|   equal.

Ada9_4_?  did ISO DIS 8652 Ada pass (voting expired 1994-10-30) with
sufficiently few comments that it will be published in 1994?  if so,
congratulations!

#<Erik>
--
Microsoft is not the answer.  Microsoft is the question.  NO is the answer.

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Michael Feldman]

In article <19941130T175838Z.enag@naggum.no>,
Erik Naggum  <erik@naggum.no> wrote:
>[David Weller]
>
>|   Redefinition of assignment in Ada94, however, is more restrictive
>|   than in C++, since the type tags of both the left and right must be
>|   equal.
>
>Ada9_4_?  did ISO DIS 8652 Ada pass (voting expired 1994-10-30) with
>sufficiently few comments that it will be published in 1994?  if so,
>congratulations!

A note was posted to comp.lang.ada the other day to the effect that
the ballotting is over and the standard is in the hands of the ISO office 
for final approval. There is a nonzero probability that this will
happen in 1994, at least that's the way I understood the note.

Mike Feldman
------------------------------------------------------------------------
Michael B. Feldman -  chair, SIGAda Education Working Group
Professor, Dept. of Electrical Engineering and Computer Science
The George Washington University -  Washington, DC 20052 USA
202-994-5919 (voice) - 202-994-0227 (fax) - mfeldman@seas.gwu.edu (Internet)
------------------------------------------------------------------------
         Ada on the World-Wide Web: http://lglwww.epfl.ch/Ada/
------------------------------------------------------------------------
"Illegitimi non carborundum." (Don't let the bastards grind you down.)
------------------------------------------------------------------------

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Bob Duff]

In article <DAG.94Nov30090717@bellman.control.lth.se>,
Dag Bruck <dag@control.lth.se> wrote:
>>>>>> "R" == R William Beckwith <beckwb@ois.com> writes:
>
>R> Maybe my perspective is skewed because I have been RC'ing in Ada
>R> 9X.  I realize that C++ calls a copy constructor if you pass an
>R> object as an argument by value.  But I was under the assumption
>R> that every C++ RC'ing implementation worth its salt would require
>R> that the reference objects are passed by reference (&).

>No, why should it?  The copy constructor has to manipulate the RC,
>that's all.  If you pass arguments by reference, RC is not changed
>(you're passing the object, not its value).

In Ada 9X, all controlled types (the ones you can define reference
counting for) are passed by reference.  This seems more efficient than
passing by copy and incr/decr-ing a reference count every time.

Whether reference counting is a good idea or not (vs. "full" Garbage
Collection) is another question -- Henry Baker's many papers on the
subject are quite interesting.

>I was under the impression that the user cannot define the assignment
>operator in Ada.  If so, how can you implement safe RC except by going
>through a private type?

You cannot directly override ":=" in Ada, but ":=" always does
"adjustment", and for controlled types, you can override Adjust.
So you *can* implement safe reference counting in Ada 9X.

Controlled types are not required to be private, but they are required
to be records (or private completed as record).  So you have to wrap
your access type in a record type (a record extension actually) to make
it controlled.

Note that this is done on a per-type basis.  So some types can be
reference-counted while others are not.

>					-- Dag Bruck

- Bob
-- 
Bob Duff                                bobduff@inmet.com
Oak Tree Software, Inc.
Ada 9X Mapping/Revision Team (Intermetrics, Inc.)

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Bill Birch]

Hi all,

Somebody on this thread said that RC takes a large proportion of
the available time, and that RC has to work in the same way
as smart pointers in C++. 

Here are some results from a run of RefLisp (an RC Lisp I wrote ).
To cut a long story short RC appears to consume 20% of CPU time
whilst running a tree-sort and a big-num 2^200 calculation.

Note that RefLisp does NOT increment reference counts in CONS, it attempts
to defer reference counts to the execution of side-effects. My personal
theory is that reference counts are only required where a function has 
the potential for side-effects. For example in RefLisp, the function
call (oblist) does not result in any reference counting. (oblist) has
no side-effects, it just creates a list.

The call (setf x (oblist)) does require reference counting, since
the variable x must semaphore to the other processes and functions
in the system that it is using the objects returned by oblist. RC
is merely an application of the Semaphore concept.

Of course the ultimate side-effect is the circular reference, something
which RC cannot handle (yet).

Here follows an exerpt from the RefLisp user guide. "purge", "reference"
and "dereference" are the RC routines.


Bill




17.2.2	Internal Function Calling Profile

The following table is the output from the UNIX "prof" utility run on
Version 2.28 of RefLisp, compiled with the -p option. The test was run
using sort.lsp and bignum.lsp.

Subsequent versions will have the most used functions replaced by
macros. Functions replaced with macros are indicated by a leading *.
__mcount is the profiling subroutine, and should be excluded from
discussions about resource usage. The less-frequently used functions
are not listed.

Name                 %Time     Seconds     Cumsecs  #Calls   msec/call
.__mcount             37.0       30.46       30.46
*car                   8.6        7.06       37.52 3569237      0.0020
*cdr                   7.6        6.28       43.80 3208130      0.0020
.eval                  5.4        4.43       48.23  471698      0.0094
.dereference           5.3        4.38       52.61 1087608      0.0040
*atom                  3.9        3.24       55.85 3509798      0.0009
.purge                 3.7        3.05       58.90  745590      0.0041
.reference             3.6        2.93       61.83 1852270      0.0016
*subrp                 3.0        2.45       64.28  992799      0.0025
*fsubrp                2.2        1.84       66.12  705840      0.0026
*numberp               2.1        1.71       67.83  478750      0.0036
*bigstringp            1.7        1.39       69.22  468474      0.0030
*stringp               1.7        1.38       70.60  473896      0.0029
.eval_list             1.6        1.34       71.94  323045      0.0041
.ref_evlis             1.6        1.30       73.24  136037      0.0096
.value                 1.5        1.23       74.47  678077      0.0018
.get_cell              1.5        1.21       75.68  366122      0.0033
*idp                   1.0        0.83       76.51  831715      0.0010
.apply                 1.0        0.80       77.31  161523      0.0050
.c_release             0.9        0.77       78.08  365852      0.0021
.evprogn               0.7        0.58       78.66   65282      0.0089
.savelis               0.6        0.51       79.17   40386      0.0126
.cons                  0.6        0.51       79.68  347003      0.0015
.setlis                0.4        0.35       80.03   40386      0.0087
.cfr                   0.4        0.32       80.35  121137      0.0026
.set                   0.3        0.24       80.59  131774      0.0018
.ap_lambda             0.2        0.17       80.76   40386      0.0042
.fixp                  0.2        0.13       80.89   50869      0.0026
.cir                   0.1        0.09       80.98   47130      0.0019
.restorlis             0.1        0.09       81.07   40386      0.0022
*floatp                0.1        0.09       81.16   55894      0.0016
.quotient              0.1        0.08       81.24    3378      0.024
.evcond                0.1        0.08       81.32   24486      0.0033
.equal                 0.1        0.07       81.39   12634      0.0055
.bcar                  0.1        0.06       81.45   21787      0.0028
.__mcount              0.1        0.06       81.51
.lessp                 0.1        0.06       81.57    7232      0.008
.newicell              0.1        0.06       81.63   14239      0.0042
.eq                    0.1        0.06       81.69  121158      0.0005
.plus                  0.1        0.06       81.75    5052      0.012
._ptrgl                0.1        0.05       81.80


-- 

bill@zikzak.apana.org.au	 Bill Birch on ZikZak (Melbourne, Australia)

                     {:-) A bas la loi Toubon! {:-)

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Hans Boehm]

beckwb@ois.com (R. William Beckwith) writes:

>Kevin Warne (kevinw@whistler.com) wrote:

>: Depending on the number of inc/decs, the cost of RCing can be very
>: significant.  A single inc + dec that hits on-chip cache would 
>: take 6 cycles.  Multiply by the avg. number of inc/decs taken
>: per object and the cost and percentage of cache misses and I think
>: you'll find the incrementing and decrementing operations are 
>: consequential after all.

>An incr/decr only occurs when there is a change to the graph of
>objects.  If the graph does not change, then there is not need
>to incr/decr the counts.

To reiterate Henry Baker's reply, this isn't always sufficient.
You either need to count references from local and global variables as well,
or you need to be very careful when you write your code.  My experience
is that you're usually tempted to do the latter and end up spending
lots of time debugging.  (My experience stems from a 50K-line
C program.  I'm unconvinced that either C++ or Ada facilities
would help, though they do make dumb/slow reference counting much easier.)

>Paul Wilson's RT, generational, incremental GC'tor causes work
>when the graph of objects is changed (write barrier).  Surely,
>the color changes required with a graph change can be as fast
>as a simple incr/decr operation.

You do need at least a write barrier on the heap for incremental collection.
(In the best case, the dirty bits in the MMU are a sufficient
write barrier, though not for that algorithm.  But using them is likely
to increase collector latency, though probably not above the simple RC scheme.
And your machine may not have hardware dirty bits, though the Intel
architecture does.  And your OS may already need those bits for other
things, adding a bit of overhead.)

The crucial issue in my mind is whether you can safely avoid counting
pointers from the stack.

>Maybe my perspective is skewed because I have been RC'ing in Ada 9X.
>I realize that C++ calls a copy constructor if you pass an object
>as an argument by value.  But I was under the assumption that every
>C++ RC'ing implementation worth its salt would require that the
>reference objects are passed by reference (&).

This no doubt helps, but isn't without cost.  At the implementation
level, instead of passing a pointer to a heap location and adjusting the
reference count, you're passing a pointer to a (stack allocated) indirect
location which points to the heap.  You're likely to introduce
additional memory references in accessing the result, and you may force
the actual parameter into memory, out of a register.  It also doesn't
help with local variables that are updated.

>The other trick about RC'ing is that you don't have to keep the
>counts in the objects, you can keep them all in the same data
>structure so that you pages are unnecessarily dirtied.

Yes, but that isn't free either.

Hans-J. Boehm
(boehm@parc.xerox.com)
Standard disclaimer ...

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[R. William Beckwith]

Hans Boehm (boehm@parc.xerox.com) wrote:
: beckwb@ois.com (R. William Beckwith) writes:

: >An incr/decr only occurs when there is a change to the graph of
: >objects.  If the graph does not change, then there is not need
: >to incr/decr the counts.

: To reiterate Henry Baker's reply, this isn't always sufficient.
: You either need to count references from local and global variables as well,
: or you need to be very careful when you write your code.  My experience
: is that you're usually tempted to do the latter and end up spending
: lots of time debugging.  (My experience stems from a 50K-line
: C program.  I'm unconvinced that either C++ or Ada facilities
: would help, though they do make dumb/slow reference counting much easier.)

Good point.  If you know you have other strong references to an
object, you can use weak pointers for interators and such.  That
helps a little.  I would recommend using weak pointers for any object
that doesn't have a strong pointer to it declared in the immediate
or enclosing scope.

: >Paul Wilson's RT, generational, incremental GC'tor causes work
: >when the graph of objects is changed (write barrier).  Surely,
: >the color changes required with a graph change can be as fast
I meant:					  can't
: >as a simple incr/decr operation.

: You do need at least a write barrier on the heap for incremental collection.
: (In the best case, the dirty bits in the MMU are a sufficient
: write barrier, though not for that algorithm.  But using them is likely
: to increase collector latency, though probably not above the simple RC scheme.
: And your machine may not have hardware dirty bits, though the Intel
: architecture does.  And your OS may already need those bits for other
: things, adding a bit of overhead.)

Hmmm.  The code that gets executed on processing the write barrier seems
like it would take alot longer than incr/decr the reference count.  I've
never seen the code, so I just going on hunch here.

: The crucial issue in my mind is whether you can safely avoid counting
: pointers from the stack.

You and Henry (et al) are the wizzards here.  Do the stack based
references really cause most of the incr/decr operations?

: >Maybe my perspective is skewed because I have been RC'ing in Ada 9X.
: >I realize that C++ calls a copy constructor if you pass an object
: >as an argument by value.  But I was under the assumption that every
: >C++ RC'ing implementation worth its salt would require that the
: >reference objects are passed by reference (&).

: This no doubt helps, but isn't without cost.  At the implementation
: level, instead of passing a pointer to a heap location and adjusting the
: reference count, you're passing a pointer to a (stack allocated) indirect
: location which points to the heap.  You're likely to introduce
: additional memory references in accessing the result, and you may force
: the actual parameter into memory, out of a register.

Interesting question.  I'll have to check with my neighborhood Ada 9X
compiler implementor to find out what parameters qualify for register
passing.

: It also doesn't help with local variables that are updated.

Updating local (stack) variables doesn't modify the object graph,
but doesn't it change to roots?  Don't non-conservative GC'tion
mechanisms have to update some root symbol list?

: >The other trick about RC'ing is that you don't have to keep the
: >counts in the objects, you can keep them all in the same data
: >structure so that you pages are unnecessarily dirtied.

: Yes, but that isn't free either.

You're right.  You have to make a speed or space choice.  Either you
add a second pointer to the pointer object for the reference count
(fast, doubles pointer object size) or you add data to the object
that points to the reference count (indirect reference is slower,
causes page with object to be moved into memory, smaller pointer
object).

I like the first approach because the memory overhead of RCing in a
compiled langauge is so much less than what is required for GCing
anyway that the extra four or eight bytes per pointer doesn't seem
like much.

... Bill

------------------------------------------------------
e-mail: Bill.Beckwith@ois.com        |    Team Ada
Objective Interface Systems, Inc.    | dist, full O-O
1895 Preston White Drive, Suite 250  | multithreading
Reston, VA  22091-5448  U.S.A.       |    built in

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[R. William Beckwith]

R. William Beckwith (beckwb@ois.com) wrote:
: helps a little.  I would recommend using weak pointers for any object
		     wouldn't
: that doesn't have a strong pointer to it declared in the immediate

Darn those finfers

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Henry G. Baker]

In article <3bjfep$9ss@gamma.ois.com> beckwb@ois.com (R. William Beckwith) writes:
>Good point.  If you know you have other strong references to an
>object, you can use weak pointers for interators and such.  That
>helps a little.  I would recommend using weak pointers for any object
>that doesn't have a strong pointer to it declared in the immediate
>or enclosing scope.

(In case anyone else is following this thread)

Please note that your use of the term 'weak pointer' is nonstandard.
'Weak pointers' are used in tracing/coping GC's to refer to pointers
which aren't traced, but _are_ updated, possibly to NIL, by the
garbage collector.

A non-increment/decrement pointer in a reference counted system I
have called a 'deferred increment' pointers.  I have a recent paper
in Sigplan Notices (and my ftp/www archive) which investigates
this issue more thoroughly.

Henry Baker
Read (192.100.81.1) ftp.netcom.com:/pub/hb/hbaker/README for ftp-able papers.
WWW archive: ftp://ftp.netcom.com/pub/hb/hbaker/home.html
************* Note change of address ^^^        ^^^^

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[R. William Beckwith]

Henry G. Baker (hbaker@netcom.com) wrote:
: Please note that your use of the term 'weak pointer' is nonstandard.
: 'Weak pointers' are used in tracing/coping GC's to refer to pointers
: which aren't traced, but _are_ updated, possibly to NIL, by the
: garbage collector.

I learned the technique from the comments in the ParcPlace Object
class.  I have also referred to them as `non-sustaining' references.

: A non-increment/decrement pointer in a reference counted system I
: have called a 'deferred increment' pointers.  I have a recent paper
: in Sigplan Notices (and my ftp/www archive) which investigates
: this issue more thoroughly.

Ahh-hah.  I have been reading this paper and I was wondering exactly
what you meant by `deferred increment'.  Thanks for the clarification.

... Bill

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Hans Boehm]

beckwb@ois.com (R. William Beckwith) writes:

>Hans Boehm (boehm@parc.xerox.com) wrote:
>: You do need at least a write barrier on the heap for incremental collection.
>:...

>Hmmm.  The code that gets executed on processing the write barrier seems
>like it would take alot longer than incr/decr the reference count.  I've
>never seen the code, so I just going on hunch here.

The cost of the write barrier clearly depends on the algorithm.  But in
a number of cases all you need to do is to remember that a write to that
location occurred.  This may require a very small number of instructions
(I vaguely remember 4 or 5 from some talks on software write barriers)
or none (in the case of VM support).  Of course the cheaper implementations
may have other costs.

>: The crucial issue in my mind is whether you can safely avoid counting
>: pointers from the stack.

>You and Henry (et al) are the wizzards here.  Do the stack based
>references really cause most of the incr/decr operations?

The details obviously depend on the application.  But that's certainly
what I would expect for the vast majority of applications.  (I intended
to include register assignments with stack assignments.)  Heap assignments
tend to be rare in most code.  But things like list traversals are very
common, and usually involve many updates to a local variable.

Manual or compiler optimizations can significantly improve matters.
But those are generally risky or not possible with smart pointer
style implementations.

As was mentioned earlier, there are several fast RC implementations
(various older Xerox systems and DEC Modula-2+) that explicitly
avoided counting stack references and instead used a conservative
stack scan.

>: It also doesn't help with local variables that are updated.

>Updating local (stack) variables doesn't modify the object graph,
>but doesn't it change to roots?  Don't non-conservative GC'tion
>mechanisms have to update some root symbol list?

Maintaining an explicit list of stack resident roots is
expensive.  I would guess that most such schemes are comparable to
reference counting.  One alternative is to conservatively
scan the stack.  (This is done by many systems other than ours,
e.g. the above reference counted systems, SRC Modula-3, gcl or AKCL,
Bartlett's C++ and Scheme collectors, scm, and probably others.)
Another alternative is to generate stack frame descriptors, and
to have the collector walk the stack, mapping return addresses
to pointer locations.  This involves no overhead outside the collector,
but substantial compiler support.  A third alternative, commonly used in
dynamically typed languages, is to use some combination of a
register usage convention and tagged pointers.  That's probably
cheaper than explicit root lists, but has some overhead and some other
problems.

Hans-J. Boehm
(boehm@parc.xerox.com)
Standard disclaimer ...

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Henry G. Baker]

In article <3bo43b$61v@news.parc.xerox.com> boehm@parc.xerox.com (Hans Boehm) writes:
>beckwb@ois.com (R. William Beckwith) writes:
>>You and Henry (et al) are the wizzards here.  Do the stack based
>>references really cause most of the incr/decr operations?

References from the registers and the stack are the most volatile, and
therefore cause the most updating of reference counts.  This is by
definition, since it is impossible to change a reference count in any
other way.

>Maintaining an explicit list of stack resident roots is
>expensive.  I would guess that most such schemes are comparable to
>reference counting.  One alternative is to conservatively
>scan the stack.

The GC for my Ada83 Lisp implementation maintains an explicit list of
stack resident roots using a 'limited private' type.  See my ftp/www
page for how to get the Ada Letters paper which describes the stack
roots scheme.

-----

I just wanted to point out again that objects whose reference counts
are always one, and the programmer/compiler knows this, avoid the
usual overheads of reference counting.  For example, one cannot have
contention on such objects, and therefore locking isn't necessary, and
one need never _check_ the count on such an object when recycling,
since one already knows that it is =1, and therefore the object can
always be recycled immediately.  Such objects are called 'linear', and
there are several papers in my ftp/www directory that discuss them.

Henry Baker
Read (192.100.81.1) ftp.netcom.com:/pub/hb/hbaker/README for ftp-able papers.
WWW archive: ftp://ftp.netcom.com/pub/hb/hbaker/home.html
************* Note change of address ^^^        ^^^^
(It _is_ accessible, but Netcom is loaded; keep trying.)

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Bob Duff]

In article <hbakerD08qGF.4qM@netcom.com>,
Henry G. Baker <hbaker@netcom.com> wrote:
>I just wanted to point out again that objects whose reference counts
>are always one, and the programmer/compiler knows this, avoid the
>usual overheads of reference counting.

But it seems to me that in a language like Ada, if a given object only
has one reference pointing to it, and that fact is known at compile
time, then you would almost always declare that object as a normal
stack-allocated object.  So it would not be in the heap in the first
place, so reference counting would never occur.

In other words, the optimization you mention seems useful in a language
like Lisp, where everything's a pointer, but it seems irrelevant to Ada.
Or, to put it differently, Ada compiler's already do this optimization
-- the way you invoke it is to use an object instead of a
pointer-to-object.

- Bob

P.S. I've read quite a few of Henry's papers.  They really are quite
entertaining (especially the titles) and informative.
-- 
Bob Duff                                bobduff@inmet.com
Oak Tree Software, Inc.
Ada 9X Mapping/Revision Team (Intermetrics, Inc.)

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Gary McKee]

In Article <D0KDGE.31F@inmet.camb.inmet.com>, bobduff@dsd.camb.inmet.com
(Bob Duff) wrote:
>In article <hbakerD08qGF.4qM@netcom.com>,
>Henry G. Baker <hbaker@netcom.com> wrote:
>>I just wanted to point out again that objects whose reference counts
>>are always one, and the programmer/compiler knows this, avoid the
>>usual overheads of reference counting.
>
>But it seems to me that in a language like Ada, if a given object only
>has one reference pointing to it, and that fact is known at compile
>time, then you would almost always declare that object as a normal
>stack-allocated object.  So it would not be in the heap in the first
>place, so reference counting would never occur.
================================================================
Bob,

One counter-example would be the situation with compilers that limit the
size of the stack space but not the size of the heap. 

I have placed large, static arrays with predefined values onto the heap in
order to leave the stack space for subprogram usage (especially recursive
subprograms).

Gary McKee
--------------------------------------------------------------------
McKee Consulting                        (303) 795-7287
P. O. Box 3009                          gmckee@cloudnine.com
Littleton, CO 80161-3009                
--------------------------------------------------------------------

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Henry G. Baker]

In article <gmckee.1137578003A@news-2.csn.net> gmckee@cloudnine.com (Gary McKee) writes:
>In Article <D0KDGE.31F@inmet.camb.inmet.com>, bobduff@dsd.camb.inmet.com
>(Bob Duff) wrote:
>>In article <hbakerD08qGF.4qM@netcom.com>,
>>Henry G. Baker <hbaker@netcom.com> wrote:
>>>I just wanted to point out again that objects whose reference counts
>>>are always one, and the programmer/compiler knows this, avoid the
>>>usual overheads of reference counting.
>>
>>But it seems to me that in a language like Ada, if a given object only
>>has one reference pointing to it, and that fact is known at compile
>>time, then you would almost always declare that object as a normal
>>stack-allocated object.  So it would not be in the heap in the first
>>place, so reference counting would never occur.
>================================================================
>One counter-example would be the situation with compilers that limit the
>size of the stack space but not the size of the heap. 
>
>I have placed large, static arrays with predefined values onto the heap in
>order to leave the stack space for subprogram usage (especially recursive
>subprograms).

Another common example is a function that returns an object of
arbitrary size.  You don't know how much space to allocate for it
on the stack, and if you simply redefine the stack frame to include
the object (which was stack-allocated by the called function), then
you may waste huge amounts of space on the stack.  So you're better
off allocating it in a heap, but remembering that you have only
one pointer to it.

Henry Baker
Read (192.100.81.1) ftp.netcom.com:/pub/hb/hbaker/README for ftp-able papers.
WWW archive: ftp://ftp.netcom.com/pub/hb/hbaker/home.html
************* Note change of address ^^^        ^^^^
(It _is_ accessible, but Netcom is loaded; keep trying.)

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[R. William Beckwith]

Henry G. Baker (hbaker@netcom.com) wrote:

: Another common example is a function that returns an object of
: arbitrary size.  You don't know how much space to allocate for it
: on the stack, and if you simply redefine the stack frame to include
: the object (which was stack-allocated by the called function), then
: you may waste huge amounts of space on the stack.  So you're better
: off allocating it in a heap, but remembering that you have only
: one pointer to it.

I thought most Ada compilers returned unconstrained objects on
a secondary stack.  True?  I guess the secondary stack might
be heap based, but this would preclude limitless size unlike
the primary stack.  Hmmm.

... Bill

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Bob Duff]

In article <hbakerD0oM3E.7s3@netcom.com>,
Henry G. Baker <hbaker@netcom.com> wrote:
>Another common example is a function that returns an object of
>arbitrary size.  You don't know how much space to allocate for it
>on the stack, and if you simply redefine the stack frame to include
>the object (which was stack-allocated by the called function), then
>you may waste huge amounts of space on the stack.  So you're better
>off allocating it in a heap, but remembering that you have only
>one pointer to it.

Some Ada compilers allocate those things on the heap.  However, others
(most, I believe) allocate those things on the stack.  When the function
returns, the result object is copied from wherever it is down to where
it belongs.  There are numerous complicated optimizations that can be
done to avoid the copying in many cases.  Some compilers use the normal
run-time stack, whereas others have a secondary stack for these kinds of
things, but either way, the principle is the same.

- Bob
-- 
Bob Duff                                bobduff@inmet.com
Oak Tree Software, Inc.
Ada 9X Mapping/Revision Team (Intermetrics, Inc.)

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Robert Dewar]

Bob says that most compilers return variable length objects on the stack. 
THat's a little misleading. What some compilers do is to return them on
a secondary stack. It is a little tricky to return them on the primary
stack, it requires a specialized calling sequence (similar to what alloca
has to use), and in many ABI's, you can't do this without violating the
standard calling sequence.

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Henry G. Baker]

In article <D0x53v.FxE@inmet.camb.inmet.com> bobduff@dsd.camb.inmet.com (Bob Duff) writes:
>In article <hbakerD0oM3E.7s3@netcom.com>,
>Henry G. Baker <hbaker@netcom.com> wrote:
>>Another common example is a function that returns an object of
>>arbitrary size.  You don't know how much space to allocate for it
>>on the stack, and if you simply redefine the stack frame to include
>>the object (which was stack-allocated by the called function), then
>>you may waste huge amounts of space on the stack.  So you're better
>>off allocating it in a heap, but remembering that you have only
>>one pointer to it.
>
>Some Ada compilers allocate those things on the heap.  However, others
>(most, I believe) allocate those things on the stack.  When the function
>returns, the result object is copied from wherever it is down to where
>it belongs.  There are numerous complicated optimizations that can be
>done to avoid the copying in many cases.  Some compilers use the normal
>run-time stack, whereas others have a secondary stack for these kinds of
>things, but either way, the principle is the same.

(There must be some sort of an echo in these newsgroups.  We keep
posting the same information over and over again.  I'll try again.)

I'm aware of the usual schemes for allocating objects on the stack and
the heap.  Below are some papers that cover some of these issues, and
reference many other papers on the same subject.

"Structured Programming with Limited Private Types in Ada".  ACM Ada
Letters and ftp://ftp.netcom.com/pub/hb/hbaker/LPprogram.ps.Z.

"CONS Should not CONS its Arguments".  ACM Sigplan Notices and
ftp://ftp.netcom.com/pub/hb/hbaker/LazyAlloc.ps.Z.

Stack allocation of arbitrary-sized objects is too inflexible and/or
too inefficient (due to excess copying) for many uses in a
multi-threaded environment where processes pass objects among
themselves -- precisely the environment the Ada implementor finds
himself.  Unfortunately, heap allocation from a global heap has its
own set of problems in this environment -- e.g., the need to
constantly check and set locks, which becomes a major problem in its
own right.

It is in environments like these that 'linear' objects are most
useful.  (Linear objects are essentially the same as those in
NIL/Hermes.)  Linear objects never need locks and don't have to be
copied.  (More precisely, you can copy them if you want, but you don't
have to worry about leaving a forwarding address, because there's only
one pointer to the object, so no one is in a position to know that it
has been moved!)

See "'Use-Once' Variables and Linear Objects--Storage Management,
Reflection and Multi-Threading".  Siglan Notices, to appear.  Also,
ftp://ftp.netcom.com/pub/hb/hbaker/Use1Var.ps.Z.

This paper references a number of other papers that are also available
on the network.

Henry Baker
Read (192.100.81.1) ftp.netcom.com:/pub/hb/hbaker/README for ftp-able papers.
WWW archive: ftp://ftp.netcom.com/pub/hb/hbaker/home.html
************* Note change of address ^^^        ^^^^
(It _is_ accessible, but Netcom is loaded; keep trying.)

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Robb Nebbe]

In article <D0KDGE.31F@inmet.camb.inmet.com>, bobduff@dsd.camb.inmet.com (Bob Duff) writes:
|> 
|> But it seems to me that in a language like Ada, if a given object only
|> has one reference pointing to it, and that fact is known at compile
|> time, then you would almost always declare that object as a normal
|> stack-allocated object.  So it would not be in the heap in the first
|> place, so reference counting would never occur.
|> 

A lot of this time this is correct but there are many cases where
the lifetime of an object doesn't mesh with the concept of scope.
If the birth and death of an object are tied to external events
completely outside the control of the program then stack allocation
won't work.

Robb Nebbe

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Henry G. Baker]

In article <D0KDGE.31F@inmet.camb.inmet.com> bobduff@dsd.camb.inmet.com (Bob Duff) writes:
>In article <hbakerD08qGF.4qM@netcom.com>,
>Henry G. Baker <hbaker@netcom.com> wrote:
>>I just wanted to point out again that objects whose reference counts
>>are always one, and the programmer/compiler knows this, avoid the
>>usual overheads of reference counting.
>
>But it seems to me that in a language like Ada, if a given object only
>has one reference pointing to it, and that fact is known at compile
>time, then you would almost always declare that object as a normal
>stack-allocated object.  So it would not be in the heap in the first
>place, so reference counting would never occur.
>
>In other words, the optimization you mention seems useful in a language
>like Lisp, where everything's a pointer, but it seems irrelevant to Ada.
>Or, to put it differently, Ada compiler's already do this optimization
>-- the way you invoke it is to use an object instead of a
>pointer-to-object.

This optimization is quite useful in Ada -- perhaps more useful than
in Lisp because of the existence of multiple threads/tasks.  Whereas
stack-allocated objects are constrained by LIFO behavior, the objects
I describe have no such constraints.  Secondly, and probably much more
important in Ada, is the fact that an object whose reference count is
exactly one can be referenced by only one task/thread, and therefore
need _not_ be protected by a semaphore or protected record.

Therefore, these objects are ideal objects to be sent in messages
from one task/thread to another.

(I didn't come up with this stuff, but I highly recommend it.  The
"NIL" and "Hermes" languages for distributed computations out of IBM
Yorktown deal nearly exclusively with singly-referenced objects of
this sort.)

Henry Baker
Read (192.100.81.1) ftp.netcom.com:/pub/hb/hbaker/README for ftp-able papers.
WWW archive: ftp://ftp.netcom.com/pub/hb/hbaker/home.html
************* Note change of address ^^^        ^^^^
(It _is_ accessible, but Netcom is loaded; keep trying.)

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Kevin Warne]

In article <3bii2g$kn2@news.parc.xerox.com>, boehm@parc.xerox.com (Hans Boehm) says:
>beckwb@ois.com (R. William Beckwith) writes:
>>Paul Wilson's RT, generational, incremental GC'tor causes work
>>when the graph of objects is changed (write barrier).  Surely,
>>the color changes required with a graph change can be as fast
>>as a simple incr/decr operation.
>
>You do need at least a write barrier on the heap for incremental collection.
>(In the best case, the dirty bits in the MMU are a sufficient
>write barrier, though not for that algorithm.  But using them is likely

Can you think of a realistic incremental collection algorithm 
that uses MMU dirty bits?  At best I suppose a collector could perform
a collection and then freeze the application while it rescanned
pointers in areas covered by dirty bits.

>to increase collector latency, though probably not above the simple RC scheme.
>And your machine may not have hardware dirty bits, though the Intel
>architecture does.  And your OS may already need those bits for other
>things, adding a bit of overhead.)

And don't forget all those OSs who keep the dirty bits to themselves.
Just imagine the hell involved to access those bits under the likes
of Windows NT and OS/2 (and other operating systems).

Still, it would turn card-marking into a win, wouldn't it...

>The crucial issue in my mind is whether you can safely avoid counting
>pointers from the stack.

Any incremental collector (RC or tracing) is going to need a stack
barrier unless either A) stacks are scanned atomically at the end of a 
collection period along with the objects that they reference or B) 
stack objects have restrictions during collection about what kind of
heap objects they may point to.  Otherwise stack-based references can 
circumvent heap barriers.

Kevin

____
Kevin Warne / kevinw@whistler.com / DDD +1 604 932 0606 / FAX +1 604 598 9546
Suite 204, 1200 Alpha Lake Road, Whistler, BC, CANADA  V0N 1B0
Warne's Garbage Collector (WGC) = The best way to allocate memory in C++

Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection)

[Hans Boehm]

kevinw@whistler.com (Kevin Warne) writes:

>In article <3bii2g$kn2@news.parc.xerox.com>, boehm@parc.xerox.com (Hans Boehm) says:
>>You do need at least a write barrier on the heap for incremental collection.
>>(In the best case, the dirty bits in the MMU are a sufficient
>>write barrier, though not for that algorithm.  But using them is likely

>Can you think of a realistic incremental collection algorithm 
>that uses MMU dirty bits?  At best I suppose a collector could perform
>a collection and then freeze the application while it rescanned
>pointers in areas covered by dirty bits.

Ours :-).  You essentially just described the algorithm.  The rescanning
takes some work, but that's typically on the order of 10% of the work
required by a full mark phase.  It also has the big advantage that with
probability nearly one, this mark phase can look only at pages that were
recently modified, and hence are nearly certain to be in physical
memory.  There are some measurements of this scheme in the 1991 SIGPLAN
PLDI paper by Alan Demers, Scott Shenker, and myself.

I would argue that on modern workstation/PC processors this is almost
always good enough for interactive (100msec) response.  With good
OS support, it's probably barely adequate for animation on a fast machine.
If you have stronger real-time requirements, you need dirty information
with better granularity than 4K pages.

>And don't forget all those OSs who keep the dirty bits to themselves.
>Just imagine the hell involved to access those bits under the likes
>of Windows NT and OS/2 (and other operating systems).

The OS vendors haven't let me forget, unfortunately.  Actually
I'm told that it's possible to fake dirty bits under NT by write-
protecting pages and catching faults.  But the NT exception model
makes that a bit clumsy, and I haven't implemented it.  (This is
actually the strategy we currently use under SunOS4.X, Irix, and OSF/1.
Solaris 2.X supports direct retrieval of kernel maintained dirty bits,
though the current implementation is slower than it should be.)

>>The crucial issue in my mind is whether you can safely avoid counting
>>pointers from the stack.

>Any incremental collector (RC or tracing) is going to need a stack
>barrier unless either A) stacks are scanned atomically at the end of a 
>collection period along with the objects that they reference or B) 
>stack objects have restrictions during collection about what kind of
>heap objects they may point to.  Otherwise stack-based references can 
>circumvent heap barriers.

Agreed.  But scanning the stack(s) atomically at the end shouldn't
be a big deal for most applications.  If you need better than 10msec
response time, then it's a problem and you have to pay for the stack
barrier.  (You can also use MMU dirty bits on the stack, though the
write protect/trap emulation of dirty bits has problems in this context.)

Note that simple RC algorithms are also unlikely to give you
10 msec response.  I suspect that many applications often drop 10K objects
at once.

Hans-J. Boehm
(boehm@parc.xerox.com)
Standard disclaimer ...