Richard Jones FBCS FRSA

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.

The Second Edition of my book The Garbage Collection Handbook: the art of automatic memory management, Richard Jones, Antony Hosking and Eliot Moss, Chapman and Hall, 2012 was released in July 2023.
The book considerably extends my earlier Garbage Collection book, in particular with complete and up-to-date coverage of parallel, concurrent, and real-time garbage collection algorithms, and explanations of some of the tricky aspects of garbage collection, including the interface to the run-time system. The Second Edition explores the latest collectors, and includes new material on finalisation, weak references, dynamic languages and GC on the GPU, and new chapters on energy efficiency and GC for persistent systems. The Handbook is also available as an e-book, with over 37,000 hyperlinks to sections, figures, algorithms, references, glossary entries and indexed items!

Garbage Collection for Multicore Systems

The EPSRC-funded MirrorGC project (September 2010 - February 2014) investigates fully concurrent garbage collection for multicore processors. Tomas Kalibera, who has a wealth of experience in automatic memory management for real-time and embedded systems, virtual machines for these systems in general, and verification of applications for these systems, Carl Ritson, who brings experience of concurrency, and in particular scheduling, Tomoharu Ugawa (Kochi University of Technology), Laurence Hellyer and Matthew Mole contributed hugely to this project.

	Transactional Sapphire: Lessons in High Performance, On-the-fly Garbage Collection. Tomoharu Ugawa, Carl G. Ritson and Richard Jones. In ACM Transactions on Programming Languages and Systems 40(4), December 2018. Constructing a high-performance garbage collector is hard. Constructing a fully concurrent 'on-the-fly', compacting collector is much more so. We describe our experience of implementing the Sapphire algorithm as the first on-the-fly, parallel, replication copying, garbage collector for the Jikes RVM Java virtual machine. In part, we explain our innovations such as copying with hardware and software transactions, on-the-fly management of Java's reference types and simple, yet correct, lock-free management of volatile fields in a replicating collector. We fully evaluate, for the first time, and using realistic benchmarks, Sapphire's performance and suitability as a low latency collector. An important contribution of this work is a detailed description of our experience of building an on-the-fly copying collector for a complete JVM with some assurance that it is correct. A key aspect of this is model checking of critical components of this complicated and highly concurrent system.
	Model Checking Transactional Sapphire. Tomoharu Ugawa and Richard Jones. University of Kent Technical report, May 2018.
	Building high performance, fully concurrent garbage collectors with confidence. Richard Jones. In Virtual Machines Summer School 2016, Cumberland Lodge, UK. [slides ppt] [slides pdf] [video]
	Exploring Garbage Collection with Haswell Hardware Transactional Memory. Carl G. Ritson, Tomoharu Ugawa and Richard Jones. In International Symposium on Memory Management (ISMM). ACM 2014. [slides]
	Reference Object Processing in On-The-Fly Garbage Collection. Tomoharu Ugawa, Richard Jones and Carl G. Ritson. In International Symposium on Memory Management (ISMM). ACM 2014. [slides]
	Rigorous Benchmarking in Reasonable Time. Tomas Kalibera and Richard Jones. In International Symposium on Memory Management (ISMM). ACM 2013.
	A Black-box Approach to Understanding Concurrency in DaCapo. Tomas Kalibera, Matthew Mole, Richard Jones and Jan Vitek. In Object Oriented Programmig, Systems, Languages and Applications (OOPSLA). ACM 2012.
	Handles Revisited: Optimising Performance and Memory Costs in a Real-time Collector. Tomas Kalibera, Richard Jones. In International Symposium on Memory Management (ISMM). ACM 2011.
	The Locality of Concurrent Write Barriers Laurence Hellyer, Richard Jones, Antony L. Hosking. In International Symposium on Memory Management (ISMM). ACM 2010

Improving Experimental Evaluation

	Progress in computer systems research is driven by experimental evaluation. Our community can only make advances when new systems can be shown to improve over earlier ones. Unfortunately, as our paper ISMM'13 shows, computer science lags far behind other disciplines. Fortunately, it also shows that we can perform rigorous experiments within a reasonable budget of experimentation time.
	Rigorous Benchmarking in Reasonable Time. Tomas Kalibera and Richard Jones. In ISMM'13, International Symposium on Memory Management. ACM 2013 (Note: this version corrects the ISMM version). See also Virtual Machine Warmup Blows Hot and Cold, Barrett et al, OOPSLA 2017, which confirms and extends these findings. Quantifying Performance Changes with Effect Size Confidence Intervals. Tomas Kalibera and Richard Jones. Technical report, University of Kent.
	We encourage researchers to help us improve the standard of experimental evaluation.
	Read The Truth, the Whole Truth, and Nothing but the Truth: A Pragmatic Guide to Assessing Empirical Evaluations. Stephen M Blackburn, Amer Diwan, Mattias Hauswirth, Peter F Sweeney, Jose Nelson Amaral, Tim Brecht, Lubomr Bulej, Cliff Click, Lieven Eeckhout, Sebastian Fischmeister, Daniel Frampton, Laurie J Hendren, Michael Hind, Antony L Hosking, Richard Jones, Tomas Kalibera, Nathan Keynes, Nathaniel Nystrom and Andreas Zeller. ACM Transactions on Programming Languages and Systems (TOPLAS), 38 (4), 2016. Read Repeatability, Reproducibility and Rigor in Systems Research. Jan Vitek and Tomas Kalibera. EMSOFT'11, International Conference on Embedded Software. IEEE 2011. Visit the Evaluate Collaboratory, a resource and a hub for everybody interested in understanding and improving the state of practice in experimental evaluation. Sign the Letter to PC chairs, arguing the importance of observation and reproduction studies.

Novel Garbage Collection Algorithms

The Beltway framework of collectors, developed with colleagues at the Australian National University and the Universities of Massachusetts 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 3400 references) The Garbage Collection Handbook: the art of automatic memory management, the second edition of the modern book on garbage collection was published in June 2023.

Students & post-docs

Here's what became of some of my former students and post-docs:
 

• Carl Ritson went to work for a start-up, RSRCHXchange.
• Matthew Mole works for Kent Police.
• Laurence Hellyer works for Smith & Williamson, a financial services company.
• Tomas Kalibera is working with Oracle and Purdue University on the R statistics language in Prague.
• Chris Ryder went to work in one of ARM's compiler groups in Cambridge.
• Sebastien Marion founded Comufy, providing novel ways for businesses to communicate with their customers.
• Andy King won first place in the graduate division of the 2003 ACM Student Research Competition for his work on Removing GC Synchronisation. After joining Microsoft in Redmond, USA, Andy now works for VMWare in Palo Alto. [thesis]
• 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). Following a PhD at McGill, he now heads the Secure Software Engineering Group at the European Centre for Security and Privacy by Design (EC SPRIDE).
• Helena Rodrigues is an Assistant Professor at Departamento de Sistemas de Informaçao at Universidade do Minho. [thesis]
• Stephen Thomas joined the University of Nottingham as a Lecturer before moving to Insignia Solutions, where he led the GC work for Insignia's Jeode JVM. He now works for Intel 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.
•  dates in formats suitable for most smart phones, Google calendar, etc. This includes a little Perl script to generate repeating, labelled and numbered events, which is probably generally useful.
•  WYC racing calendar in a format suitable for import into iCal, Google Calendar or Outlook.
• MetaTF: a language for specifying traces + tools for generating trace readers/writers.
•  Once upon a time, back in 1999...

• 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.