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

[hbaker@netcom.com (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.)