These works are copyright © ACM, IEEE, Usenix, Prentice-Hall, Springer-Verlag, North-Holland, Byte Magazine, IBM, or David F. Bacon. Permission to make digital or hard copies of part of 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. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

List of publications in printable form. The citations are available in LaTeX BibTeX format, including abstracts for most papers.

Invited Papers

David F. Bacon, Perry Cheng, David Grove, Michael Hind, V.T. Rajan, Eran Yahav, Matthias Hauswirth, Christoph Kirsch, Daniel Spoonhower, and Martin T. Vechev
Proceedings of the Fifth ACM International Conference on Embedded Software (Jersey City, New Jersey, September 2005).

An overview of the technology behind Metronome real-time garbage collection and our ongoing research program in making Java a high-level real-time programming language, and addressing the needs of complex real-time systems in general.

David F. Bacon, Ravi Konuru, Chet Murthy, and Mauricio Serrano
Twenty Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation: A Selection (2004), ACM SIGPLAN Notices, volume 39, number 4 (April 2004), pp. 583-595. Includes original paper.

Thin locks were selected as one of the most influential contributions in last twenty years of the PLDI conference. The retrospective discusses the origins, subsequent improvements, and future direction of this work.

Refereed Publications

Martin T. Vechev, David F. Bacon, Perry Cheng, and David Grove
Proceedings of the Nineteenth European Conference on Object-Oriented Programming, (Glasgow, Scotland, July 2005), Lecture Notes in Computer Science, Lecture Notes in Computer Science (to appear).
Presentation.

Presents a new abstract, generalized, and more accurate algorithm for concurrent garbage collection, shows how both pre-existing and new concrete algorithms can be derived, and studies the relative performance of four algorithms.

David F. Bacon, Perry Cheng, David Grove, and Martin T. Vechev
Proceedings of the Conference on Languages, Compilers, and Tools for Embedded Systems (Chicago, Illinois, June 2005), ACM SIGPLAN Notices, volume 40, number 7, July 2005, pp. 183-192.
Presentation.

Shows how two new techniques, syncopation and arraylet pre-tenuring can be combined with an over-clocked scheduler to extend the benefits of generational systems to real-time garbage collection.

Harel Paz, David F. Bacon, Elliot K. Kolodner, Erez Petrank, and V.T. Rajan
Proceedings of the Fourteenth International Conference on Compiler Construction, (Edinburgh, Scotland, April 2005), R. Bodik, editor, Lecture Notes in Computer Science vol. 3443, pp. 156-171.
Presentation.

A number of improvements to the Recycler algorithm greatly reduce the load on the cycle collector and yield a corresponding increase in performance.

David F. Bacon, Perry Cheng, and V.T. Rajan
OOPSLA'04 Conference Proceedings: Object-Oriented Systems, Languages, and Applications, ACM SIGPLAN Notices volume 39, number 10, October 2004, (Vancouver, British Columbia), pp. 50--68.
Presentation.

Tracing and reference counting garbage collection are shown to be duals of one another, and all high-performance garbage collectors are shown to be hybrids of tracing and reference counting. A uniform cost model for comparing space and time requirements is provided.

David F. Bacon
Third International Workshop on Language Runtimes (Vancouver, British Columbia, October 2004).
Presentation.

Position paper describing a vision for future virtual machines, in which all components, from the run-time system down to the hardware instruction set, are virtualized and dynamically generated.

Martin T. Vechev and David F. Bacon
Proceedings of the International Symposium on Memory Management (Vancouver, British Columbia, October 2004), pp. 13-24.
Presentation.

A limit study of the opportunities for eliminating write barriers in concurrent garbage collectors, showing that in many cases well over 90% of write barriers are redundant.

Sunil Soman, Chandra Krintz, and David F. Bacon
Proceedings of the International Symposium on Memory Management (Vancouver, British Columbia, October 2004), pp. 49-60.
Presentation.

Shows how a virtual machine can dynamically switch between diverse garbage collectors to optimize performance as the application mix and available resources change.

David F. Bacon, Xiaowei Shen
First Watson Conference on Interaction between Architecture, Circuits, and Compilers (Yorktown Heights, New York, October 2004).
Presentation.

Braids and Fibers are high level constructs for user-level programming of of threads that are significantly lightweight to respond to cache misses. Hardware support in the form of split-phase loads and stores, and a hardware/software handshake for completed split-phase operations is described, and the compilation of high-level code to the extended instruction set is described.

David F. Bacon, Perry Cheng, and David Grove
Proceedings of the Fourth ACM International Conference on Embedded Software (Pisa, Italy, September 2004), pp. 125-136.
Presentation.

Describes two different garbage collector implementations for a J2ME virtual machine (mark-compact and paged mark-sweep), along with some novel techniques for reducing per-object overheads. Several versions of each collector are tested using the EEMBC embedded systems benchmark suite, and most of them perform well with only 10% space overhead.

David F. Bacon, Perry Cheng, and V.T. Rajan
Workshop on Java Technologies for Real-Time and Embedded Systems (Catania, Sicily, November 2003), Proceedings of the OTM Workshops, R. Meersman and Z. Tari, eds., Lecture Notes in Computer Science vol. 2889, pp. 466-478. Presentation.

A position paper that shows how true real-time garbage collection, as we have implemented in the Metronome, can greatly simplify the programmer interface for real-time systems over that provided by environments such as the Real-Time Specification for Java (RTSJ).

John Corwin, David F. Bacon, David Grove, and Chet Murthy
OOPSLA'03 Conference Proceedings: Object-Oriented Systems, Languages, and Applications, ACM SIGPLAN Notices, volume 38, number 11, October 2003 (Anaheim, California), pp. 241-254. Presentation.

Describes a module system for Java that is compatible with the existing Java language but provides significantly improved support for building large, robust, long-lived systems out of modular components. We implemented MJ and converted the Tomcat web application server from using classloaders to using about 30 MJ modules. The resulting system is much easier to install and maintain, and also achieves a 30% speedup.

David F. Bacon, Perry Cheng, and V.T. Rajan
Proceedings of the Conference on Languages, Compilers, and Tools for Embedded Systems (San Diego, California, June 2003). ACM SIGPLAN Notices Volume 38, number 7, July 2003, pp. 81-92. Presentation.

Describes the Metronome real-time garbage collector's mechanisms for limiting fragmentation and the resulting wasted space. The application is characterized in terms of a fragmentation factor λ. For real-world applications λ is very small and the collector only needs to copy a very small number of objects to limit fragmentation.

David F. Bacon, Perry Cheng, and V.T. Rajan
Conference Record of the Thirtieth ACM Symposium on Principles of Programming Languages (New Orleans, Louisiana, January 2003), pp. 285-298. Presentation .

Describes a real-time garbage collector for uniprocessors, implemented for Java in the Jikes RVM virtual machine. The collector makes use of low-overhead read barriers (4%), and is mostly non-copying. Pause times are low and utilization meets the target within a small range of variation.

David F. Bacon, Stephen J. Fink, and David Grove
Proceedings of the Sixteenth European Conference on Object-Oriented Programming (Málaga, Spain, June, 2002), B. Magnusson, ed., Lecture Notes in Computer Science vol. 2374, pp. 111-132. Presentation.

Most implementations of Java use two or three word object headers. We show that there are a variety of ways to represent this information using a single header word without any appreciable run-time performance penalty, while reducing memory consumption by 12%. We also show how this can be implemented in the IBM Jikes RVM as a pluggable module, thereby making the object model more well-documented, flexible, and amenable to experimentation.

David F. Bacon
Concurrency--Practice and Experience, volume 15, numbers 3-5, March-April 2003, pp. 185-206.

Kava is a backward-compatible extension to Java that allows a single object model to be used consistently from the bit level on up, combining the abstraction facilities of high-level object-oriented programming languages with the ability to create highly efficient value types.

Clement R. Attanasio, David F. Bacon, A. Cocchi, and Stephen E. Smith
Proceedings of the Fourteenth Annual Workshop on Languages and Compilers for Parallel Computing, (Cumberland Falls, Kentucky, August 2001), H.G. Dietz, ed., Lecture Notes in Computer Science vol. 2624 (January 2003), pp. 177-192.
Presentation at University of Washington, June 5, 2001.

Describes a suite of garbage collectors we implemented in the IBM Jalapeño Java Virtual Machine, and quantitatively evaluates the relative performance of the different collectors. With large amounts of available memory, a generational semi-space copying collector performs best. But a hybrid collector that uses a copying semi-space for the young generation and a mark-and-sweep collector for the old generation can run at close to the same speed in half the memory of other collectors, thereby doubling the potential transaction throughput.

David F. Bacon, Clement R. Attanasio, Han B. Lee, V.T. Rajan, and Stephen E. Smith
Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, Snowbird, Utah (June 2001), ACM SIGPLAN Notices, volume 36, number 5, May 2001, pp. 92-103. Presentation.

The Recycler is a concurrent multiprocessor garbage collector with extremely low pause times (maximum of 6 milliseconds over eight benchmarks) while remaining competitive with the best throughput-oriented collectors in end-to-end execution times. This paper describes the overall architecture of the Recycler, including its use of reference counting and concurrent cycle collection, and presents extensive measurements of the system comparing it to a parallel, stop-the-world mark-and-sweep collector.

David F. Bacon and V.T. Rajan
Proceedings of the Fifteenth European Conference on Object-Oriented Programming (University Eötvös Loránd, Budapest, Hungary, June 2001), J.L. Knudsen, ed., Lecture Notes in Computer Science vol. 2072, pp. 207-235.
Presentation at U.C. Berkeley, Feb. 6, 2001.

This paper describes in detail the concurrent cycle collection algorithm employed in the Recycler (see above). It includes both detailed pseudo-code and a proof of correctness. Measurements show that cycle collection can be highly effective for garbage collection, and often exhibits better locality properties than mark-and-sweep collectors.

David F. Bacon
Proceedings of the Joint ACM Java Grande/ISCOPE Conference, pp. 68-77, Stanford, California, June 2001. Presentation.

Kava is a backward-compatible extension to Java that allows a single object model to be used consistently from the bit level on up, combining the abstraction facilities of high-level object-oriented programming languages with the ability to create highly efficient value types.

David F. Bacon, Robert E. Strom, and Ashis Tarafdar
OOPSLA'00 Conference Proceedings: Object-Oriented Systems, Languages, and Applications, ACM SIGPLAN Notices, volume 35, number 10, October 2000 (Minneapolis, Minnesota), pp. 382-400.

Guava is a dialect of Java that provides true monitors: mutual exclusion of access to shared data is guaranteed at compile-time. This frees the programmer from trying to understand complexities of the underlying memory model, while also allowing efficient compilation to weakly ordered multiprocessors.

David F. Bacon, Ravi Konuru, Chet Murthy, and Mauricio Serrano
Proceedings of the ACM Conference on Programming Language Design and Implementation (Montreal, Canada, June 1998), ACM SIGPLAN Notices volume 33 number 6, pp. 258-268.
Also appears with a retrospective in Twenty Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation: A Selection (2004), pp. 585-595.
Presentation.

High performance synchronization for Java, now incorporated into most of IBM's Java virtual machines. When implemented in the JDK, mean application speedup was 1.22, maximum speedup was 1.7. Multiprocessor scalability also improved drammatically.

David F. Bacon and Peter Sweeney
OOPSLA'96 Conference Proceedings: Object-Oriented Programming Systems, Languages, and Applications (San Jose, California, October 1996), ACM SIGPLAN Notices volume 31 number 10, pp. 324-341. Presentation.

Describes and evaluates Rapid Type Analysis, an algorithm that resolves 71% of the dynamic virtual function calls in a suite of seven C++ benchmark programs of significant size. Rapid Type Analysis also reduces compiled program size by 25%, and can be used to help the programmer understand his or her C++ program more easily.

David F. Bacon, Susan L. Graham, and Oliver Sharp
Computing Surveys, volume 26, number 4, December 1994

An encyclopedic summary of the state of the art (as of 1993) in optimizing compiler transformations for superscalar, vector, and multiprocessor computers.

David F. Bacon, Jyh-Herng Chow, Dz-ching R. Ju, Kalyan Muthukumar, and Vivek Sarkar
CASCON '94, Toronto, Canada.

An algorithm for inter- and intra-array padding that reduces cache and TLB conflicts. The algorithm also minimizes cache jamming, a new performance bottleneck we identified in CPU's capable of issuing multiple outstanding loads.

David F. Bacon and Robert E. Strom
Proceedings of the Third ACM Symposium on Principles and Practices of Parallel Programming (Williamsburg, Virginia, April 1991), SIGPLAN Notices volume 26, number 7, July 1991, pp. 155-166. Presentation.

A method for optimistically parallelizing any sequential computation in a distributed system when the result of the first part of the compuation can be guessed with reasonably high probability.

David F. Bacon and Seth Copen Goldstein
Proceedings of the ACM SIGPLAN/SIGOPS Workshop on Parallel and Distributed Debugging (Santa Cruz, California, May 1991), SIGPLAN Notices volume 26, number 12, December 1991, pp. 194-206. Presentation.

Design and simulation results for a bus-monitoring device that logs memory transactions to allow deterministic replay of parallel programs on a shared-memory multiprocessor.

David F. Bacon
Proceedings of the Tenth IEEE Symposium on Reliable Distributed Systems (Pisa, Italy, September 1991), pp. 21-30. Presentation.

Demonstrates that deterministic replay can be achieved by only logging 1% of all file system operations, by using the volatile logging technique.

Joshua Auerbach, David F. Bacon, Arthur P. Goldberg, G. Goldszmidt, Ajei Gopal, Mark Kennedy, Andy Lowry, James R. Russell, William Silverman, Robert E. Strom, Daniel M. Yellin and Shaula Yemini
Proceedings of the International Conference on Computer Languages (Oakland, California, April 1992), pp. 320-330.

Concert is a system that adds a process model (derived from Hermes) to languages like C, C++, and PL/I.

Alexander Dupuy, Jed Schwartz, Yechiam Yemini, and David F. Bacon
Communications of the ACM, volume 33, number 10, October 1990.

NEST is a network simulation tool in wide use at many industry and academic sites around the world. Includes material published previously in the Proceedings of the 1989 Winter Simulation Conference and the Winter 1988 Usenix Technical Conference.

David F. Bacon, Alexander Dupuy, Jed Schwartz, and Yechiam Yemini
USENIX Conference Proceedings, Winter 1988, Dallas, Texas, pp. 71-77.

The original paper on NEST.

David F. Bacon
Proceedings of the Fourth ACM SIGOPS European Workshop on Reliability in Distributed Systems (Bologna, Italy, September 1990), Operating Systems Review, volume 25, number 2, April 1991, pp. 1-4.

The case for using transparent recovery techniques like optimistic recovery instead of transactions.

David F. Bacon and Andy Lowry
Usenix Conference Proceedings, Summer 1990, Anaheim, California, pp. 39-50.

Describes the portable run-time system for the Hermes distributed programming language.

Arthur P. Goldberg, David F. Bacon, Ajei Gopal, Kong Li, and Robert E. Strom
Proceedings of the 1990 Usenix Mach Workshop. Also available as IBM Research Report RC 16242.

An implementation of optimistic techniques on Mach processes.

Robert E. Strom, David F. Bacon, and Shaula Yemini
Proceedings of the Eighteenth International Symposium on Fault Tolerant Computing, IEEE Computer Society, 1988. Also available as IBM Research Report RC 13373.

Deterministic replay requires logging of non-deterministic events. But many events are actually determined by other inputs, and therefore can be logged "volatilely" by using the replay capability of other processes in the system.

Robert E. Strom, Shaula Yemini, and David F. Bacon
Proceedings of the Hawaii International Conference on Systems Sciences, IEEE Computer Society, 1988.

Application of optimistic recovery techniques to a persistent object store.

Robert E. Strom, Shaula Yemini, and David F. Bacon
Proceedings of the International Conference on Parallel Processing, North-Holland, 1987.

How to integrate recovery as a fundamental operating system primitive.

Theses

David F. Bacon
Ph.D. Thesis, Computer Science Division, University of California, Berkeley, December 1997. Presentation.

An analysis algorithm for languages like C++ and Java, and a collection of optimizations driven by the analysis. This algorithm is now being used in the JAX Java code compression tool (available on alphaWorks) and in an optimizer for a future IBM C++ compiler.

David F. Bacon
M.S. Thesis, University of California, Berkeley, 1995.

We worked for a year with a group of astrophysicists to vectorize and parallelize their X-ray pulsar simulation, and sped it up by a factor of 42 on the Cray Y-MP. But we found that scaling a real-world application up to a massively parallel computer like the Thinking Machines CM-5 is not always effective. These issues are expressed in a new, more general formulation of Amdahl's Law.

Book

Robert E. Strom, David F. Bacon, Andy Lowry, Arthur P. Goldberg, Daniel M. Yellin, and Shaula Yemini
Prentice-Hall, Series in Innovative Technology, ISBN 0-13-389537-8, February 1991.

Hermes is a secure language like Java but allows fully transparent distributed computing. Hermes uses typestate in a powerful way that eliminates the need for garbage collection. A simple version of the typestate concept is used to achieve security by the Java verifier.

Magazine Articles

Oliver Sharp and David F. Bacon
Byte, volume 19 number 10, October 1994

How to use the SPEC benchmarks to make realistic and useful comparisons between different microprocessors and systems.

David F. Bacon
Byte, volume 19 number 8, August 1994

A tutorial on modern cache design and its effects on performance.

Technical Reports and Unpublished Papers

JaLA comprises vector and array class libraries coupled with a modified Java-to-bytecode compiler that adds operator overloading to the source language. The result is a high-performance array package with a clean syntax.

Download Package.

David F. Bacon
Unpublished internal IBM document (declassified).

Description of the first thin lock implementation to be delivered, including C code for various lock operations and the x86 code for inlined fast paths.

David F. Bacon, Ravi Konuru, and Chet Murthy
Unpublished internal IBM document (declassified).

Detailed evaluation of the first thin lock implementation in IBM's AIX JVM, with detailed performance studies of various uni- and multi-processor architectures.

David F. Bacon
Unpublished. Presentation.

An earlier version of Thin Locks for Java, with a fully integrated mechanism for heavy-weight locks.

David F. Bacon
Unpublished. Presentation.

Automatic transformations on pointer-intsenive programs: multi-tail recursion elimination, pointer expansion, malloc strip-mining, and others.

Robert E. Strom, David F. Bacon, Arthur P. Goldberg, Andy Lowry, Bill Silvermann, Daniel Yellin, Jim Russell, and Shaula Yemini
Technical Report, IBM T.J. Watson Research Center, March 1992.

User's manual for the Hermes implementation for Unix running on the RS/6000, Sun-4, NeXT, IBM-RT/BSD 4.3 and includes a bytecode compiler, a bytecode to C compiler and an associated run-time system.

Submitted for Publication

David F. Bacon, Clement R. Attanasio, V.T. Rajan, Stephen E. Smith, and Han B. Lee

A journal-length paper on the Recycler, a pure reference-counting garbage collector that achieves both low pause times and high performance, while using a novel design based entirely on reference counting -- even for cycle collection. The collector is fully concurrent. This article combines and extends the PLDI and ECOOP papers previously published on the Recycler, with greater algorithmic detail and complete proofs of correctness.