Re: Large-space GC

I promised to summarize responses to my question: ``Has anybody looked at
garbage collection in very large address spaces.'' In particular, I was
interested in cases where the GCable space is large enough that it cannot
be scanned by a tracing collector in a reasonable time.


Thanks to:
moss@cs.umass.edu (Eliot Moss)
Scott Draves <spot@HOPELESS.MESS.CS.CMU.EDU>
kandt@ai-titania.Jpl.Nasa.Gov (kirk kandt)
jyl@Eng.Sun.COM (Jacob Levy)
hosking@kiwi.cs.umass.edu (Tony Hosking)
hisgen@src.dec.com (Andy Hisgen)
Gordon Russell gor@computer-science.strathclyde.ac.uk
detlefs@src.dec.com (Dave Detlefs)
cliffc@cs.rice.edu (Cliff Click)
chambers@klamath (Craig Chambers)
bruce@ugcs.caltech.edu (Bruce J Bell)


Probably the original reference that dealt with this problem is Bishop's
MIT Ph.D dissertation. Of the ideas I originally mentioned, his work is
closest to "Keep summary info for a segment, where the summary info says
what other segments have pointers in to the segment and what other
segments are pointed to by the segment." Or as another respondent put it,
"indirection tables that track all pointers into and out of an area."


Andy Hisgen notes that some segments will be large and contribute no
references. For example, images & sound. The garbage collector can skip
tracing such objects, and reference counting will work on them since they
can't possibly be part of a cycle.


He also suggested an incremental scheme having `anchor pointers', where
removing the anchor pointer puts the object on a GC candidate list. If
the collector finds it dead, great. If the collector finds it live, it
promotes a new anchor and the object need not be examined again until the
new anchor is discarded. He suggests the anchor might tend to migrate to
stable objects, further reducing the frequency of consideration. He
suggests the effective size of a pointer would double or triple.


Several respondents noted locality must be important in large spaces.


Somebody asked if my posting was bait. I wish it were :-) Sorry, I have
not already done work on GC in systems with single-level stores. Seems to
me like an interesting area...


Gordon Russell suggests reference counting probably has too much
incremental overhead to be useful, which sounds like he's hopeful there
are efficient solutions even for large-space GC. He also points out that
my suggestion of marking memory segments non-GC'able only works
automatically in general up to a write to the segment. Detecting writes
is easy for a single machine, but for his work in networked GC, that won't
work. He has a paper on distributed references and another on
gang-deallocation of groups of objects, but I didn't get a citation. He
also votes that my security concerns point out a corruption of the idea of
a uniform object heap.


Rick Hudson notes conservative GC is really great partly because the range
of addresses where there is heap-allocated data is small compared to the
values of random integers (floating-point numbers, strings, ...) found on
the stack (in the heap, ...). He suggests that write barriers techniques
for GC are similar to those for persistant stores [Hosking91] and that
write barriers are not all that expensive [HMS92]. He also mentions that
Modula-3 qualifies objects and types as reference-contributing or not.


Citations:


@PhDThesis{BishopPhd,
Key = "Bishop",
Author = "Bishop, Peter B.",
Title = "Computer Systems with Very Large Address Spaces and
Garbage Collection",
School = "MIT",
Year = "1977",
Month = "May",
Address = "Cambridge, MA",
Annote = "Available as MIT TR MIT/LCS/TR-178"
}


@PhdThesis(Detlefs90b,
Author = "Detlefs, David L.",
Key = "Detlefs",
Title = "Concurrent, Atomic Garbage Collection",
Schule = "Carnegie-Mellon University",
Year = "1990",
Annote = "Available as CMU TR CMU-CS-90-119",
)


@INPROCEEDINGS{garbage:hayes91,
AUTHOR = "Barry Hayes",
TITLE = "Using Key Objects Opportunism to Collect Old Objects",
BOOKTITLE = "OOPSLA'91",
PAGES = "33--46",
YEAR = "1991"
}


@Misc{Hosking91,
author = "Antony L. Hosking",
title = "Main Memory Management for Persistence",
year = 1991,
month = oct,
note = "Position paper presented at the OOPSLA '91
Workshop on Garbage Collection",
howpublished = "anon ftp ibis.cs.umass.edu
pub/papers/oopsla91gc.ps.Z"
}


@InProceedings{HMS92,
author = "Antony L. Hosking and J. Eliot B. Moss and
Darko Stefanovi{\'c}",
title = "A Comparative Performance Evaluation of Write
Barrier Implementations",
crossref = "oopsla92",
note = "To appear.",
}


@Misc{HuMo92,
author = "Richard L. Hudson and J. Eliot B. Moss",
title = "Incremental collection of mature objects",
howpublished = "International Workshop on Memory Management",
year = 1992,
month = sep,
note = "To appear"
Abstract = "We present a garbage collection algorithm
that extends generational scavenging to collect large older
generations ({\em mature objects}) non-disruptively. The algorithm's
approach is to process bounded-size pieces of mature object space at
each collection; the subtleties lie in guaranteeing that it eventually
collects any and all garbage. The algorithm does not assume any
special hardware or operating system support, e.g., for forwarding
pointers or protection traps. The algorithm copies objects, so it
naturally supports compaction and reclustering."
}


@Misc{Moss90c,
author = "J. Eliot B. Moss",
title = "Garbage Collecting Persistent Object Stores",
year = 1990,
month = oct,
note = "Position paper for OOPSLA/ECOOP '90 workshop on
garbage collection",
howpublished = "anon ftp ibis.cs.umass.edu
pub/papers/oopsla90gc.ps.Z"
}


@article{WhiteLFP,
Author = "Jon L. White",
Key = "White",
Title = "?",
Journal = "Proceedings of the first Lisp and Functional
Programming Conference",
Year = "1979 or 1980",
}


@article{Hawaii,
Journal = "Proceeedings of the Hawaii International Conference
on System Sciences",
Year = "1992"
}


@book{Canada,
Booktitle = "Distributed Object Management",
Editor = "Ozsu",
Publisher = "Morgan-Kaufman",
Year = "1992 (in preparation)",
Note = "From a workshop `in Canada'"
}


See also anonymous ftp:
ibis.cs.umass.edu pub/papers/dbpl89.ps.Z


And somebody mentioned Paul Wilson's paper on pointer swizzling,
"Operating System Support for Small Objects", but I don't have a handy
reference (so to speak...) If you write to Paul
(wilson@edu.utexas.cs) I'm confident he'll provide you with a
reference.


Finally, it's always dangerous to ask for references in the field of
garbage collection:


>>If you can dig up a reference -- even a partial one -- I would
>>certainly like it, and I will include it in my summary.


> I suppose you mean the collecting of objects together into blocks
> for garbage collection purposes paper? If so, that would be [list of
> citations]


But I suppose it's equally risky to ask for citations when you're
studying law :-)


;-D on ( A two-bit reference ) Pardo
--

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