CACM

In Defense of Soundiness: A Manifesto

Ben Livshits, Manu Sridharan, Yannis Smaragdakis, Ondrej Lhotak, J. Nelson Amaral, Bor-Yuh Evan Chang, Sam Guyer, Uday Khedker, Anders Moller, and Dimitrios Vardoulakis

Paper: [PDF]

SIGCSE 2014

Metaphors We Teach By

Joseph P. Sanford, Aaron Tietz, Saad Farooq, Samuel Z. Guyer, R. Benjamin Shapiro

Paper: [PDF]

Abstract:

InfoVis 2013

Heapviz: Interactive Heap Visualization for Program Understanding and Debugging

Sean Kelley, Edward Aftandilian, Connor Gramazio, Nathan P. Ricci, Sara L. Su, Samuel Z. Guyer

Paper: [PDF]

Abstract:

ISMM 2013

Elephant Tracks: Portable Production of Complete and Precise GC Traces

Nathan P. Ricci, Samuel Z. Guyer, J. Eliot B. Moss

Paper: [PDF]

Software: Elephant tracks page

Abstract:

We present Elephant Tracks (ET), a dynamic program analysis tool for Java that produces detailed traces of garbage collection-related events, including object allocations, object deaths, and pointer updates. Like prior work, our tracing tool is based on the Merlin algorithm [6,7], but offers several substantial new capabilities. First, it is much more precise than previous tools: it traces method entries and exits and measures time in terms of them, allowing it to place events precisely in the context of the program structure. Second, it is implemented using a combination of JVM Tool Interface (JVMTI)[13] callbacks and bytecode rewriting, and works with any standard JVM. Finally, it produces complete traces, including weak references, events from the Java Native Interface and sun.misc.Unsafe, and VM start up objects. In this paper we also explore the general design space of tracing tools, and carefully define the execution model that the traces represent.

VISSOFT 2013

Visualizing the Allocation and Death of Objects

Raoul L. Veroy, Nathan P. Ricci, Samuel Z. Guyer

Paper: [PDF]

Abstract:

We present memory allocation and death plots, a visualization technique for showing both which method an object is allocated in a Java program, and in which method that object eventually dies. This relates the place in a program’s execution where memory is first used to the place it is no longer used, thus helping the programmer to better understand the memory behavior of a program.

ISMM 2012

new Scala() instance of Java: a comparison of the memory behaviour of Java and Scala programs

Andreas Sewe, Mira Mezini, Aibek Sarimbekov, Danilo Ansaloni, Walter Binder, Nathan P. Ricci, Samuel Z. Guyer

Paper: [PDF]

Abstract:

OOPSLA 2011

Asynchronous Assertions

Edward E. Aftandilian, Samuel Z. Guyer, Martin Vechev, Eran Yahav

Paper: [PDF]

Abstract:

Assertions are a familiar and widely used bug detection technique. Traditional assertion checking, however, is performed synchronously, imposing its full cost on the runtime of the program. As a result, many useful kinds of checks, such as data structure invariants and heap analyses, are impractical because they lead to extreme slowdowns.

We present a solution that decouples assertion evaluation from program execution: assertions are checked <>asynchronously by separate checking threads while the program continues to execute. Our technique guarantees that asynchronous evaluation always produces the same result as synchronous evaluation, even if the program concurrently modifies the program state. The checking threads evaluate each assertion on a consistent snapshot of the program state as it existed at the moment the assertion started.

We implemented our technique in a system called Strobe, which supports asynchronous assertion checking in both single-and multi-threaded Java applications. Strobe runs inside the Java virtual machine and uses copy-on-write to construct snapshots incrementally, on-the-fly. Our system includes all necessary synchronization to support multiple concurrent checking threads, and to prevent data races with the main program threads. We find that asynchronous checking significantly outperforms synchronous checking, incurring tolerable overheads -- in the range of 10% to 50% over no checking at all -- even for heavy-weight assertions that would otherwise result in crushing slowdowns.

IV 2011

Heapviz: Interactive Heap Visualization for Program Understanding and Debugging

Sean Kelley, Edward E. Aftandilian, Connor Gramazio, Nathan Ricci, Sara L. Su, and Samuel Z. Guyer

Paper: [PDF]

Abstract:

Understanding the data structures in a program is crucial to understanding how the program works, or why it doesn't work. Inspecting the code that implements the data structures, however, is an arduous task and often fails to yield insights into the global organization of a program's data. Inspecting the actual contents of the heap solves these problems but presents a significant challenge of its own: finding an effective way to present the enormous number of objects it contains.

In this paper we present Heapviz, a tool for visualizing and exploring snapshots of the heap obtained from a running Java program. Unlike existing tools, such as traditional debuggers, Heapviz presents a global view of the program state as a graph, together with powerful interactive capabilities for navigating it. Our tool employs several key techniques that help manage the scale of the data. First, we reduce the size and complexity of the graph by using algorithms inspired by static shape analysis to aggregate the nodes that make up a data structure. Second, we implement a powerful visualization component whose interactive interface provides extensive support for exploring the graph. The user can search for objects based on type, connectivity, and field values; group objects; and color or hide and show each group. The user may also inspect individual objects to see their field values and neighbors in the graph. These interactive abilities help the user manage the complexity of these huge graphs.

By applying Heapviz to both constructed and real-world examples, we show that Heapviz provides programmers with a powerful and intuitive tool for exploring program behavior.

OOPSLA 2010

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

Christof Reichenbach, Neil Immerman, Yannis Smaragdakis, Eddie Aftandilian, Samuel Z. Guyer.

Paper: [PDF]

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 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.

SOFTVIS 2010

Heapviz: Interactive Heap Visualization for Program Understanding and Debugging

Eddie Aftandilian, Sean Kelley, Connor Gramazio, Nathan Ricci, Sara Su, and Samuel Z. Guyer

Paper: [PDF]

Abstract:

Understanding the data structures in a program is crucial to understanding how the program works, or why it doesn't work. Inspecting the code that implements the data structures, however, is an arduous task and often fails to yield insights into the global organization of a program's data. Inspecting the actual contents of the heap solves these problems but presents a significant challenge of its own: finding an effective way to present the enormous number of objects it contains.

In this paper we present Heapviz, a tool for visualizing and exploring snapshots of the heap obtained from a running Java program. Unlike existing tools, such as traditional debuggers, Heapviz presents a global view of the program state as a graph, together with powerful interactive capabilities for navigating it. Our tool employs several key techniques that help manage the scale of the data. First, we reduce the size and complexity of the graph by using algorithms inspired by static shape analysis to aggregate the nodes that make up a data structure. Second, we introduce a dominator-based layout scheme that emphasizes hierarchical containment and ownership relations. Finally, the interactive interface allows the user to expand and contract regions of the heap to modulate data structure detail, inspect individual objects and field values, and search for objects based on type or connectivity. By applying Heapviz to both constructed and real-world examples, we show that Heapviz provides programmers with a powerful and intuitive tool for exploring program behavior.

PLDI 2010

Breadcrumbs: Efficient Context Sensitivity for Dynamic Bug Detection Analyses

Michael D. Bond, Graham Z. Baker, and Samuel Z. Guyer

Paper: [PDF]

Abstract:

Calling context---the set of active methods on the stack---is critical for understanding the dynamic behavior of large programs. Dynamic program analysis tools, however, are almost exclusively context insensitive because of the prohibitive cost of representing calling contexts at run time. Deployable dynamic analyses, in particular, have been limited to reporting only static program locations.

This paper presents Breadcrumbs, an efficient technique for recording and reporting dynamic calling contexts. It builds on an existing technique for computing a compact (one word) encoding of each calling context that client analyses can use in place of a program location. The key feature of our system is a search algorithm that can reconstruct a calling context from its encoding using only a static call graph and a small amount of dynamic information collected at cold (infrequently executed) callsites. Breadcrumbs requires no offline training or program modifications, and handles all language features, including dynamic class loading.

We use Breadcrumbs to add context sensitivity to two dynamic analyses: a data-race detector and an analysis for diagnosing null pointer exceptions. On average, it adds 10% to 20% runtime overhead, depending on a tunable parameter that controls how much dynamic information is collected. Collecting less information lowers the overhead, but can result in a search space explosion. In some cases this causes reconstruction to fail, but in most cases Breadcrumbs produces nontrivial calling contexts that have the potential to significantly improve both the precision of the analyses and the quality of the bug reports.

PLDI 09

GC Assertions: Using the Garbage Collector to Check Heap Properties

Edward Aftandilian and Samuel Z. Guyer

Paper: [PDF]

This is an expanded version of our MSPC 2008 paper.

CACM 2008

Wake Up and Smell the Coffee: Evaluation Methodology for the 21st Century

Blackburn et al.

Paper: [PDF]

Abstract:

Evaluation methodology underpins all innovation in experimental computer science. It requires relevant workloads, appropriate experimental design, and rigorous analysis. Unfortunately, methodology is not keeping pace with the changes in our field. The rise of managed languages such as Java, C#, and Ruby in the past decade and the imminent rise of commodity multicore architectures for the next de- cade pose new methodological challenges that are not yet widely understood. This paper explores the consequences of our collective inattention to methodology on innovation, makes recommendations for addressing this problem in one domain, and provides guidelines for other domains. We describe benchmark suite design, experimental design, and analysis for evaluating Java applications. For example, we introduce new criteria for measuring and selecting di- verse applications for a benchmark suite. We show that the complexity and nondeterminism of the Java runtime system make experimental design a first-order consideration, and we recommend mechanisms for addressing complexity and nondeterminism. Drawing on these results, we suggest how to adapt methodology more broadly. To continue to deliver innovations, our field needs to significantly increase partici- pation in and funding for developing sound methodological foundations.

OOPSLA 07

Tracking Bad Apples: Reporting the Origin of Null and Undefined Value Errors

Michael D. Bond, Nicholas Nethercote, Stephen W. Kent, Samuel Z. Guyer, and Kathryn S. McKinley

Paper: [PDF]

Abstract:

Programs sometimes crash due to unusable values, for example, when Java and C# programs dereference null pointers and when C and C++ programs use undefined values to affect program behavior. A stack trace produced on such a crash identifies the effect of the unusable value, not its cause, and is often not much help to the programmer.

This paper presents efficient origin tracking of unusable values; it shows how to record where these values come into existence, correctly propagate them, and report them if they cause an error. The key idea is value piggybacking: when the original program stores an unusable value, value piggybacking instead stores origin information in the spare bits of the unusable value. Modest compiler support alters the program to propagate these modified values through operations such as assignments and comparisons. We evaluate two implementations: the first tracks null pointer origins in a JVM, and the second tracks undefined value origins in a memory-checking tool built with Valgrind. These implementations show that origin tracking via value piggybacking is fast and often useful, and in the Java case, has low enough overhead for use in a production environment.

TFP 07

Bytecode Verification for Haskell

Rob Dockins and Samuel Z. Guyer

Paper: [PDF]

Abstract:

In this paper we present a method for verifying Yhc bytecode, an intermediate form of Haskell suitable for mobile code applications. We examine the issues involved with verifying Yhc bytecode programs, and we present a proof-of-concept bytecode compiler and verifier.

Verification is a static analysis which ensures that a bytecode program is type-safe. The ability to check type-safety is important for mobile code situations where un- trusted code may be executed. Type-safety subsumes the critical memory-safety property and excludes important classes of exploitable bugs, such as buffer over- flows. Haskell's rich type system also allows programmers to build effective, static security policies and enforce them using the type checker. Verification allows us to be confident the constraints of our security policy are enforced.

OOPSLA 06

The DaCapo Benchmarks: Java Benchmarking Development and Analysis

with Steve Blackburn et al.

Paper: [PDF]

Abstract:

Since benchmarks drive computer science research and industry product development, which ones we use and how we evaluate them are key questions for the community. Despite complex runtime tradeoffs due to dynamic compilation and garbage collection required for Java programs, many evaluations still use methodologies developed for C, C++, and Fortran. SPEC, the dominant purveyor of benchmarks, compounded this problem by institutionalizing these methodologies for their Java benchmark suite. This paper recommends benchmarking selection and evaluation methodologies, and introduces the DaCapo benchmarks, a set of open source, client-side Java benchmarks. We demonstrate that the complex interactions of (1) architecture, (2) compiler, (3) virtual machine, (4) memory management, and (5) application require more extensive evaluation than C, C++, and Fortran which stress (4) much less, and do not require (3). We use and introduce new value, time-series, and statistical metrics for static and dynamic properties such as code complexity, code size, heap composition, and pointer mutations. No benchmark suite is definitive, but these metrics show that DaCapo improves over SPEC Java in a variety of ways, including more complex code, richer object behaviors, and more demanding memory system requirements. This paper takes a step towards improving methodologies for choosing and evaluating benchmarks to foster innovation in system design and implementation for Java and other managed languages.

PLDI 06

Free-Me: A Static Analysis for Automatic Individual Object Reclamation

Samuel Z. Guyer, Kathryn S. McKinley and Daniel Frampton

Also see complete results graphs for mark/sweep and GenMS collectors.

Paper: [PDF]

Abstract:

Garbage collection has proven benefits, including fewer memory-related errors and reduced programmer effort. Garbage collection, however, trades space for time. It reclaims memory only when it is invoked: invoking it more frequently reclaims memory quickly, but incurs a significant cost; invoking it less frequently fills memory with dead objects. In contrast, explicit memory management provides prompt low cost reclamation, but at the expense of programmer effort.

This work comes closer to the best of both worlds by adding novel compiler and runtime support for compiler inserted frees to a garbage-collected system. The compiler's free-me analysis identifies when objects become unreachable and inserts calls to free. It combines a lightweight pointer analysis with liveness information that detects when short-lived objects die. Our approach differs from stack and region allocation in two crucial ways. First, it frees objects incrementally exactly when they become unreachable, instead of based on program scope. Second, our system does not require allocation-site lifetime homogeneity, and thus frees objects on some paths and not on others. It also handles common patterns: it can free objects in loops and objects created by factory methods.

We evaluate free() variations for free-list and bump-pointer allocators. Explicit freeing improves performance by promptly reclaiming objects and reducing collection load. Compared to mark-sweep alone, free-me cuts total time by 22% on average, collector time by 50% to 70%, and allows programs to run in 17% less memory. This combination retains the software engineering benefits of garbage collection while increasing space efficiency and improving performance, and thus is especially appealing for real-time and space constrained systems.

CC 06

Efficient Flow-Sensitive Interprocedural Data-flow Analysis in the Presence of Pointers

Teck Bok Tok, Samuel Z. Guyer and Calvin Lin

Paper: [PDF]

Abstract:

This paper presents a new worklist algorithm that significantly speeds up a large class of flow-sensitive data-flow analyses, including typestate error checking and pointer analysis. Our algorithm works particularly well for inter- procedural analyses. By contrast, traditional algorithms work well for individual procedures but do not scale well to interprocedural analysis because they spend too much time unnecessarily re-analyzing large parts of the program. Our algo- rithm solves this problem by exploiting the sparse nature of many analyses. The key to our approach is the use of interprocedural def-use chains, which allows our algorithm to re-analyze only those parts of the program that are affected by changes in the flow values. Unlike other techniques for sparse analysis, our algo- rithm does not rely on precomputed def-use chains, since this computation can itself require costly analysis, particularly in the presence of pointers. Instead, we compute def-use chains on the fly during the analysis, along with precise pointer information. When applied to large programs such as nn, our techniques im- prove analysis time by up to 90% -- from 1974s to 190s -- over a state of the art algorithm.

SCP 05

Error Checking with Client-Driven Pointer Analysis

Samuel Z. Guyer and Calvin Lin

Science of Computer Programming, Special Issue on the Static Analysis Symposium 2003

Paper: [Postscript] [PDF]

Abstract:

This paper presents a new client-driven pointer analysis algorithm that automatically adjusts its precision in response to the needs of client analyses. Using five significant error detection problems as clients, we evaluate our algorithm on 18 real C programs. We compare the accuracy and performance of our algorithm against several commonly-used fixed-precision algorithms. We find that the client-driven approach effectively balances cost and precision, often producing results as accurate as fixed-precision algorithms that are many times more costly. Our algorithm works because many client problems only need a small amount of extra precision applied to selected portions of each input program.

OOPSLA 04

Finding Your Cronies: Static Analysis for Dynamic Object Colocation

Samuel Z. Guyer and Kathryn S. McKinley

Paper: [PDF][Slides]

Abstract:

This paper introduces dynamic object colocation, an optimization to reduce copying costs in generational and other incremental garbage collectors by allocating connected objects together in the same space. Previous work indicates that connected objects belong together because they often have similar lifetimes. Generational collectors, however, allocate all new objects in a nursery space. If these objects are connected to data structures residing in the mature space, the collector must copy them. Our solution is a cooperative optimization that exploits compiler analysis to make runtime allocation decisions. The compiler analysis discovers potential object connectivity for newly allocated objects. It then replaces these allocations with calls to coalloc, which takes an extra parameter called the colocator object. At runtime, coalloc() determines the location of the colocator and allocates the new object together with it in either the nursery or mature space. Unlike pretenuring, colocation makes precise per-object allocation decisions and does not require lifetime analysis or allocation site homogeneity. Experimental results for SPEC Java benchmarks using JikesRVM show colocation can reduce garbage collection time by 50% to 75%, and total performance by up to 10%.

IEEE 04

Broadway: A Compiler for Exploiting the Domain-Specific Semantics of Software Libraries

Samuel Z. Guyer Calvin Lin

Proceedings of the IEEE: Special Issue on Program Generation, Optimization, and Platform Adaptation

Paper: [Postscript] [PDF]

Abstract:

This paper describes the Broadway compiler and our experiences using it to support domain-specific compiler optimizations. Our goal is to provide compiler support for a wide range of domains and to do so in the context of existing programming languages. Therefore we focus on a technique that we call library-level optimization, which recognizes and exploits the domain-specific semantics of software libraries. The key to our system is a separation of concerns: compiler expertise is built into the Broadway compiler machinery, while domain expertise resides in separate annotation files that are provided by domain experts. We describe how this system can optimize parallel linear algebra codes written using the PLAPACK library. We find that our annotations effectively capture PLAPACK expertise at several levels of abstraction, and that our compiler can automatically apply this expertise to produce considerable performance improvements. Our approach shows that the abstraction and modularity found in modern software can be as much as asset to the compiler as it is to the programmer.

SAS 03

Client-Driven Pointer Analysis

Samuel Z. Guyer and Calvin Lin

June 2003 with FCRC '03.

Paper: [Postscript] [PDF] [Slides]

Abstract:

This paper presents a new client-driven pointer analysis algorithm that automatically adjusts its precision in response to the needs of client analyses. We evaluate our algorithm on 18 real C programs, using five significant error detection problems as clients. We compare the accuracy and performance of our algorithm against several commonly-used fixed-precision algorithms. We find that the client-driven approach effectively balances cost and precision, often producing results as accurate as fixed-precision algorithms that are many times more costly. Our algorithm works because many client problems only need a small amount of extra precision applied to the right places in each input program.

Dissertation

Incorporating Domain-Specific Information into the Compilation Process

Advisor: Calvin Lin

May 2003

Paper: [Postscript] [PDF] [Slides]

Abstract:

Despite many advances in compiler research, traditional compilers continue to suffer from one significant limitation: they only recognize the low-level primitive constructs of their languages. In contrast, programmers increasingly benefit from higher level software components, which implement a variety of specialized domains---everything from basic file access to 3D graphics and parallel programming. The result is a marked difference between the level of abstraction in software development and the level of abstraction in compilation.

In this thesis we present the Broadway compiler, which closes this gap. Broadway represents a new kind of compiler, called a library-level compiler, that supports domain-specific compilation by extending the benefits of compiler support to software libraries. The key to our approach is a separate annotation language that conveys domain-specific information about libraries to our compiler, allowing it to treat library routines more like built-in language operations. Using this information, the compiler can perform library-level program analysis and apply library-level optimizations.

We explore both the opportunities and challenges presented by library-level compilation. We show that library-level optimizations can increase the performance of several parallel programs written using a highly-tuned parallel linear algebra library. These high-level optimizations are beyond the capabilities of a traditional compiler and even rival the performance of programs hand-coded by an expert. We also show that our compiler is an effective tool for detecting a range of library-level errors, including several significant security vulnerabilities. Finally, we present a new client-driven pointer analysis algorithm, which provides precise and scalable program analysis to meet the demanding requirements of library-level compilation.

UTCS TR-02-04

Detecting Errors with Configurable Whole-Program Dataflow Analysis

Samuel Z. Guyer, Emery D. Berger and Calvin Lin

Paper: [PDF]

Abstract:

Broadway: A Software Architecture for Scientific Computing

Samuel Z. Guyer and Calvin Lin

R. F. Boisvert and P. T. P. Tang Editors. Kluwer Academic Press, 2000.

The Architecture of Scientific Software.

Paper: [Postscript] [PDF]

Abstract:

LCPC 00

Optimizing the Use of High Performance Libraries

Samuel Z. Guyer and Calvin Lin

Paper: [Postscript] [PDF] [Slides]

Abstract:

This paper describes how the use of software libraries, which is prevalent in high performance computing, can benefit from compiler optimizations in much the same way that conventional programming languages do. We explain how the compilation of these informal languages differs from the compilation of more conventional languages. In particular, such compilation requires precise pointer analysis, domain-specific information about the library's semantics, and a configurable compilation scheme. We describe a solution that combines dataflow analysis and pattern matching to perform configurable optimizations.

DSL 99

An Annotation Language for Optimizing Software Libraries

Samuel Z. Guyer and Calvin Lin

October 1999.

Paper: [Postscript] [PDF]

Abstract:

This paper introduces an annotation language and a compiler that together can customize a library implementation for specific application needs. Our approach is distinguished by its ability to exploit high level, domain-specific information in the customization process. In particular, the annotations provide semantic information that enables our compiler to analyze and optimize library operations as if they were primitives of a domain-specific language. Thus, our approach yields many of the performance benefits of domain-specific languages, without the effort of developing a new compiler for each domain. This paper presents the annotation language, describes its role in optimization, and illustrates the benefits of the overall approach. Using a partially implemented compiler, we show how our system can significantly improve the performance of two applications written using the PLAPACK parallel linear algebra library.