What Can the GC Compute Efficiently? A Language for Heap Assertions at GC Time

Christoph Reichenbach (University of Massachusetts), Neil Immerman (University of Massachusetts), Yannis Smaragdakis (University of Massachusetts), Edward Aftandilian (Tufts University), Samuel Z. Guyer (Tufts University)

We present the DeAL language for heap assertions that are efficiently evaluated during garbage collection time. DeAL is a rich, declarative, logic-based language whose programs are guaranteed to be executable with good whole-heap locality, i.e., within a single traversal over every live object on the heap and a finite neighborhood around each object. As a result, evaluating DeAL programs incurs negligible cost: for simple assertion checking at each garbage collection, the end-to-end execution slowdown is below 2%. DeAL is integrated into Java as a VM extension and we demonstrate its efficiency and expressiveness with several applications and properties from the past literature.

Compared to past systems for heap assertions, DeAL is distinguished by its very attractive expressiveness/efficiency tradeoff: it offers a significantly richer class of assertions than what past systems could check with a single traversal. Conversely, past systems that can express the same (or more) complex assertions as DeAL do so only by suffering orders-of-magnitude higher costs.


Source code

Below are the source code patches needed to reproduce our experiments. The first diff contains the relevant runtime system modifications, the second diff contains the modifications needed for the compiler. Both diffs contain README files with instructions for how to set up and run the experiments. Also, both diffs contain unit tests, to be run through the included Makefiles. Make sure to chmod u+x *.sh before running the tests, so that the helper scripts can function properly. If you have any questions, please feel free to contact me at cs.umass.edu as creichen.