Proceedings of ISMM'00

Minneapolis, Minnesota

15-16 October, 2000

The documents contained in these directories are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis.  Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically.  It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright.  These works may not be reposted without the explicit permission of the copyright holder.

All papers (except where noted otherwise) are Copyright © 2000 by the Association for Computing Machinery, Inc.  Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.  Copyrights for components of this work owned by others than ACM must be honored.  Abstracting with credit is permitted.  To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.  Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or

Sunday October 15th Monday October 16th
8:15-9:00  Coffee & Registration 8:15-9:00 Coffee
9:00-9:15 Welcome & Introduction 9:00-10:20 Session III: Hardware Support
Chair: David Detlefs
9:15-10:20 Invited Speaker
Jon L. White
CommerceOne, Inc.
10:20-10:50 Break 10:20-10:50 Break
10:50-12:30 Session I: Accuracy & Locality
Chair: Bart Demoen
10:50-12:30 Session IV: Profiling & Object Lifetimes
Chair: Trishul Chilimbi
12:30-14:00 Lunch 12:30-14:00 Lunch
14:00-15:00 Proposal & Discussion: Trace Formats
Trishul Chilimbi, Richard Jones and Ben Zorn
14:00-15:00 Informal Presentations
Open signup for 5-10 minute presentations
Chair: Tony Hosking
15:00-15:30 Break 15:00-15:30 Break
15:30-17:00 Session II: Implementation
Chair: Eric Jul
15:30-17:00 Session V: Concurrent & Distributed
Chair: Scott Nettles
17:00-17:30 Wrap-up
17:30-18:30 OOPSLA tutorial/workshop reception 17:30-19:30 OOPSLA welcome reception
18:30-20:30 Conference dinner

Invited Speaker
Sunday 15th October, 9:15-10:20
Conquering the Hurdles, Challenging the Horizons
A Historical Perspective on Memory Management
Jon L. White
CommerceOne, Inc.

We will travel through a retrospective overview of some of the great "hurdles" in the area of Memory Management, from the discovery of "Garbage Collection", through the realization of the potential harmfulness of GC, to the expanded horizons which are driven by paradigm shifts in application programs. In the process, we will review some of the very early approaches to memory management to appreciate just how far we have come, and just how much the great leaps of this science have been driven by the appearance of cheaper and faster hardware.  We will also re-visit some "war stories" of the past where a paradigm shift was forced because of unforseen consequences in what was otherwise perceived to be a "Very Good Idea(tm)". Examples will include the speaker's own pioneering experiences in shifting from pure "collection" techniques to BIBOP storage strategies, compile-time change-of-representation for a one to two orders of magnitude speedup in numerical programs written in Lisp, to the discovery of the "Pig-in-a-Python" syndrome. Speculative, overview-like conjectures will be made about the current horizons of the field, especially with respect to large databases and the Java programming language.

A Brief Biography of Jon L. White

JonL received a B.S. degree in Mathematics from Carnegie-Mellon University, and an M.A. in Applied Mathematics from Harvard University. He subsequently joined Marvin Minsky's team at the M.I.T Artifical Intelligence Laboratory, where he began the development of high-quality Lisp systems and compilers.  The PDP10 MacLisp efforts subsequently supported not only the A.I. lab, but the MACSYMA Symbolic Algebra group, and ultimately many other university and commercial research labs.  JonL also spent one calendar year away from MIT at IBM's Watson Research Center in Yorktown Heights, NY, contributing to the development of Lisp/370.

At the birth of the commercial A.I. revolution, JonL joined a group at Xerox's Palo Alto Research Center tasked with product development of Interlisp on the special-purpose, microded Xerox D-series machines. A few years later, in January 1985, he joined the "startup" company Lucid, Inc. whose goal was to make high-quality Common Lisp systems available on all the prevalent "stock" hardware machines.  As the commercial A.I. market - and consequently the commercial Common Lisp market - went into decline in the early 1990's, JonL joined the Lisp group at Harlequin.  In all of these commercial Lisp developments, JonL contributed substantially not only to the compiler development, but also to both "GC" and higher-level memory management.

After a brief 8 months at NASA/Ames Research Center working with the Automated Software Engineering group there, JonL joined yet another startup - a spin-off from Stanford University - which was quickly bought out by his present employer CommerceOne.  He is currently working on a product called iMerge, written in Lisp and a result of many years of A.I. research at Stanford which is directed at the database needs of today's Business-to-Business commercial environment.

Session I: Accuracy & Locality
Sunday 15th October, 10:50-12:30
Chair: Bart Demoen
On the Type Accuracy of Garbage Collection, Martin Hirzel and Amer Diwan, pp. 1-11
On the Effectiveness of GC in Java, Ran Shaham, Elliot Kolodner and Mooly Sagiv, pp. 12-17
Thread-Specific Heaps for Multi-Threaded Programs, Bjarne Steensgaard, pp. 18-24
A Region-Based Memory Manager for Prolog, Henning Makholm, pp. 25-34
Proposal & Discussion: Trace Formats
Sunday 15th October, 14:00-15:00
Designing a Trace Format for Heap Allocation Events, Trishul Chilimbi, Richard Jones and Benjamin Zorn, pp. 35-49
Session II: Implementation
Sunday 15th October, 15:30-17:00
Chair: Eric Jul
Compact Garbage Collection Tables, David Tarditi, pp. 50-58
Reducing Garbage Collector Cache Misses, Hans-J. Boehm, pp. 59-64
Memory Allocation with Lazy Fits, Yoo C. Chung and Soo-Mook Moon, pp. 65-70
Conservative Garbage Collection for General Memory Allocators, Gustavo Rodriguez-Rivera, Mike Spertus and Charles Fiterman, pp. 71-79
Session III: Hardware Support
Monday 16th October, 09:00-10:20
Chair: David Detlefs
Concurrent Garbage Collection Using Hardware-Assisted Profiling, Timoth H. Heil and James E. Smith, pp. 80-93
Concurrent Garbage Collection Using Program Slices on Multithreaded Processors, Manoj Plakal and Charles N. Fischer, pp. 94-100
Cycles to Recycle: Garbage Collection on the IA-64, Richard L. Hudson, J. Eliot B. Moss, Sreenivas Subramoney and Weldon Washburn, pp. 101-110
Session IV: Profiling & Object Lifetimes
Monday 16th October, 10:50-12:30
Chair: Trishul Chilimbi
The Case for Profile-Directed Selection of Garbage Collectors, Robert Fitzgerald and David Tarditi, pp. 111-120
Efficient Object Sampling via Weak References, Ole Agesen and Alex Garthwaite, pp. 121-126
Dynamic Adaptive Pre-Tenuring, Timothy L. Harris, pp. 127-136
On Models for Object Lifetimes, Darko Stefanovic, Kathryn S. McKinley and J. Eliot B. Moss, pp. 137-142
Session V: Concurrent & Distributed
Monday 16th October, 15:30-17:00
A Generational Mostly-Concurrent Garbage Collector, Tony Printezis and David Detlefs, pp. 143-154
Copyright © 2000 by Sun Microsystems, Inc.
Implementing an On-the-Fly Garbage Collector for Java, Tamar Domani, Elliot K. Kolodner, Ethan Lewis and Eliot E. Salant, pp. 155-166
Diffusion Tree Restructuring for Indirect Reference Counting, Peter Dickman, pp. 167-177

Antony Hosking