Project: Designs for Per-Object Metadata

Overview

Garbage collectors maintain a lot of metadata. Among those, an important case is per-object metadata. This is metadata that pertains to each object. There are broadly two kinds of such metadata: that owned by the language runtime (such as type information), and that owned by the GC (such as mark bits or a reference count). Metadata owned by the runtime is (by definition) not something the GC can control. This project is concerned with designs for per-object metadata owned by the GC. In our experience, one byte of GC metadata per object is sufficient to support a wide range of GC algorithms, and this project will work on that assumption. The metadata is performance-critical because it is typically accessed by write barriers (critical to mutator performance) and by the core of the GC algorithm.

Very broadly, there are three alternatives when implementing such metadata: 1) use otherwise unused space in the object’s (runtime provided) header; 2) allocate space in front of the object for storing such metadata; 3) use a data structure elsewhere in memory. Each of these approaches embodies significant tradeoffs. The first two approaches have the distinct advantage of being collocated with the object, at a fixed offset. This means both that accesses to the metadata have great spatial locality with the object, and also that the code to access them is trivial (given that the object reference is likely already in a register and the offset is constant). However, the first option comes with the significant tradeoff in that it depends entirely on their being a free byte available in the runtime-provided header, which may not be the case. The second option requires extra space to be allocated for the metadata which, given that objects usually must be allocated at least word-aligned means consuming up to one word extra per object (given typical object sizes of around 28 bytes, this may mean 4/28, or 15% overhead). The third option imposes a one-byte space penalty per object, a loss of locality and complex access instructions.

This project will conduct the first in-depth exploration of the above tradeoffs. It will use MMTk and OpenJDK. It may involve identifying new, better alternatives.

Themes

Garbage collection
Language runtimes
Performance analysis

Requirements

Coding This project involves some low-level coding, deep in the innards of a highly optimized virtual machine. OpenJDK is written in C++, MMTk is written in Rust. The project will not involve writing a lot of new code, but will require understanding some complex performance-critical code.
Analysis This project will involve running large numbers of experiments using industry-standard workloads, and then analyzing the results. We have good tools for doing this, and you will use those tools.

Project Length

The length of the project is fairly flexible—the depth and breadth of the investigation is something that can be tuned according to time constraints, experience, and enthusiasm. Given the significant cost of getting to know the relevant code base, the minimum time for this project would be one semester, half time.

Project Outputs

The project will produce code for the MMTk project. Ideally, the project will produce analysis and/or new ideas worth of a publication at ISMM.

References

This is new work. To my knowledge no one has studied this issue in the literature. I think the closest is the work done by a former PhD student, Robin Garner, on object scanning, which is a different, but related subject. Aside from that, the OpenJDK and MMTk code bases are relevant.