Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!spool.mu.edu!uwm.edu!bionet!parc!boehm From: boehm@parc.xerox.com (Hans Boehm) Newsgroups: comp.lang.c++ Subject: Re: Smart pointers and stupid people (was: garbage collection...) Message-ID: Date: 12 Feb 91 18:58:12 GMT References: <3344@lupine.NCD.COM> <4174@osc.COM> <3779@lupine.NCD.COM> <70606@microsoft.UUCP> Sender: news@parc.xerox.com Distribution: comp Organization: Xerox PARC Lines: 53 tom@ssd.csd.harris.com (Tom Horsley) writes: >Yep. Mark-and-sweep type algorithms can leave objects in their original >location, but copy collecting algorithms move them around (in fact, the way >most simple copy collectors are implemented, they *always* move an object >when GC is run). >If you examine the literature on garbage collection, you will find that the >performance is generally vastly superior for variations of copy collectors. >This is the main reason a lot of people are interested in GC schemes in >which objects *do* move. Neither copying, nor mark-sweep collection performs uniformly better under all circumstances. The tradeoffs are fairly complicated. The standard argument about copying collection taking time proportional to the number of accessible objects and mark/sweep collection taking time proportional to the size of the heap is 95% bogus. If you include allocation time, they are both the same. If you do not include allocation time, I can write my Mark-Sweep collector so that the Sweep pahse takes place incrementally during allocation. Copying collection tends to do better (by a constant) with large amounts of available physical memory (and no shortage of resources needed to map it into your address space). It also interacts better with generational collection, since I can keep the generations physically separated. However, It is not at all clear that copying outperforms M/S when paging becomes an issue. Copying requires that you allocate roughly twice as much virtual memory as for M/S, all of which is touched at least once for every full collection cycle. A M/S collector may run in physical memory, when a copying collector would be thrashing. (It takes a long time to page in 20 MB, even if it happens only every once in a while.) It is also unclear which strategy produces better locality between collections. Simple breadth-first copying collectors do compact, but in such a way that a single data structure tends to get smeared over the entire heap. Based on what little data I've seen, this is probably a lot worse than the approximation to allocation order maintained by a M/S collector. Cleverer copying collectors are possible, but something like the Appel-Ellis-Li parallel collector is nontrivial to adapt to something like depth-first traversal. I'm routinely using a parallel M/S collector. I have yet to see much realistic data on a comparison between the two strategies. (Note that the ratio of time-to-page-in-my-entire-address-space to cpu speed has gotten larger over time. Old claims should be treated with caution.) Zorn's paper in the 1990 Lisp conference does compare a copying collector with a mixed strategy, and points out that the mixed strategy often wins. (My apologies for repeating this argument again.) Hans-J. Boehm