Re: gc's and locality (with ref. list)

In article 92-02-040, wilson@cs.utexas.edu (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?


@inproceedings{Zorn,
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
programming",
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
programs",
month = june,
year = 1990 }


Another interesting citation from the paper is:
\begin{quote}
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
effective.


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
programs.
\end{quote}
--
Ulrich Neumerkel, ulrich@dec4.wu-wien.ac.at ulrich@mips.complang.tuwien.ac.at
(ulrich@vip.UUCP) +431 58801/4477 fax +431 5057838
TU Inst.f. Computersprachen E185/1 Argentinierstr.8/4, A-1040 Wien Austria
--

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