What can the GC compute efficiently? A language for heap assertions at GC time

Research output: Contribution to journalArticle


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 ordersof-magnitude higher costs.


External organisations
  • University of Massachusetts System
  • Tufts University
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science


  • Dominance, Garbage collector, Heap assertions, Reachability
Original languageEnglish
Pages (from-to)256-269
Number of pages14
JournalACM SIGPLAN Notices
Issue number10
Publication statusPublished - 2010 Oct 1
Publication categoryResearch
Externally publishedYes