I am a research scientist at Google DeepMind and professor of computer science at the Australian National University. My primary research focus is on programming language implementation. I have published in venues that specialize in programming languages, memory management, operating systems, virtual machines, computer architecture, compilers, performance analysis and software engineering. I am a Fellow of the ACM.

Project: Write Barriers and Compilers

Project: Write Barriers and Compilers

Overview

Write barriers are small snippets of code injected into the execution of a program that capture the program’s writes to pointer fields, thereby allowing the garbage collector to be aware of changes to the object graph as they happen. Two of the most well-known uses of write barriers are: a) in generational collectors were the write barrier is used to record pointers from old objects to young objects, which allows the young objects to be collected independently of the rest of the heap, and b) in reference counting collectors, were they allow the collector to generate decrements for the referents of overwritten pointers and increments for the referents of newly installed pointers. Because write barriers are injected at every pointer update, they are ubiquitous, which means they are performance-critical. Not only do they have the potential to significantly slow down the execution of a program, but they can also significantly increase the amount of code the compiler generates, slowing down the compiler and increasing pressure on the instruction cache. For this reason, it is often desirable for the compiler to implement optimizations that remove barriers when it is safe to do so. For example, if the compiler can guarantee that the source and target of a pointer are both young objects it may be able to remove a generational barrier (since the generational barrier only needs to remember old-to-young pointers).

Unfortunately, because barriers can be hard to implement within a compiler, often the barriers and any optimizations are hard-wired into the compiler. Because barriers are a powerful tool for garbage collector designers, having the barriers fixed limits creativity, and thus likely curtails the development of new and potentially better-performing collectors. This project will explore this problem and how it might be addressed. The project will examine the space of existing barriers and identify fundamental elements, and it will examine the space of optimizations and identify the assumptions on which such optimizations rest. Eventually, this project will lead to an implementation where barriers express their semantics in such a way that a compiler can infer which optimizations it may correctly apply to the barrier.

Themes

  • Garbage collection
  • Compiler optimizations

Requirements

  • Coding This project will most likely be explored in the context of the V8 and OpenJDK virtual machines and their respective compilers, which are written in C++.

  • Compilers The project is sharply focussed on the semantics of the few lines of code that comprise the write barriers, and the optimizing compilers’ treatment of them.

Project Length

Elements of this project could be tackled by and advanced undergraduate in a semester-long project. The project has enough depth that it could form the basis for a PhD.

Project Outputs

If successful, the project will change the way garbage collectors and optimizing compilers work together, producing peer reviewed publications and a solution implemented in a production-quality compiler (either OpenJDK or V8).

References