Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!decwrl!parc!boehm From: boehm@parc.xerox.com (Hans Boehm) Newsgroups: comp.lang.c++ Subject: Re: reference counting vs. scanning GC Keywords: locality, large address spaces, reference counting, garbage collection Message-ID: Date: 22 May 91 18:09:50 GMT References: <1991Apr24.192424.23745@kestrel.edu> <72149@microsoft.UUCP> <1991May11.054648.2483@kestrel.edu> <72460@microsoft.UUCP> Sender: news@parc.xerox.com Organization: Xerox PARC Lines: 40 jimad@microsoft.UUCP (Jim ADCOCK) writes: >In article boehm@parc.xerox.com (Hans Boehm) writes: >|Reality is of course more complicated. Different objects sizes interact, >|though this is probably not a major effect, since the number of different >|object sizes in a typical data structure is probably small. In our >|experience, pages tend to be very nonuniformly populated, even after >|a system has been up for quite a while. This helps >|the nonmoving allocator, since it can chose not to allocate on nearly >|full pages. >In which case you're ending up with a situation with old pages, containing >un-reclaimed holes. Eventually pages fill up with old long-lived objects, >excepting a few holes. Either one ignores those holes, failing to reclaim >memory, in which case you don't have a stable persistent system, or one >is forced to fill the holes in old pages, in which case you've got new >objects spread out across predominantly old pages. The only way >around this dilemma is to move objects. Of course, for non-stable >systems or even quasi-stable systems, it might be acceptible to "leak" >a little memory by never plugging the holes in old pages with new objects. >But, unless one can predict a finite lifetime for one's app, you've >got to go back and fill those holes eventually. Our system does not fill holes on pages that are 3/4 occupied by old objects. (The choice of 3/4 is rather arbitrary. I don't have numbers to back up that choice.) This does nothing to prevent the system from being stable. In the (unlikely) worst case, it will prevent 1/4 of the available memory from getting used. The decision about whethether a page is 3/4 full of old objects is recomputed at every full collection. Thus holes are likely to get filled eventually, without adversely affecting my original argument about locality. Thus stability is not really the issue. We're wasting at most an amount of space proportional to the amount of live space. This is a concern. But it's usually even more of a concern with copying collectors. (Again, compacting in place wins, but ...) Hans (boehm@xerox.com)