Re: gc's and locality (with ref. list)
Mon, 10 Feb 1992 10:38:23 GMT

          From comp.compilers

Related articles
VM-friendly GC (1992-02-08)
gc's and locality (with ref. list) (1992-02-08)
Re: gc's and locality (with ref. list) (1992-02-10)
copying vs. mark-sweep gc's; more gc biblio; funny (1992-02-10)
Re: copying vs. mark-sweep gc's; more gc biblio; funny (1992-02-12)
gc locality and the gc toolkit (1992-02-13)
| List of all articles for this month |

Newsgroups: comp.compilers
Keywords: storage, bibliography
Organization: Technische Universitaet Wien, Institut fuer Computersprachen
References: 92-02-039 92-02-040
Date: Mon, 10 Feb 1992 10:38:23 GMT

In article 92-02-040, (Paul Wilson) writes:
|> Reference counting has better locality than simple copying or mark-sweep,
|> but I don't think anybody's ever properly compared it to a generational
|> GC.

The paper below suggests that it has been done. I was rather surprised
that nobody seems to reference that paper. Are the results not applicable
to other systems?

author = "Benjamin Zorn",
title = "Comparing Mark-and-sweep ans Stop-and-copy Garbage Collection",
booktitle = "Proceedings of th 1990 ACM Conference on Lisp and functional
abstract = "Stop-and-copy garbage collection has been preferred to
mark-and-sweep collection in the last decade because its collection time
is proportional to the size of reachable data and not the memory size.
This paper compares the CPU overhead and the memory requirements of the
two collection algorithms extended with generations, and finds that
mark-and-sweep collection requires at most a small amount of additional
CPU overhead (3-6%) but requires an average of 20% (and up to 40%) less
memory to achieve the same page fault rate. The comparison is based on
results obtained using trace-driven simulation with large Common Lisp
month = june,
year = 1990 }

Another interesting citation from the paper is:
Many recent papers on copying gc algorithms have mentioned mark-and-sweep
collection only in passing, noting that because the cost is proportional to
the size of memory, mark-and-sweep collection is less efficient that copying
collection [....]. Appel, Ellis, and Li note that the cost of mark-and-sweep
collection is probably somewhat higher than the cost of copying collection,
but concede that other costs (allocation, barriers, vm overhead) effect
performance enough that copying collectos may not necessarily be the most

I note that the cost of sweeping is just an extension of the cost of
allocation, and quantify that cost to be up to 5% in allocation intensive
Ulrich Neumerkel,
(ulrich@vip.UUCP) +431 58801/4477 fax +431 5057838
TU Inst.f. Computersprachen E185/1 Argentinierstr.8/4, A-1040 Wien Austria

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.