gc's and locality (with ref. list)

Steve Boswell wrote:
>There was a discussion over in comp.compilers about SML NJ (a Standard
>ML compiler) and how its garbage collector thrashed virtual memory.


It should be noted that the SML of NJ GC is a generational GC, and while
it's not designed to work particularly well in virtual memory, it's still
not nearly as bad as a simple mark-sweep or semispace copying collector.
There's certainly an advantage to using the SML of NJ compiler, because it
allows you to use a much smaller memory size than a simple gc lets you
use, without incurring greatly increased copying costs due the the
increased frequency of garbage collections. So it's designed to do less
copying for a given size of main memory rather than to operate in a large
virtual memory.




In a simple, non-generational copy collector, you have to copy all the
live data at every garbage collection. The smaller the memory you use,
the more often you have to garbage collect and copy whatever's live at
that time.


With a generational gc, most of the live data at a given collection are
copied to another area of memory, which is NOT garbage collected very
often. It's been empirically shown that most objects that survive one or
two gc's will survive several, so it's a very good idea to move those
objects someplace and leave them alone for a while.


Most objects tend to die young, and therefore don't incur any copying cost
at all, because even if you only allocate a few dozen KB between
collections, the large majority die before the next collection.


Taking the survivors and treating them specially keeps you from having to
copy them over and over again until THEY finally die.


This is the basic principle of generational garbage collection, from Henry
Lieberman and Carl Hewitt's 1983 CACM paper. (Unfortunately, that paper
is a bit too abstract in some ways and specific in others. For example,
it incorporates Baker's real-time incremental copying, which is pretty
much independent of the basic generational scheme. An easier place to
start would probably be Ungar's 1984 paper and/or my 1989 paper.)


>Has there been any work in VM-friendly garbage collection? My guess
>would be to do reference counting and a FIFO freespace list, as a
>start, and to split memory up into sub-heaps so marking doesn't cause
>all memory to be paged in.


Several papers have been published on VM friendly gc's.




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. Most people don't use reference-counting for serious systems because
it's difficult if not impossible to make it really efficient. (See
Ungar's 84 paper; Deutsch and Bobrow improved RC considerably, but it's
still not worth it for most purposes.)


Splitting the heap into sub-heaps is exactly the idea behind generational
gc's. (Surprisingly enough, you can even do generational collection with
a conservative mark-sweep gc for an off-the-shelf C system. It's hairier
than with a copy collector, because you can't move things around. Boehm,
Weiser, Demers, Hauser, Hayes and Shenker---I hope I haven't left somebody
out---of Xerox PARC, have an amazing parallel generational, non-copying gc
that collects for Scheme, Mesa, and C intermixed in one virtual memory
image. Wow.)




In addition, Jim Stamos, Ricki Blau, and I have all looked at the effects
of copy collector's traversal algorithms on the locality within the live
data that get advanced into older generations. Jim's and Ricki's results
were positive but not all that encouraging; they mostly compared breadth-
and depth- first traversals. I got much better results using an algorithm
similar to Moon's "approximately depth first" traversal. I call it
"hierarchical decomposition" copying, because it tends to group
hierarchical data structures nicely into things that resemble B-trees at
the virtual memory level. (It also linearizes simple lists quite
naturally, because they're degenerate trees; they tend to get grouped
entirely onto a page.) That's discussed in my paper from the last SIGPLAN
conference. (The algorithm is really pretty simple. We hacked it in C.)


I also found that it's important to be VERY CAREFUL when traversing hash
tables, to avoid scrambling the data structures you reach from the hash
table. (If you scan a hash table in linear order, you reach data
structures in pseudo-random order and copy them that way... that can be a
real disaster if your highest-level namespace structures are big hash
tables, and that's where you reach EVERYTHING from. That's common in Lisp
and Smalltalk systems.)




Other people (Jon L White, now of Lucid, and Bob Courts and Doug Johnson
at TI) have looked at using incremental garbage collectors to copy objects
as the running program reaches them. That tends to reorder objects in the
order they're likely to be touched in the future, as well, and improves
locality. It's not very attractive these days, though, because it
requires specialized Lisp-machine style hardware to be efficient. (Some
similar stuff was done by the MUSHROOM group at Manchester, working on
object oriented memory hardware.)


My group is currently looking at similar reordering tricks that work in a
conventional memory hierarchy, by reordering VM pages within larger units
of disk transfer. We believe that's the right granularity to work at
anyway, so no special hardware is necessary (small pages are nice,
though). Another nice benefit is that it doesn't even require a gc'd
language---it should work for most things in most languages. (This is of
particular importance because we want to support C++; we're implementing a
persistent store for GCC that uses address translation at page fault time
to support arbitrarily huge address spaces efficiently on stock hardware.)


                    --- Paul


P.S. Anybody who asked for an email copy of the tech. summary of my paper
(on generational gc's effects on cache memories) should have gotten it by
now. I got a lot of bounces though, so you should try me again if you
haven't gotten it. If you send me a postal address, I can just send
hardcopy.


----------------------------------------------------------------------------
Here are a few references. Discussion and more references can be found in
my OOPSLA and SIGPLAN PLDI papers. (Those proceedings come out as special
issues of SIGPLAN Notices, so they should be easy to find.)


@inproceedings{Whit80,
author = "White, Jon L.",
title = "Address/Memory Management For a Gigantic {L}isp Environment, or, {GC}
Considered Harmful",
booktitle = "Conference Record of the 1980 {L}isp Conference",
note = {Redwood Estates, California},
pages = "119--127",
month = aug,
year = 1980 }


@article{LiHe83,
author = "Lieberman, Henry and Carl Hewitt",
title = "A Real-Time Garbage Collector Based on the Lifetimes of Objects",
journal = CACM,
volume = 26,
number = 6,
month = "June",
year = 1983
pages = "419--429"}


@inproceedings{Moon84,
author = "Moon, David",
title = "Garbage Collection in a Large {L}isp System",
booktitle = "Conference Record of the 1984 {ACM} Symposium on {L}isp and
Functional Programming",
year = 1984,
month = aug,
pages = "235--246",
note = {Austin, Texas} }


@inproceedings{Mo:AS3600,
AUTHOR = "David A. Moon",
TITLE = "Architecture of the {S}ymbolics 3600",
@inproceedings{Unga84,
author = "Ungar, David M.",
title = "Generation Scavenging: A Non-disruptive High-Performance Storage
Reclamation Algorithm",
booktitle = "Proceedings of the {ACM SIGSOFT/SIGPLAN} Software
Engineering Symposium on Practical Software Development Environments",
month = apr,
year = 1984,
pages = "157--167",
note = "Also distributed as {\em ACM SIGPLAN Notices 19}(5):157--167,
May, 1987" }


@article{Cour88,
author = "Courts, Robert",
title = "Improving Locality of Reference in a Garbage-Collecting Memory
Management System",
journal = CACM,
volume = 31,
number = 9,
month = Sep,
year = 1988,
pages = "1128--1138" }


@techreport{Deb:EGCGM,
@inproceedings{WM:OGC,
author = "Wilson, Paul R. and Thomas G. Moher",
title = "Design of the Opportunistic Garbage Collector",
booktitle = OOPSLA89,
note = "New Orleans, Louisiana",
month = Oct,
year = 1989,
pages = "23--35"
}


@inproceedings{GCandMH,
author = "Wilson, Paul R.",
title = "Some Issues and Strategies in Heap Management and Memory
Hierarchies",
booktitle = "{OOPSLA/ECOOP} '90 Workshop on Garbage Collection in
Object-Oriented Systems",
note = "Also in {\em SIGPLAN Notices 23}(1):45--52, January 1991.",
month = oct,
year = 1990 }


@inproceedings{DJoh91,
title = "The Case For a Read Barrier",
author = "Douglas Johnson",
booktitle = "Proceedings of the Fourth International Conference on
Architectural Support for Programming Languages and Operating Systems
(ASPLOS IV)",
note = {Santa Clara, CA},
month = "April",
year = 1991,
pages = "96--107" }


@inproceedings{Wi:DM,
@inproceedings{StaticGrouping,
author = "Wilson, Paul R. and Michael S. Lam and Thomas G. Moher",
title = "Effective Static-Graph Reorganization to Improve Locality in
Garbage-Collected Systems",
booktitle = "Proceedings of the {ACM} {SIGPLAN} '91 Conference on
Programming Language Design and Implementation",
month = Jun,
year = 1991,
note = {Toronto, Canada},
pages = "177--191" }




@inproceedings{BDS:MPGC,
AUTHOR = "Hans-J. Boehm and Alan J. Demers and Scott Shenker",
TITLE = "Mostly Parallel Garbage Collection",
BOOKTITLE = PLDI,
YEAR = 1991,
PAGES= {157--164}
}


@techreport{SwizzCAN,
title = "Pointer Swizzling at Page Fault Time: Efficiently Supporting
Huge Address Spaces on Standard Hardware",
author = "Paul R. Wilson",
type = "Technical Report",
number = "UIC-EECS-90-6",
institution = "University of Illinois at Chicago, Electrical Engineering and
Computer Science Department",
address = "Chicago, Illinois",
month = Dec,
year = 1990,
note = "Also in {\em Computer Architecture News}, 19(4):6-13, June 1991"}


@techreport{WiLM90b,
title = "Caching Consideration For Generational Garbage Collection",
author = "Paul R. Wilson and Michael S. Lam and Thomas G. Moher",
institution = "University of Illinois at Chicago EECS Dept.",
type = "Technical Report",
number = "UIC-EECS-90-5",
address = "Chicago, Illinois",
month = Dec,
year = 1990,
note = "A much improved version will appear in ACM 1992 Conf on Lisp and
Functional Programming.
Technical summary available from wilson@cs.utexas.edu"}
--

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