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: 109fba,8e3b3db66f3b0061 X-Google-Attributes: gid109fba,public X-Google-Thread: 1014db,8e3b3db66f3b0061 X-Google-Attributes: gid1014db,public X-Google-Thread: fd443,8e3b3db66f3b0061 X-Google-Attributes: gidfd443,public X-Google-Thread: 103376,474d28ddf953b3c1 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 1994-12-01 02:40:57 PST Path: bga.com!news.sprintlink.net!pipex!uunet!ankh.iia.org!ralph.vnet.net!news1.digex.net!ois.com!ois.com!not-for-mail From: beckwb@ois.com (R. William Beckwith) 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) Followup-To: alt.lang.design,comp.lang.c,comp.lang.c++,comp.lang.lisp,comp.lang.ada Date: 30 Nov 1994 22:20:57 -0500 Organization: Objective Interface Systems, Inc. Message-ID: <3bjfep$9ss@gamma.ois.com> References: <3be0mh$1p7@gamma.ois.com> <3bfprn$okr@scipio.cyberstore.ca> <3bg6ci$18k@gamma.ois.com> <3bii2g$kn2@news.parc.xerox.com> NNTP-Posting-Host: gamma.ois.com X-Newsreader: TIN [version 1.2 PL2] Xref: bga.com alt.lang.design:142 comp.lang.c:32766 comp.lang.c++:39111 comp.lang.lisp:4233 comp.lang.ada:8135 Date: 1994-11-30T22:20:57-05:00 List-Id: 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