* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) [not found] ` <3bfprn$okr@scipio.cyberstore.ca> @ 1994-11-29 21:27 ` R. William Beckwith 1994-11-30 2:27 ` Henry G. Baker ` (2 more replies) 0 siblings, 3 replies; 41+ messages in thread From: R. William Beckwith @ 1994-11-29 21:27 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-11-29 21:27 ` Reference Counting (was Re: Searching Method for Incremental Garbage Collection) R. William Beckwith @ 1994-11-30 2:27 ` Henry G. Baker 1994-11-30 18:59 ` Hans Boehm [not found] ` <DAG.94Nov30090717@bellman.control.lth.se> 2 siblings, 0 replies; 41+ messages in thread From: Henry G. Baker @ 1994-11-30 2:27 UTC (permalink / raw) 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 ^^^ ^^^^ ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-11-29 21:27 ` Reference Counting (was Re: Searching Method for Incremental Garbage Collection) R. William Beckwith 1994-11-30 2:27 ` Henry G. Baker @ 1994-11-30 18:59 ` Hans Boehm 1994-12-01 3:20 ` R. William Beckwith [not found] ` <DAG.94Nov30090717@bellman.control.lth.se> 2 siblings, 1 reply; 41+ messages in thread From: Hans Boehm @ 1994-11-30 18:59 UTC (permalink / raw) 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 ... ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-11-30 18:59 ` Hans Boehm @ 1994-12-01 3:20 ` R. William Beckwith 1994-12-01 3:51 ` R. William Beckwith ` (2 more replies) 0 siblings, 3 replies; 41+ messages in thread From: R. William Beckwith @ 1994-12-01 3:20 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-01 3:20 ` R. William Beckwith @ 1994-12-01 3:51 ` R. William Beckwith 1994-12-01 13:59 ` Henry G. Baker 1994-12-02 21:37 ` Hans Boehm 2 siblings, 0 replies; 41+ messages in thread From: R. William Beckwith @ 1994-12-01 3:51 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-01 3:20 ` R. William Beckwith 1994-12-01 3:51 ` R. William Beckwith @ 1994-12-01 13:59 ` Henry G. Baker 1994-12-02 4:26 ` R. William Beckwith 1994-12-02 21:37 ` Hans Boehm 2 siblings, 1 reply; 41+ messages in thread From: Henry G. Baker @ 1994-12-01 13:59 UTC (permalink / raw) 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 ^^^ ^^^^ ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-01 13:59 ` Henry G. Baker @ 1994-12-02 4:26 ` R. William Beckwith 0 siblings, 0 replies; 41+ messages in thread From: R. William Beckwith @ 1994-12-02 4:26 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-01 3:20 ` R. William Beckwith 1994-12-01 3:51 ` R. William Beckwith 1994-12-01 13:59 ` Henry G. Baker @ 1994-12-02 21:37 ` Hans Boehm 1994-12-03 15:17 ` Henry G. Baker 2 siblings, 1 reply; 41+ messages in thread From: Hans Boehm @ 1994-12-02 21:37 UTC (permalink / raw) 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 ... ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-02 21:37 ` Hans Boehm @ 1994-12-03 15:17 ` Henry G. Baker 1994-12-09 22:07 ` Bob Duff 0 siblings, 1 reply; 41+ messages in thread From: Henry G. Baker @ 1994-12-03 15:17 UTC (permalink / raw) 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.) ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-03 15:17 ` Henry G. Baker @ 1994-12-09 22:07 ` Bob Duff 1994-12-11 23:59 ` Gary McKee ` (2 more replies) 0 siblings, 3 replies; 41+ messages in thread From: Bob Duff @ 1994-12-09 22:07 UTC (permalink / raw) 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.) ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-09 22:07 ` Bob Duff @ 1994-12-11 23:59 ` Gary McKee 1994-12-12 5:04 ` Henry G. Baker 1994-12-12 9:36 ` Robb Nebbe 1994-12-13 16:12 ` Henry G. Baker 2 siblings, 1 reply; 41+ messages in thread From: Gary McKee @ 1994-12-11 23:59 UTC (permalink / raw) 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 -------------------------------------------------------------------- ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-11 23:59 ` Gary McKee @ 1994-12-12 5:04 ` Henry G. Baker 1994-12-12 12:46 ` R. William Beckwith 1994-12-16 19:35 ` Bob Duff 0 siblings, 2 replies; 41+ messages in thread From: Henry G. Baker @ 1994-12-12 5:04 UTC (permalink / raw) 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.) ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-12 5:04 ` Henry G. Baker @ 1994-12-12 12:46 ` R. William Beckwith 1994-12-16 19:35 ` Bob Duff 1 sibling, 0 replies; 41+ messages in thread From: R. William Beckwith @ 1994-12-12 12:46 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-12 5:04 ` Henry G. Baker 1994-12-12 12:46 ` R. William Beckwith @ 1994-12-16 19:35 ` Bob Duff 1994-12-17 20:36 ` Robert Dewar 1994-12-20 5:24 ` Henry G. Baker 1 sibling, 2 replies; 41+ messages in thread From: Bob Duff @ 1994-12-16 19:35 UTC (permalink / raw) 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.) ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-16 19:35 ` Bob Duff @ 1994-12-17 20:36 ` Robert Dewar 1994-12-20 5:24 ` Henry G. Baker 1 sibling, 0 replies; 41+ messages in thread From: Robert Dewar @ 1994-12-17 20:36 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-16 19:35 ` Bob Duff 1994-12-17 20:36 ` Robert Dewar @ 1994-12-20 5:24 ` Henry G. Baker 1 sibling, 0 replies; 41+ messages in thread From: Henry G. Baker @ 1994-12-20 5:24 UTC (permalink / raw) 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.) ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-09 22:07 ` Bob Duff 1994-12-11 23:59 ` Gary McKee @ 1994-12-12 9:36 ` Robb Nebbe 1994-12-13 16:12 ` Henry G. Baker 2 siblings, 0 replies; 41+ messages in thread From: Robb Nebbe @ 1994-12-12 9:36 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-09 22:07 ` Bob Duff 1994-12-11 23:59 ` Gary McKee 1994-12-12 9:36 ` Robb Nebbe @ 1994-12-13 16:12 ` Henry G. Baker 2 siblings, 0 replies; 41+ messages in thread From: Henry G. Baker @ 1994-12-13 16:12 UTC (permalink / raw) 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.) ^ permalink raw reply [flat|nested] 41+ messages in thread
[parent not found: <DAG.94Nov30090717@bellman.control.lth.se>]
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) [not found] ` <DAG.94Nov30090717@bellman.control.lth.se> @ 1994-11-30 16:39 ` David Weller 1994-11-30 17:58 ` Erik Naggum 1994-12-02 23:41 ` Reference Counting (was Re: Searching Method for Incremental Garbage Collection) Bob Duff 1 sibling, 1 reply; 41+ messages in thread From: David Weller @ 1994-11-30 16:39 UTC (permalink / raw) 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 | ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-11-30 16:39 ` David Weller @ 1994-11-30 17:58 ` Erik Naggum 1994-11-30 23:14 ` Michael Feldman 1994-12-09 14:19 ` Ada 95 is the name Tucker Taft 0 siblings, 2 replies; 41+ messages in thread From: Erik Naggum @ 1994-11-30 17:58 UTC (permalink / raw) [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. ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-11-30 17:58 ` Erik Naggum @ 1994-11-30 23:14 ` Michael Feldman 1994-12-09 14:19 ` Ada 95 is the name Tucker Taft 1 sibling, 0 replies; 41+ messages in thread From: Michael Feldman @ 1994-11-30 23:14 UTC (permalink / raw) 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.) ------------------------------------------------------------------------ ^ permalink raw reply [flat|nested] 41+ messages in thread
* Ada 95 is the name 1994-11-30 17:58 ` Erik Naggum 1994-11-30 23:14 ` Michael Feldman @ 1994-12-09 14:19 ` Tucker Taft 1994-12-09 22:33 ` Pat Rogers 1994-12-10 10:10 ` Marc Wachowitz 1 sibling, 2 replies; 41+ messages in thread From: Tucker Taft @ 1994-12-09 14:19 UTC (permalink / raw) 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? Yes and no ;-). ISO has the camera-ready copy (as of Dec. 1), and has approved it for publication, but because of their own administrative procedures, prefers to makes its publication date Jan. 1, 1995 rather than Dec. 30, 1994. So we might as well get used to calling it Ada '95. After the fact, it is easy to see whay Ada '95 is preferable to Ada '94. Imagine the year is now 1996. Clearly Ada '95 will sound more modern than Ada '94. So we really have the best of both worlds -- we have a standard that is finalized in 1994, but with a date that will make it sound a year more modern from now on... > if so, congratulations! Congratulations accepted anyway! Bob Duff of the Ada 9X Mapping/Revision Team and Bob Mathis of WG9 and ARA fame (someday? ;-) deserve the credit for the last minute efforts. >#<Erik> S. Tucker Taft stt@inmet.com Ada 9X Mapping/Revision Team. Intermetrics, Inc. Cambridge, MA 02138 ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Ada 95 is the name 1994-12-09 14:19 ` Ada 95 is the name Tucker Taft @ 1994-12-09 22:33 ` Pat Rogers 1994-12-11 18:59 ` Jean D. Ichbiah 1994-12-10 10:10 ` Marc Wachowitz 1 sibling, 1 reply; 41+ messages in thread From: Pat Rogers @ 1994-12-09 22:33 UTC (permalink / raw) In article <D0JrtA.1sL@inmet.camb.inmet.com> stt@dsd.camb.inmet.com (Tucker Taft) writes: >ISO has the camera-ready copy (as of Dec. 1), and has approved it >for publication, but because of their own administrative procedures, >prefers to makes its publication date Jan. 1, 1995 rather than >Dec. 30, 1994. So we might as well get used to calling it Ada '95. > Out of curiosity more than anything else, won't it just be called "Ada"? Then, when wanting to refer to what used to be Ada, we'll say Ada83/7 ... pat -- Pat Rogers, Team Ada progers@ajpo.sei.cmu.edu ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Ada 95 is the name 1994-12-09 22:33 ` Pat Rogers @ 1994-12-11 18:59 ` Jean D. Ichbiah 1994-12-11 20:05 ` Pat Rogers 1994-12-12 14:50 ` Garlington KE 0 siblings, 2 replies; 41+ messages in thread From: Jean D. Ichbiah @ 1994-12-11 18:59 UTC (permalink / raw) progers@ajpo.sei.cmu.edu (Pat Rogers) writes: >Out of curiosity more than anything else, won't it just be called "Ada"? >Then, when wanting to refer to what used to be Ada, we'll say Ada83/7 ... >pat There is no such thing as "Ada83/7": I wrote the manual and you can read it : The language published in 1983 is called "Ada". And now, as you read, the new language is called "Ada 95". Jean D. Ichbiah ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Ada 95 is the name 1994-12-11 18:59 ` Jean D. Ichbiah @ 1994-12-11 20:05 ` Pat Rogers 1994-12-16 1:01 ` Bob Duff 1994-12-12 14:50 ` Garlington KE 1 sibling, 1 reply; 41+ messages in thread From: Pat Rogers @ 1994-12-11 20:05 UTC (permalink / raw) In article <ichbiah.81.2EEB4C2F@jdi.tiac.net> ichbiah@jdi.tiac.net (Jean D. Ichbiah) writes: > progers@ajpo.sei.cmu.edu (Pat Rogers) writes: > >>Out of curiosity more than anything else, won't it just be called "Ada"? >>Then, when wanting to refer to what used to be Ada, we'll say Ada83/7 ... > >>pat > > There is no such thing as "Ada83/7": I wrote the manual and you can > read it : The language published in 1983 is called "Ada". And now, Oh. Thank you. Perhaps I should get around to reading that. I did read the Rationale, though. I especially liked your tasking-based disk head scheduler as an example of real-time programming. >as you read, the new language is called "Ada 95". Tucker's post didn't have the quotes around it. I'm still wondering if that is literally (no pun intended, honest) the new name. > > >Jean D. Ichbiah > Ah, the fond memories this brings back... -- Pat Rogers, Team Ada progers@ajpo.sei.cmu.edu ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Ada 95 is the name 1994-12-11 20:05 ` Pat Rogers @ 1994-12-16 1:01 ` Bob Duff 0 siblings, 0 replies; 41+ messages in thread From: Bob Duff @ 1994-12-16 1:01 UTC (permalink / raw) In article <1994Dec11.150548.1947@sei.cmu.edu>, Pat Rogers <progers@ajpo.sei.cmu.edu> wrote: >Tucker's post didn't have the quotes around it. I'm still wondering if >that is literally (no pun intended, honest) the new name. The new language and the old language are both, in official ISO/IEC terms, called "Ada". In the next few years, we'll call them "Ada 83" and "Ada 95", to distinguish the versions. Eventually, when everybody's converted over, I suspect we'll call the Ada 95 version, just "Ada". The same thing has happened with Fortan and lots of other languages that have been revised over the years. Does "Fortran" refer to "Fortran 66" or "Fortran II" nowadays? - Bob -- Bob Duff bobduff@inmet.com Oak Tree Software, Inc. Ada 9X Mapping/Revision Team (Intermetrics, Inc.) ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Ada 95 is the name 1994-12-11 18:59 ` Jean D. Ichbiah 1994-12-11 20:05 ` Pat Rogers @ 1994-12-12 14:50 ` Garlington KE 1994-12-13 21:48 ` Tucker Taft ` (2 more replies) 1 sibling, 3 replies; 41+ messages in thread From: Garlington KE @ 1994-12-12 14:50 UTC (permalink / raw) Jean D. Ichbiah (ichbiah@jdi.tiac.net) wrote: : There is no such thing as "Ada83/7": I wrote the manual and you can : read it : The language published in 1983 is called "Ada". And now, : as you read, the new language is called "Ada 95". I've been curious about this, too. My copy of the draft Ada 95 manual just says "Programming Language Ada" on the title page. The Foreword (at least in draft 5.0) says, "ISO/IEC 8652 defines the Ada programming language, a general-purpose language designed to support the construction of long-lived, highly reliable software systems. This International Standard replaces the previous version of 1987." If this is so, shouldn't Ada mean The Latest Ada (at least as of 1995), and Ada 95 and Ada 87 be the preferred form when referring to the current version and the previous version in the same context? -------------------------------------------------------------------- Ken Garlington GarlingtonKE@lfwc.lockheed.com F-22 Computer Resources Lockheed Fort Worth Co. If LFWC or the F-22 program has any opinions, they aren't telling me. ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Ada 95 is the name 1994-12-12 14:50 ` Garlington KE @ 1994-12-13 21:48 ` Tucker Taft 1994-12-14 12:44 ` Gentle 1994-12-14 17:34 ` Jean D. Ichbiah 2 siblings, 0 replies; 41+ messages in thread From: Tucker Taft @ 1994-12-13 21:48 UTC (permalink / raw) In article <3cho0b$k4f@cliffy.lfwc.lockheed.com>, Garlington KE <l107353@cliffy.lfwc.lockheed.com> wrote: >Jean D. Ichbiah (ichbiah@jdi.tiac.net) wrote: > >: There is no such thing as "Ada83/7": I wrote the manual and you can >: read it : The language published in 1983 is called "Ada". And now, >: as you read, the new language is called "Ada 95". > >I've been curious about this, too. My copy of the draft Ada 95 manual just says >"Programming Language Ada" on the title page. The Foreword (at least in >draft 5.0) says, "ISO/IEC 8652 defines the Ada programming language, a >general-purpose language designed to support the construction of long-lived, >highly reliable software systems. This International Standard replaces the >previous version of 1987." > >If this is so, shouldn't Ada mean The Latest Ada (at least as of 1995), and >Ada 95 and Ada 87 be the preferred form when referring to the current version >and the previous version in the same context? Yes, "Ada" by itself will eventually come to mean the latest Ada. But most available "Ada" compilers today handle Ada 83/87, so it might be confusing to start to presume "Ada" meant Ada 95. Better to be explicit until we are all using the latest version. Note that sometimes a new language standard does not replace the old one. However, in the case of Ada, the new ISO standard replaces the old one, and similarly for ANSI. I believe that at least for a while (perhaps still), "Fortran" meant Fortran 77 and "Fortran 90" was considered a distinct standard (perhaps only by ANSI?). >Ken Garlington GarlingtonKE@lfwc.lockheed.com >F-22 Computer Resources Lockheed Fort Worth Co. -Tucker Taft stt@inmet.com Intermetrics, Inc. ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Ada 95 is the name 1994-12-12 14:50 ` Garlington KE 1994-12-13 21:48 ` Tucker Taft @ 1994-12-14 12:44 ` Gentle 1994-12-14 17:34 ` Jean D. Ichbiah 2 siblings, 0 replies; 41+ messages in thread From: Gentle @ 1994-12-14 12:44 UTC (permalink / raw) On 12 Dec 1994 14:50:51 GMT, Garlington KE (l107353@cliffy.lfwc.lockheed.com) wrote: : If this is so, shouldn't Ada mean The Latest Ada (at least as of 1995), and : Ada 95 and Ada 87 be the preferred form when referring to the current version : and the previous version in the same context? Pretty much. Just look at other software: Windows 3.0, Windows 3.1, then Windows Chicago, which is technically known as Windows 4.0. -- ========================================================================= gentle@cnj.digex.net Software Engineer (extraordinaire!) Level: International Hacker Edison, NJ "If you can count your money, you don't have a billion dollars." -- J. Paul Getty ========================================================================= ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Ada 95 is the name 1994-12-12 14:50 ` Garlington KE 1994-12-13 21:48 ` Tucker Taft 1994-12-14 12:44 ` Gentle @ 1994-12-14 17:34 ` Jean D. Ichbiah 2 siblings, 0 replies; 41+ messages in thread From: Jean D. Ichbiah @ 1994-12-14 17:34 UTC (permalink / raw) In article <3cho0b$k4f@cliffy.lfwc.lockheed.com> l107353@cliffy.lfwc.lockheed.com (Garlington KE) writes: >If this is so, shouldn't Ada mean The Latest Ada (at least as of 1995), and >Ada 95 and Ada 87 be the preferred form when referring to the current version >and the previous version in the same context? Now that the Soviet Union has ceased to exist, we have noticed a significant decrease in the practice of rewriting history. But, well, perhaps it could be tried again. Jean D. Ichbiah ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Ada 95 is the name 1994-12-09 14:19 ` Ada 95 is the name Tucker Taft 1994-12-09 22:33 ` Pat Rogers @ 1994-12-10 10:10 ` Marc Wachowitz 1994-12-11 21:37 ` Bob Duff 1 sibling, 1 reply; 41+ messages in thread From: Marc Wachowitz @ 1994-12-10 10:10 UTC (permalink / raw) Tucker Taft (stt@dsd.camb.inmet.com) wrote: > ISO has the camera-ready copy (as of Dec. 1), and has approved it Is that the same version (by content - I'm not asking about layout etc.) as the files currently available on the ajpo ftp server? I wouldn't like to print another intermediate copy, but save the paper for the last one. ------------------------------------------------------------------------------ * wonder everyday * nothing in particular * all is special * Marc Wachowitz <mw@ipx2.rz.uni-mannheim.de> ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Ada 95 is the name 1994-12-10 10:10 ` Marc Wachowitz @ 1994-12-11 21:37 ` Bob Duff 0 siblings, 0 replies; 41+ messages in thread From: Bob Duff @ 1994-12-11 21:37 UTC (permalink / raw) In article <3cbuqq$m1n@darum.uni-mannheim.de>, Marc Wachowitz <mw@ipx2.rz.uni-mannheim.de> wrote: >Tucker Taft (stt@dsd.camb.inmet.com) wrote: >> ISO has the camera-ready copy (as of Dec. 1), and has approved it > >Is that the same version (by content - I'm not asking about layout etc.) >as the files currently available on the ajpo ftp server? Version 5.95 is available on the ajpo server. It is the same text (except for formatting issues) as what was sent to ISO. However, ISO is making some minor changes (e.g. some wording changes in the "Instructions for Comment" section). There will eventually be a version 6.0 that matches the ISO version (again, except for formatting issues). I can't promise when 6.0 will be out -- probably at least a few more weeks. But if you print out 5.95, you won't be far wrong -- certainly we don't plan to make any *technical* changes to the RM at this point. (We might add a few things to the AARM annotations, though.) - Bob -- Bob Duff bobduff@inmet.com Oak Tree Software, Inc. Ada 9X Mapping/Revision Team (Intermetrics, Inc.) ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) [not found] ` <DAG.94Nov30090717@bellman.control.lth.se> 1994-11-30 16:39 ` David Weller @ 1994-12-02 23:41 ` Bob Duff 1994-12-03 8:16 ` Bill Birch 1 sibling, 1 reply; 41+ messages in thread From: Bob Duff @ 1994-12-02 23:41 UTC (permalink / raw) 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.) ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-02 23:41 ` Reference Counting (was Re: Searching Method for Incremental Garbage Collection) Bob Duff @ 1994-12-03 8:16 ` Bill Birch 0 siblings, 0 replies; 41+ messages in thread From: Bill Birch @ 1994-12-03 8:16 UTC (permalink / raw) 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! {:-) ^ permalink raw reply [flat|nested] 41+ messages in thread
[parent not found: <3be0mh$1p7@ga <3bii2g$kn2@news.parc.xerox.com>]
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) [not found] ` <3be0mh$1p7@ga <3bii2g$kn2@news.parc.xerox.com> @ 1994-12-01 4:58 ` Kevin Warne 1994-12-02 21:58 ` Hans Boehm 0 siblings, 1 reply; 41+ messages in thread From: Kevin Warne @ 1994-12-01 4:58 UTC (permalink / raw) 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++ ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-01 4:58 ` Kevin Warne @ 1994-12-02 21:58 ` Hans Boehm 0 siblings, 0 replies; 41+ messages in thread From: Hans Boehm @ 1994-12-02 21:58 UTC (permalink / raw) 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 ... ^ permalink raw reply [flat|nested] 41+ messages in thread
[parent not found: <D06r8x.JBy@inmet.camb.inmet.com>]
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) [not found] <D06r8x.JBy@inmet.camb.inmet.com> @ 1994-12-02 17:32 ` Henry G. Baker 1994-12-05 20:59 ` Robert Firth 1994-12-04 1:06 ` Rick Busdiecker 1 sibling, 1 reply; 41+ messages in thread From: Henry G. Baker @ 1994-12-02 17:32 UTC (permalink / raw) 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 ^^^ ^^^^ ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-02 17:32 ` Henry G. Baker @ 1994-12-05 20:59 ` Robert Firth 1994-12-06 14:15 ` Robert Dewar 0 siblings, 1 reply; 41+ messages in thread From: Robert Firth @ 1994-12-05 20:59 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-05 20:59 ` Robert Firth @ 1994-12-06 14:15 ` Robert Dewar 0 siblings, 0 replies; 41+ messages in thread From: Robert Dewar @ 1994-12-06 14:15 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) [not found] <D06r8x.JBy@inmet.camb.inmet.com> 1994-12-02 17:32 ` Henry G. Baker @ 1994-12-04 1:06 ` Rick Busdiecker 1994-12-04 18:57 ` R. William Beckwith 1 sibling, 1 reply; 41+ messages in thread From: Rick Busdiecker @ 1994-12-04 1:06 UTC (permalink / raw) To: Mitch Gart 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 ^ permalink raw reply [flat|nested] 41+ messages in thread
* Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) 1994-12-04 1:06 ` Rick Busdiecker @ 1994-12-04 18:57 ` R. William Beckwith 0 siblings, 0 replies; 41+ messages in thread From: R. William Beckwith @ 1994-12-04 18:57 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 41+ messages in thread
end of thread, other threads:[~1994-12-20 5:24 UTC | newest] Thread overview: 41+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- [not found] <CzHCvp.9rM@rheged.dircon.co.uk> [not found] ` <TFB.94Nov21091959@burns.cogsci.ed.ac.uk> [not found] ` <RFB.94Nov27213114@cfdevx1.lehman.com> [not found] ` <3be0mh$1p7@gamma.ois.com> [not found] ` <3bfprn$okr@scipio.cyberstore.ca> 1994-11-29 21:27 ` Reference Counting (was Re: Searching Method for Incremental Garbage Collection) R. William Beckwith 1994-11-30 2:27 ` Henry G. Baker 1994-11-30 18:59 ` Hans Boehm 1994-12-01 3:20 ` R. William Beckwith 1994-12-01 3:51 ` R. William Beckwith 1994-12-01 13:59 ` Henry G. Baker 1994-12-02 4:26 ` R. William Beckwith 1994-12-02 21:37 ` Hans Boehm 1994-12-03 15:17 ` Henry G. Baker 1994-12-09 22:07 ` Bob Duff 1994-12-11 23:59 ` Gary McKee 1994-12-12 5:04 ` Henry G. Baker 1994-12-12 12:46 ` R. William Beckwith 1994-12-16 19:35 ` Bob Duff 1994-12-17 20:36 ` Robert Dewar 1994-12-20 5:24 ` Henry G. Baker 1994-12-12 9:36 ` Robb Nebbe 1994-12-13 16:12 ` Henry G. Baker [not found] ` <DAG.94Nov30090717@bellman.control.lth.se> 1994-11-30 16:39 ` David Weller 1994-11-30 17:58 ` Erik Naggum 1994-11-30 23:14 ` Michael Feldman 1994-12-09 14:19 ` Ada 95 is the name Tucker Taft 1994-12-09 22:33 ` Pat Rogers 1994-12-11 18:59 ` Jean D. Ichbiah 1994-12-11 20:05 ` Pat Rogers 1994-12-16 1:01 ` Bob Duff 1994-12-12 14:50 ` Garlington KE 1994-12-13 21:48 ` Tucker Taft 1994-12-14 12:44 ` Gentle 1994-12-14 17:34 ` Jean D. Ichbiah 1994-12-10 10:10 ` Marc Wachowitz 1994-12-11 21:37 ` Bob Duff 1994-12-02 23:41 ` Reference Counting (was Re: Searching Method for Incremental Garbage Collection) Bob Duff 1994-12-03 8:16 ` Bill Birch [not found] ` <3be0mh$1p7@ga <3bii2g$kn2@news.parc.xerox.com> 1994-12-01 4:58 ` Kevin Warne 1994-12-02 21:58 ` Hans Boehm [not found] <D06r8x.JBy@inmet.camb.inmet.com> 1994-12-02 17:32 ` Henry G. Baker 1994-12-05 20:59 ` Robert Firth 1994-12-06 14:15 ` Robert Dewar 1994-12-04 1:06 ` Rick Busdiecker 1994-12-04 18:57 ` R. William Beckwith
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox