hudson@yough.cs.umass.edu (Rick Hudson) (04/23/91)
stolfi@src.dec.COM writes: > > > Around here we sit around and count the number of > instructions/record it takes to do allocation and garbage collection > on our fingers. This myth that GC takes thousands of instruction > for each allocation just isn't true. > > Congratulations, you must be a very happy man... Actually, I just broke my finger playing basketball, thus ending my digital computing for a while :-) > I presume you have a good incremental garbage collector in a favorable > architecture, and you measured its performance on typical real-world > programs (whatever that means). Moon, David ("Garbage Collection in a Large Lisp System" Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming) and Ungar, David and Jackson, Frank, ("Tenuring Policies for Generation-Based Storage Reclamation", OOPSLA 1988 Conference Proceedings) describe techniques aimed at improving garbage collection in "real" world situations. > Forgive me if I sound a bit skeptical, but often the cost of garbage > collection does not scale linearly with working set size. Do you still > get tens of instruction/record when you have, say, 5MB worth of active > nodes? The above references discuss your concerns. > For example, the SRC Modula-3 compiler currently uses a copying > garbage collector, whose cost per allocation grows rather quickly as > the size of accessible structures approaches the total available memory > size. Does the SRC Modula-3 use Bartlett's, Joel F. (Mostly Copying Garbage Collection Picks Up Generations and C+, DEC-WRL Tech note TN12) enhancements that incorporate generations. I would have guessed that this work would have lessened such problems. > > Note also that, depending on the implementation, the mere existence > of GC may slow down all pointer assignments quite a bit, even when > the program is not doing any allocations. Bartlett (above) reports a 4% to 12% slowdown due to remembered set maintenance in Scheme->C using some of the Gabriel benches. > For instance, our Modula-2+ > GC is partly based on reference counts, and the code for an assignment > of the form ref1^.field := ref2 must update the reference count of > ref2^. Since Modula-2+ programs are usually multi-threaded and run > on multi-processor workstations, that code must be careful to do the > right thing even when two threads are trying to update the same count > at the same time. On a vanilla VAX architecture, this apparently takes > at least a dozen VAX instructions. Reference count GCs also deal poorly with reference count overflow as well as circular list structures. Mark-and-Sweep collection do not seem practical either, but Zorn, Benjamin ("Comparing Mark-and-Sweep and Stop-and-Copy Garbage Collection" 1990 ACM Conference on Lisp and Functional Programming) has added generations and indicated why we should reconsider Mark-and-Sweep algorithms. Apple, Andrew W. and Li, Kai ("Virtual Memory Primitives for User Programs" Architectural Support for Programming Languages and Operating Systems, 1991) discusses what support would be needed from the OS to implement faster incremental, generational GCs, some of their suggestions deal directly with how to handle pointer updates and other remembered set problems. Hope this helps. - Rick
Hans_Boehm.PARC@xerox.com (04/24/91)
Rick Hudson writes:
"Reference count GCs also deal poorly with reference count overflow as well as
circular list structures. Mark-and-Sweep collection do not seem practical
either, but Zorn, Benjamin ("Comparing Mark-and-Sweep and Stop-and-Copy
Garbage Collection" 1990 ACM Conference on Lisp and Functional Programming)
has added generations and indicated why we should reconsider Mark-and-Sweep
algorithms."
I would like to amend the last sentence with a further plea for caution. The
tradeoffs between various techniques are much more subtle than some of the
recent literature indicates. Reference counting may well win if your heap is
nearly full most of the time. It may win in other cases, too. See DeTreville,
"Experience with Concurrent Garbage Collectors for Modula-2", SRC report 64.
Similarly Mark-and-Sweep seems to win in a number of cases, even in a much
purer form than that used by Ben Zorn. It can handle large numbers of
ambiguous references. It requires significantly less compiler support. It
almost always touches significantly less memory during full collections. It
allows hashing on addresses. I would argue that there are better (stock
hardware) parallel collection algorithms available than for copying collection.
(See our upcoming SIGPLAN paper.)
Of course, copying collection has its advantages, too. But there seems to be
no shortage of papers advertising those.
Hanssakkinen@jyu.fi (Markku Sakkinen) (04/25/91)
In article <91Apr23.113622pdt.16245@alpha.xerox.com> Hans_Boehm.PARC@xerox.com writes: > ... >Of course, copying collection has its advantages, too. But there seems to be >no shortage of papers advertising those. One very important disadvantage of copying collection is that it restricts the possible semantics of objects: no finalisation (destructors, as in C++) is possible. This has been explicitly admitted at least in Edelson's report. One could very well paraphrase the above restriction: "Old objects never die, they just fade quietly away." Markku Sakkinen Department of Computer Science and Information Systems University of Jyvaskyla (a's with umlauts) PL 35 SF-40351 Jyvaskyla (umlauts again) Finland SAKKINEN@FINJYU.bitnet (alternative network address)
chased@rbbb.Eng.Sun.COM (David Chase) (04/26/91)
sakkinen@jytko.jyu.fi (Markku Sakkinen) writes: >One very important disadvantage of copying collection is that it >restricts the possible semantics of objects: no finalisation >(destructors, as in C++) is possible. Finalisation is possible with copying collection, though it is not pretty. The game played is somewhat like the game played to implement "weak pointers". Registering a pointer for finalisation is implemented by hiding it on a list (hidden by its encoding, or hidden by design). At a collection, assume that all the live pointers have been forwarded. At this point, traverse the list of finalizable objects. Each pointer stored there is either forwarded, or about to die. All the sickly pointers are placed on another list, and the objects that they reference are copied into new space. Of course, these objects may reference other objects, etc. At this point, you've got a couple of choices based on how you feel about cyclic and shared finalisable garbage. The easy answer is to declare that it is all going to die, and to finalise everything on the "sickly list". The hard answer is to assume that finalisation might alter the accessibility of memory (e.g., "global_variable := my_component"), and proceed accordingly. Except for cycles, even this can be dealt with, though it is painful (find the roots of the finalisable garbage graph, finalise them, put everything else back on the finalisable list, wait till next collection). One hopes that better algorithms to do this exist, but it is possible. David