Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Reichenbach, Christoph LU orcid ; Immerman, Neil ; Smaragdakis, Yannis ; Aftandilian, Edward E. and Guyer, Samuel Z. (2010) In ACM SIGPLAN Notices 45(10). p.256-269
Abstract

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... (More)

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.

(Less)
Please use this url to cite or link to this publication:
author
; ; ; and
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Dominance, Garbage collector, Heap assertions, Reachability
in
ACM SIGPLAN Notices
volume
45
issue
10
pages
14 pages
publisher
Association for Computing Machinery (ACM)
external identifiers
  • scopus:79551665930
ISSN
1523-2867
DOI
10.1145/1932682.1869482
language
English
LU publication?
no
id
68c485a2-c254-47a0-9374-8775ea4219e0
date added to LUP
2019-03-29 20:20:21
date last changed
2022-02-15 17:37:39
@article{68c485a2-c254-47a0-9374-8775ea4219e0,
  abstract     = {{<p>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.</p>}},
  author       = {{Reichenbach, Christoph and Immerman, Neil and Smaragdakis, Yannis and Aftandilian, Edward E. and Guyer, Samuel Z.}},
  issn         = {{1523-2867}},
  keywords     = {{Dominance; Garbage collector; Heap assertions; Reachability}},
  language     = {{eng}},
  month        = {{10}},
  number       = {{10}},
  pages        = {{256--269}},
  publisher    = {{Association for Computing Machinery (ACM)}},
  series       = {{ACM SIGPLAN Notices}},
  title        = {{What can the GC compute efficiently? A language for heap assertions at GC time}},
  url          = {{http://dx.doi.org/10.1145/1932682.1869482}},
  doi          = {{10.1145/1932682.1869482}},
  volume       = {{45}},
  year         = {{2010}},
}