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: 109fba,8e3b3db66f3b0061 X-Google-Attributes: gid109fba,public X-Google-Thread: f4fd2,8e3b3db66f3b0061 X-Google-Attributes: gidf4fd2,public X-Google-Thread: 103376,474d28ddf953b3c1 X-Google-Attributes: gid103376,public X-Google-Thread: 1014db,8e3b3db66f3b0061 X-Google-Attributes: gid1014db,public X-Google-Thread: fd443,8e3b3db66f3b0061 X-Google-Attributes: gidfd443,public X-Google-ArrivalTime: 1994-11-30 12:28:27 PST Path: bga.com!news.sprintlink.net!howland.reston.ans.net!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: 30 Nov 1994 18:59:28 GMT Organization: Xerox Palo Alto Research Center Message-ID: <3bii2g$kn2@news.parc.xerox.com> References: <3be0mh$1p7@gamma.ois.com> <3bfprn$okr@scipio.cyberstore.ca> <3bg6ci$18k@gamma.ois.com> NNTP-Posting-Host: siria.parc.xerox.com Xref: bga.com alt.lang.design:133 comp.lang.c:32632 comp.lang.c++:38989 comp.lang.lisp:4222 comp.lang.ada:8105 Date: 1994-11-30T18:59:28+00:00 List-Id: 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 ...