Richard Jones

Research Interests

My chief area of interest is dynamic memory management - this grew out of work on lazy functional programming languages and particularly their efficient implementation.

I am particularly keen to hear from potential research students with interests in memory management.

The table of contents, preface, bibliography, figures and errata are available on-line for Garbage Collection: Algorithms for Automatic Dynamic Memory Management, John Wiley & Sons, July 1996, February 1997, November 1997, January 1999, June 2000.

Novel Garbage Collection Algorithms

The Beltway framework of collectors, developed with colleagues at the Australian National University and the Universities of Massachussetts and Texas, not only generalises existing copying collectors but also makes possible the design of new collectors that outperform state of the art generational copying collectors.

The Lifetime Aware GC (LACE) project builds on Beltway to provide a novel GC framework that can flexibly exploit object lifetime analysis yet tolerates imprecision.

With Andy King, I developed a new static analysis and a novel GC framework that allows truely independent collection of thread-local heaps. In contrast to previous work, our solution safely classifies objects even in the presence of dynamic class loading, requires neither write-barriers that may do unbounded work, nor synchronisation, nor locks during thread-local collections; our analysis is sufficiently fast to permit its integration into a high-performance, production-quality virtual machine.

Visualising the Heap

Deep understanding of program behaviour is essential to the design of the next generation of garbage collectors and explicit allocators. Until now no satisfactory tools have been available to assist the implementer in gaining an understanding of heap behaviour. GCspy is an architectural framework for the collection, transmission, storage and replay of memory management behaviour. Its architecture allows easy incorporation into any memory management system: it is not limited to garbage-collected languages. It requires only small changes to the system in which it is incorporated but provides a simple to use yet powerful data-gathering API, that scales to allow very large heaps to be visualised effectively and efficiently. GCspy allows already-running, local or remote, systems to be visualised and those systems to run at full speed outside the points at which data is gathered. Its visualisation tool presents this information in a number of novel ways. GCspy is the product of an Memory Management Network collaboration between the universities of Glasgow (Tony Printezis) and Kent (Richard Jones). Screen shots can be found here.

Distributed Reference Counting

Luc Moreau, Peter Dickman and I have been investigated how to formalise distributed reference counting, starting with the Java RMI algorithm. We used our formalisation to derive an invariant-based proof of correctness of the algorithm that avoids notoriously difficult temporal reasoning. A novel graphical representation of the algorithm allows intuitive explanations, and helped uncover a bug in the original. It also extends to describe fault tolerance in a clear way..

Distributed Garbage Collection

My PhD student, Dr. Helena Rodrigues, and I used a reference listing scheme augmented by partial tracing in a garbage collector for distributed systems that can reclaim distributed, cyclic garbage data structures. The collector is designed to be flexible thereby allowing efficiency, expediency and fault-tolerance to be traded against completeness. The algorithm places no overhead on local collectors and suspends local mutators only briefly. Partial tracing of the distributed graph involves only objects thought to be part of a garbage cycle: no collaboration with other processes is required.

A taxonomy for Distributed Garbage Collection. I have also been thinking about a taxonomy for distributed garbage collection. Sylvain Louboutin correctly observed that such distributed collectors need to free themselves from the legacy of centralised collectors. A taxonomy that avoids this legacy can illuminate new areas for distributed garbage collection research. My (rather old) Microsoft Research Lecture (7/8/00) presents an outline of such a taxonomy (PowerPoint show).

the Garbage Collection Page

My Garbage Collection pages include the Garbage Collection Bibliography (a collection of over 1400 references) Garbage Collection: Algorithms for Automatic Dynamic Memory Management, the book on garbage collection links to commercial and freely available GC implementations links to other GC-related sites

The UK Memory Management Network

I am the coordinator of the UK Memory Management Network (MM-NET), an EPSRC-funded network of researchers, interested in memory management for programming languages. The project's mission is to establish collaborations between UK industrialists and academics to further research and development of advanced memory management systems.

Students

Here's what became of some of my former students:

• Andy King won first place in the graduate division of the 2003 ACM Student Research Competition for his work on Removing GC Synchronisation.
  Previously, he won the ACM SIGPLAN Student Research Competition at the Object-Oriented Programming, Systems, Languages and Applications OOPSLA'02 Conference).
  After joining Microsoft in Redmond, USA, Andy now works for VMWare in Palo Alto.
• Eric Bodden, an undergraduate project student, won the undergraduate division for 2004 for his work on a A Lightweight LTL Runtime Verification Tool for Java (conducted at the Aachen University of Technology).
• Helena Rodrigues is an Assistant Professor at Departamento de Sistemas de Informação at Universidade do Minho.
• Stephen Thomas joined the University of Nottingham as a Lecturer before moving to Insignia Solutions, where he led the garbage collection work for Insignia's Jeode Java virtual machine. He now works for ARM in Cambridge.

Lazy Functional Languages

My interest in garbage collection came from earlier work on the efficient implementation of lazy functional languages. An interesting example is the Three Instruction Machine, an abstract machine for lazy functional languages, which makes heavy demands upon the the memory management system. In particular the garbage collector must ensure that environment sharing does not lead to space leaks. Stephen Thomas and I developed an efficient and precise garbage collector tailored to the requirements of each closure (code-environment pair). The collector uses continuations to avoid all interpretive overheads and scavenges depth-first without using additional space by threading the stack through already visited environment slots.

Electronic publishing

I led the Kent team in the JISC-funded Infobike/JournalsOnline project (now ingentaJournals). The project consortium brought together publishers, librarians, computer scientists and industry to provide full-text access to journals.

Fonts and stuff I have also taught courses in Electronic Publishing and my fonts for the Z specification language are freely available for the Macintosh and Windows and can be adapted to be used with Unix. Both PostScript Type 1 and TrueType fonts are included.

• the GCspy heap visualiser.
• MetaTF: a language for specifying traces + tools for generating trace readers/writers.
• University of Kent dates in Palm datebook format. This includes a little Perl script to generate repeating, labelled and numbered events for the Palm datebook, which is probably generally useful.

• Zedfont, a Postscript and TrueType font for the Z specification language
• sd, a little bash script for comparing files under the control of various source code control systems (git, svn, cvs, sccs, rcs), allowing viewing as output from diff or gnudiff, or side by side with gvim, vdiff or opendiff.
• stripmail, a little Perl script for stripping headers off mail messages before printing them. It also handles MIME attachments (HTML with lynx, Word with antiword, etc). Useful for mail readers like exmh.
• WYC racing calendar in Palm datebook format.