From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00,INVALID_DATE autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f4fd2,8e3b3db66f3b0061 X-Google-Attributes: gidf4fd2,public X-Google-Thread: 103376,474d28ddf953b3c1 X-Google-Attributes: gid103376,public X-Google-Thread: 109fba,8e3b3db66f3b0061 X-Google-Attributes: gid109fba,public X-Google-Thread: fd443,8e3b3db66f3b0061 X-Google-Attributes: gidfd443,public X-Google-Thread: 1014db,8e3b3db66f3b0061 X-Google-Attributes: gid1014db,public X-Google-ArrivalTime: 1994-12-02 23:48:53 PST Path: bga.com!news.sprintlink.net!hookup!swrinde!gatech!bloom-beacon.mit.edu!biosci!parc!boehm From: boehm@parc.xerox.com (Hans Boehm) Newsgroups: alt.lang.design,comp.lang.c,comp.lang.c++,comp.lang.lisp,comp.lang.ada Subject: Re: Reference Counting (was Re: Searching Method for Incremental Garbage Collection) Date: 2 Dec 1994 21:37:47 GMT Organization: Xerox Palo Alto Research Center Message-ID: <3bo43b$61v@news.parc.xerox.com> References: <3be0mh$1p7@gamma.ois.com> <3bfprn$okr@scipio.cyberstore.ca> <3bg6ci$18k@gamma.ois.com> <3bii2g$kn2@news.parc.xerox.com> <3bjfep$9ss@gamma.ois.com> NNTP-Posting-Host: siria.parc.xerox.com Xref: bga.com alt.lang.design:153 comp.lang.c:33157 comp.lang.c++:39382 comp.lang.lisp:4255 comp.lang.ada:8220 Date: 1994-12-02T21:37:47+00:00 List-Id: 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 ...