Contract Soundness for Object-Oriented Languages

10/16 10:30 - 11:00 | Convention Center Ballroom A
Checking pre- and post-conditions of procedures and methods at runtime helps improve software reliability. In the procedural world, pre- and post-conditions have a straightforward interpretation. If a procedure's pre-condition doesn't hold, the caller failed to establish the proper context. If a post-condition doesn't hold, the procedure failed to compute the expected result. In the object-oriented world, checking pre- and post-conditions for methods, often called "contracts" in this context, poses complex problems. Because methods may be overridden, it is not sufficient to check only pre- and post-conditions. In addition, the contract hierarchy must be checked to ensure that the contracts on overridden methods are properly related to the contracts on overriding methods. Otherwise, a class hierarchy may violate the substitution principle; that is, it may no longer be true that an instance of a class is substitutable for objects of the superclass. In this paper, we study the problem of contract enforcement in an object-oriented world from a foundational perspective. More specifically, we study contracts as refinements of types. Pushing the analogy further, we state and prove a contract soundness theorem that captures the essential properties of contract enforcement. We use the theorem to illustrate how most existing tools suffer from a fundamental flaw and how they can be improved.
Authors: Robert Bruce Findler, Rice University, Matthias Felleisen, Rice University and Northeastern University

A Core Calculus for Java Exceptions

10/16 11:00 - 11:30 | Convention Center Ballroom A
In this paper we present a simple calculus (called CJE) in order to fully investigate the exception mechanism of Java, and in particular its interaction with inheritance, which turns out to be nontrivial. Moreover, we show that the type system for the calculus directly driven by the Java Language Specification (called "Full") uses too many types, in the sense that there are different types which provide exactly the same information. Hence, we obtain from Full a simplified type system called "Min" where equivalent types have been identified. We show that this is useful both for type-checking optimization and for clarifying the static semantics of the language. The two type systems are proved to satisfy the subject reduction property.
Authors: Davide Ancona, DISI - Universitý di Genova, Giovanni Lagorio, DISI - Universitý di Genova, Elena Zucca, DISI - Universitý di Genova

The Java Syntactic Extender

10/16 11:30 - 12:00 | Convention Center Ballroom A
The ability to extend a language with new syntactic forms is a powerful tool. A sufficiently flexible macro system allows programmers to build from a common base towards a language designed specifically for their problem domain. However, macro facilities that are integrated, capable, and at the same time simple enough to be widely used have been limited to the Lisp family of languages to date. In this paper we introduce a macro facility, called the Java Syntactic Extender (JSE), with the superior power and ease of use of Lisp macro systems, but for Java, a language with a more conventional algebraic syntax. The design is based on the Dylan macro system, but exploits Java's compilation model to offer a full procedural macro engine. In other words, syntax expanders may be implemented in, and so use all the facilities of, the full Java language.
Authors: Jonathan Bachrach, MIT AI Lab, Keith Playford, Functional Objects, Inc.

Points-To Analysis for Java using Annotated Constraints

10/16 13:30 - 14:00 | Convention Center Ballroom A
The goal of points-to analysis for Java is to determine the set of objects pointed to by a reference variable or a reference object field. This information has a wide variety of client applications in optimizing compilers and software engineering tools. In this paper we present a points-to analysis for Java based on Andersen's points-to analysis for C. We implement the analysis by using a constraint-based approach which employs annotated inclusion constraints. Constraint annotations allow us to model precisely and efficiently the semantics of virtual calls and the flow of values through object fields. By solving systems of annotated inclusion constraints, we have been able to perform practical and precise points-to analysis for Java. We evaluate the performance of the analysis on a large set of Java programs. Our experiments show that the analysis runs in practical time and space. We also show that the points-to solution has significant impact on clients such as object read-write information, call graph construction, virtual call resolution, synchronization removal, and stack-based object allocation. Our results demonstrate that the analysis is a realistic candidate for a relatively precise, practical, general-purpose points-to analysis for Java.
Authors: Atanas Rountev, Rutgers University, Ana Milanova, Rutgers University, Barbara G. Ryder, Rutgers University

A Study of Exception Handling and Its Dynamic Optimization in Java

10/16 13:30 - 14:00 | Convention Center Ballroom D
Optimizing exception handling is critical for programs that frequently throw exceptions. We observed that there are many such exception-intensive programs in various categories of Java programs. There are two commonly used exception handling techniques: stack unwinding and stack cutting. Stack unwinding optimizes the normal path, while stack cutting optimizes the exception handling path. However, there has been no single exception handling technique to optimize both paths. We propose a new technique called Exception-Directed Optimization (EDO), which optimizes exception-intensive programs without slowing down exception-minimal programs. EDO, a feedback-directed dynamic optimization, consists of three steps: exception path profiling, exception path inlining, and throw elimination. Exception path profiling attempts to detect hot exception paths. Exception path inlining compiles the catching method in a hot exception path, inlining the rest of methods in the path. Throw elimination replaces a throw with the explicit control flow to the corresponding catch. We implemented EDO in IBM's production Just-In-Time compiler, and obtained the experimental results, which show that, in SPECjvm98, it improved performance of exception-intensive programs by up to 18.3% without affecting performance of exception-minimal programs at all.
Authors: Takeshi Ogasawara, IBM Tokyo Research Laboratory, Hideaki Komatsu, IBM Tokyo Research Laboratory, Toshio Nakatani, IBM Tokyo Research Laboratory

A Parameterized Type System for Race-Free Java Programs

10/16 14:00 - 14:30 | Convention Center Ballroom A
This paper presents a new static type system for multithreaded programs; any well-typed program in our system is free of data races. Our type system is significantly more expressive than previous such type systems. In particular, our system lets programmers write generic code to implement a class, then create different objects of the same class that have different protection mechanisms. This flexibility enables programmers to reduce the number of unnecessary synchronization operations in a program without risking data races. We also support default types which reduce the burden of writing the extra type annotations. Our experience indicates that our system provides a promising approach to make multithreaded programs more reliable and efficient.
Authors: Chandrasekhar Boyapati, MIT, Martin Rinard, MIT

Efficient Subtyping Tests with PQ-Encoding

10/16 14:00 - 14:30 | Convention Center Ballroom D
Subtyping tests, i.e., determining whether one type is a subtype of another, are a frequent operation during the execution of object-oriented programs. The challenge is in encoding the hierarchy in a small space, while simultaneously making sure that subtyping tests have efficient implementation. We present a new scheme for encoding multiple and single inheritance hierarchies, which, in the standardized hierarchies, reduces the footprint of all previously published schemes. The scheme is called PQ-encoding after PQ-trees, a data structure previously used in graph theory for finding the orderings that satisfy a collection of constraints. In particular, we show that in the traditional object layout model, the extra memory requirements for single inheritance hierarchies is zero. In the PQ-encoding subtyping tests are constant time, and use only two comparisons. Other than PQ-trees, PQ-encoding uses several novel optimization techniques. These techniques are applicable also in improving the performance of other, previously published, encoding schemes.
Authors: Yoav Zibin, Technion, Joseph (Yossi) Gil, Technion

Object Race Detection

10/16 14:30 - 15:00 | Convention Center Ballroom A
We present an on-the-fly mechanism that detects access conflicts in executions of multithreaded Java programs. Access conflicts are a conservative approximation of data races. The checker tracks access information at the level of objects (object races) rather than at the level of individual variables. This viewpoint allows the checker to exploit specific properties of object-oriented programs for optimization by restricting dynamic checks to those objects that are identified by escape analysis as potentially shared. The checker has been implemented in collaboration with an "ahead-of-time" Java compiler. The combination of static program analysis (escape analysis) and inline instrumentation during code generation allows us to reduce the runtime overhead of detecting access conflicts. This overhead amounts to about 16-129% in time and less than 25% in space for typical benchmark applications and compares favorably to previously published on-the-fly mechanisms that incurred an overhead of about a factor of 2-80 in time and up to a factor of 2 in space.
Authors: Christoph von Praun, ETH Z¸rich, Thomas R. Gross, ETH Z¸rich

Efficient Implementation of Java Interfaces: Invokeinterface Considered Harmless

10/16 14:30 - 15:00 | Convention Center Ballroom D
Single superclass inheritance enables simple and efficient table-driven virtual method dispatch. However, virtual method table dispatch does not handle multiple inheritance and interfaces. This complication has led to a widespread misimpression that interface method dispatch is inherently inefficient. This paper argues that with proper implementation techniques, Java interfaces need not be a source of significant performance degradation. We present an efficient interface method dispatch mechanism, associating a fixed-sized interface method table (IMT) with each class that implements an interface. Interface method signatures hash to an IMT slot, with any hashing collisions handled by custom-generated conflict resolution stubs. The dispatch mechanism is efficient in both time and space. Furthermore, with static analysis and online profile data, an optimizing compiler can inline the dominant target(s) of any frequently executed interface call. Micro-benchmark results demonstrate that the expected cost of an interface method call dispatched via an IMT is comparable to the cost of a virtual method call. Experimental evaluation of a number of interface dispatch mechanisms on a suite of larger applications demonstrates that, even for applications that make only moderate use of interface methods, the choice of interface dispatching mechanism can significantly impact overall performance. Fortunately, several mechanisms provide good performance at a modest space cost.
Authors: Bowen Alpern, IBM T. J. Watson Research Center, Anthony Cocchi, IBM T. J. Watson Research Center, Stephen Fink, IBM T. J. Watson Research Center, David Grove, IBM T. J. Watson Research Center, Derek Lieber, IBM T. J. Watson Research Center

Multitasking without Compromise: A Virtual Machine Evolution

10/16 15:30 - 16:00 | Convention Center Ballroom A
The Multitasking Virtual Machine (MVM) is a modification of the Java virtual machine. It enables safe, secure, and scalable multitasking. Safety is achieved by strict isolation of applications from one another. Resource control mechanisms augment security by preventing some denial-of-service attacks. Improved scalability results from an aggressive application of the main design principle of MVM: share as much of the runtime as possible among applications and replicate everything else. The system can be described as a "no compromise" approach---all the known APIs and mechanisms of the Java programming language are available to applications. MVM is implemented as a series of carefully tuned modifications to the Java HotSpot virtual machine, including the dynamic compiler. This paper presents the design of MVM, focusing on several novel and general techniques: an in-runtime design of lightweight isolation; an extension of a copying, generational garbage collector to provide best-effort management of a portion of the heap space; and a transparent and automated mechanism for safe execution of user-level native code. MVM demonstrates that multitasking in a safe language can be accomplished with a high degree of protection, without constraining the language, and with competitive performance characteristics.
Authors: Grzegorz Czajkowski, Sun Microsystems Laboratories, Laurent DaynËs, Sun Microsystems Laboratories

Portable Resource Control in Java: The J-SEAL2 Approach

10/16 16:00 - 16:30 | Convention Center Ballroom A
Preventing abusive resource consumption is indispensable for all kinds of systems that execute untrusted mobile code, such as mobile object systems, extensible web servers, and web browsers. To implement the required defense mechanisms, some support for resource control must be available: accounting and limiting the usage of physical resources like CPU and memory, and of logical resources like threads. Java is the predominant implementation language for the kind of systems envisaged here, even though resource control is a missing feature on standard Java platforms. This paper describes the model and implementation mechanisms underlying the new resource-aware version of the J-SEAL2 mobile object kernel. Our fundamental objective is to achieve complete portability, and our approach is therefore based on Java bytecode transformations. Whereas resource control may be targeted towards the provision of quality of service or of usage-based billing, the focus of this paper is on security, and more specifically on prevention of denial-of-service attacks originating from hostile or poorly implemented mobile code.
Authors: Walter Binder, CoCo Software Engineering, Jarle G. Hulaas, University of Geneva, Alex VillazŰn, University of Geneva

Incremental Computation of Complex Objects Queries

10/16 16:30 - 17:00 | Convention Center Ballroom A
The need for incremental algorithms for evaluating database queries is well known, but constructing algorithms that work on object-oriented databases (OODBs) has been difficult. The reason is that OODB query languages involve complex data types including composite objects and nested collections. As a result, existing algorithms have limitations in that the kinds of database updates are restricted, the operations found in many query languages are not supported, or the algorithms are too complex to be described precisely. We present an incremental computation algorithm that can handle any kind of database updates, can accept any expressions in complex query languages such as OQL, and can be described precisely. By translating primitive values and records into collections, we can reduce all query expressions into ones composed of only one kind of operation, namely comprehension. This makes the problems with incremental computation less complicated and thus allows us to describe the algorithm precisely. Our incremental algorithm consists of two parts: one is to maintain the consistency in each comprehension occurrence and the other is to update the value of an entire expression. The algorithm is so flexible that we can use strict updates, lazy updates, and their combinations. By comparing the performance of applications built with our mechanism and that of equivalent hand-written update programs, we show that our incremental algorithm can be implemented efficiently.
Authors: Hiroaki Nakamura, IBM Tokyo Research Laboratory

Partial Method Compilation using Dynamic Profile Information

10/17 10:30 - 11:00 | Convention Center Ballroom A
The traditional tradeoff when performing dynamic compilation is that of fast compilation time versus fast code performance. Most dynamic compilation systems for Java perform selective compilation and/or optimization at a method granularity. This is the not the optimal granularity level. However, compiling at a sub-method granularity is thought to be too complicated to be practical. This paper describes a straightforward technique for performing compilation and optimizations at a finer, sub-method granularity. We utilize dynamic profile data to determine intra-method code regions that are rarely or never executed, and compile and optimize the code without those regions. If a branch that was predicted to be rare is actually taken at run-time, we fall back to the interpreter or dynamically compile another version of the code. By avoiding compiling and optimizing code that is rarely executed, we are able to decrease compile-time significantly, with little to no degradation in performance. Furthermore, ignoring rarely executed code can open up more optimization opportunities on the common paths. We present two optimizations---partial dead code elimination and rare-path-sensitive pointer and escape analysis---that take advantage of rare path information. Using these optimizations, our technique is able to improve performance beyond the compile-time improvements.
Authors: John Whaley, Stanford University

A Dynamic Optimization Framework for a Java Just-In-Time Compiler

10/17 11:00 - 11:30 | Convention Center Ballroom A
The high performance implementation of Java Virtual Machines (JVM) and Just-In-Time (JIT) compilers is directed toward adaptive compilation optimizations on the basis of online runtime profile information. This paper describes the design and implementation of a dynamic optimization framework in a production-level Java JIT compiler. Our approach is to employ a mixed-mode interpreter and a three-level optimizing compiler, supporting quick, full, and special optimization, each of which has a different set of tradeoffs between compilation overhead and execution speed. A lightweight sampling profiler operates continuously during the entire program's execution. When necessary, detailed information on runtime behavior is collected by dynamically generating instrumentation code which can be installed to and uninstalled from the specified recompilation target code. Value profiling with this instrumentation mechanism allows fully automatic code specialization to be performed on the basis of specific parameter values or global data at the highest optimization level. The experimental results show that our approach offers high performance and a low code expansion ratio in both program startup and steady state measurements in comparison to the compile-only approach, and that the code specialization can also contribute modest performance improvements.
Authors: Toshio Suganuma, IBM Tokyo Research Laboratory, Toshiaki Yasue, IBM Tokyo Research Laboratory, Motohiro Kawahito, IBM Tokyo Research Laboratory, Hideaki Komatsu, IBM Tokyo Research Laboratory, Toshio Nakatani, IBM Tokyo Research Laboratory

Dynamic Optimistic Interprocedural Analysis: A Framework and an Application

10/17 11:30 - 12:00 | Convention Center Ballroom A
In this paper, we address the problem of dynamic optimistic interprocedural analysis. Our goal is to build on past work on static interprocedural analysis and dynamic optimization by combining their advantages. We present a framework for performing dynamic optimistic interprocedural analysis. The framework is designed to be used in the context of dynamic class loading and dynamic compilation, and includes mechanisms for event notification (on class loading and method compilation) and dependence tracking (to enable invalidation of optimistic assumptions). We illustrate the functionality of the framework by using it to implement a dynamic optimistic interprocedural type (DOIT) analysis algorithm. The DOIT algorithm uses a new global data structure called the Value Graph. The framework and DOIT analysis are implemented as part of the IBM JalapeŇo Java Virtual Machine. Our experimental results for the SPECjvm benchmarks and two larger programs show promising benefits due to dynamic optimistic analysis. Compared to pessimistic analysis, the reduction in the number of methods and fields analyzed was in the 2.7X-4.6X and 1.6X-2.4X ranges, respectively. The average fraction of polymorphic virtual calls decreased from 39.5% to 24.4% due to optimistic analysis, with a best-case decrease from 47.0% to 8.1%. The average fraction of polymorphic interface calls decreased from 96.4% to 36.2% due to optimistic analysis, with a best-case decrease from 100.0% to 0.0%. These benefits were obtained with a low dynamic analysis overhead in the range of 570-930 bytes/millisecond (about 2.5X-5.4X faster than the JalapeŇo baseline compiler).
Authors: Igor Pechtchanski, New York University, Vivek Sarkar, IBM T. J. Watson Research Center

Jiazzi: New-Age Components for Old-Fashioned Java

10/17 13:30 - 14:00 | Convention Center Ballroom A
We present Jiazzi, a system that enables the construction of large-scale binary components in Java. Jiazzi components can be thought of as generalizations of Java packages with added support for external linking and separate compilation. Jiazzi components are practical because they are constructed out of standard Java source code. Jiazzi requires neither extensions to the Java language nor special conventions for writing Java source code that will go inside a component. Our components are expressive because Jiazzi supports cyclic component linking and mixins, which are used together in an open class pattern that enables the modular addition of new features to existing classes. This paper describes Jiazzi, how it enhances Java with components, its implementation, and how type checking works. An implementation of Jiazzi is available for download.
Authors: Sean McDirmid, University of Utah, Matthew Flatt, University of Utah, Wilson C. Hsieh, University of Utah

Modular Mixin-Based Inheritance for Application Frameworks

10/17 14:00 - 14:30 | Convention Center Ballroom A
Mixin modules are proposed as an extension of a class-based programming language. Mixin modules combine parallel extension of classes, including extension of the self types for those classes, with mixin-based inheritance. For soundness of subtyping purposes, they require an explicit distinction between mixin-based objects and class-based objects. Applications of mixin modules are in statically type-safe monad-based aspect-oriented programming, and in modular mixin-based Internet programming.
Authors: Dominic Duggan, Stevens Institute of Technology, Ching-Ching Techaubol, Stevens Institute of Technology

Encapsulating Objects with Confined Types

10/17 14:30 - 15:00 | Convention Center Ballroom A
Object-oriented languages provide little support for encapsulating objects. Reference semantics allows objects to escape their defining scope. The pervasive aliasing that ensues remains a major source of software defects. This paper introduces Kacheck/J, a tool for inferring object encapsulation properties in large Java programs. Our goal is to develop practical tools to assist software engineers; thus we focus on simple and scalable techniques. Kacheck/J is able to infer confinement for Java classes. A class and its subclasses are confined if all of their instances are encapsulated in their defining package. This simple property can be used to identify accidental leaks of sensitive objects. The analysis is scalable and efficient; Kacheck/J is able to infer confinement on a corpus of 46,000 classes (115 MB) in 6 minutes.
Authors: Christian Grothoff, Purdue University, Jens Palsberg, Purdue University, Jan Vitek, Purdue University

On Objects and Events

10/17 15:30 - 16:00 | Convention Center Ballroom A
This paper presents linguistic primitives for publish/subscribe programming using events and objects. We integrate our primitives into a strongly typed object-oriented language through four mechanisms: (1) serialization, (2) multiple subtyping, (3) closures, and (4) deferred code evaluation. We illustrate our primitives through Java, showing how we have overcome its respective lacks. A precompiler transforms statements based on our publish/subscribe primitives into calls to specifically generated typed adapters, which resemble the typed stubs and skeletons generated by the rmic precompiler for remote method invocations in Java.
Authors: Patrick T. Eugster, Swiss Federal Institute of Technology, Rachid Guerraoui, Swiss Federal Institute of Technology, Christian H. Damm, University of Aarhus

Visitor Combination and Traversal Control

10/17 16:00 - 16:30 | Convention Center Ballroom A
The Visitor design pattern allows the encapsulation of polymorphic behavior outside the class hierarchy on which it operates. A common application of Visitor is the encapsulation of tree traversals. Unfortunately, visitors resist composition and allow little traversal control. To remove these limitations, we introduce "visitor combinators." These are implementations of the visitor interface that can be used to compose new visitors from given ones. The set of combinators we propose includes traversal combinators that can be used to obtain full traversal control. A clean separation can be made between the generic parts of the combinator set and the parts that are specific to a particular class hierarchy. The generic parts form a reusable framework. The specific parts can be generated from a (tree) grammar. Due to this separation, programming with visitor combinators becomes a form of generic programming with significant reuse of (visitor) code.
Authors: Joost Visser, CWI

Object-Oriented Composition Untangled

10/17 16:30 - 17:00 | Convention Center Ballroom A
Object-oriented languages come with pre-defined composition mechanisms, such as inheritance, object composition, or delegation, each characterized by a certain set of composition properties, which do not themselves individually exist as abstractions at the language level. However, often non-standard composition semantics is needed, with a mixture of composition properties, which is not provided as such by any of the standard composition mechanisms. Such non-standard semantics are simulated by complicated architectures that are sensitive to requirement changes and cannot easily be adapted without invalidating existing clients. In this paper, we propose "compound references," a new abstraction for object references that allows us to provide explicit linguistic means for expressing and combining individual composition properties on-demand. The model is statically typed and allows the programmer to express a seamless spectrum of composition semantics in the interval between object composition and inheritance. The resulting programs are better understandable, due to explicitly expressed design decisions, and less sensitive to requirement changes.
Authors: Klaus Ostermann, Siemens AG, Mira Mezini, Darmstadt University of Technology

A Categorization of Classes based on the Visualization of their Internal Structure: The Class Blueprint

10/18 10:30 - 11:00 | Convention Center Ballroom A
The reengineering and reverse engineering of software systems is gaining importance in software industry, because the accelerated turnover in software companies creates legacy systems in a shorter period of time. Especially understanding classes is a key activity in object-oriented programming, since classes represent the primary abstractions from which applications are built. The main problem of this task is to quickly grasp the purpose of a class and its inner structure. To help the reverse engineers in their first contact with a foreign system, we propose a categorization of classes based on the visualization of their internal structure. The contributions of this paper are a novel categorization of classes and a visualization of the classes which we call the "class blueprint." We have validated the categorization on several case studies, two of which we present here.
Authors: Michele Lanza, University of Berne, StČphane Ducasse, University of Berne

Regression Test Selection for Java Software

10/18 11:00 - 11:30 | Convention Center Ballroom A
Regression testing is applied to modified software to provide confidence that the changed parts behave as intended and that the unchanged parts have not been adversely affected by the modifications. To reduce the cost of regression testing, test cases are selected from the test suite that was used to test the original version of the software---this process is called regression test selection. A "safe" regression-test-selection algorithm selects every test case in the test suite that may reveal a fault in the modified software. Safe regression-test-selection techniques can help to reduce the time required to perform regression testing because they select only a portion of the test suite for use in the testing but guarantee that the faults revealed by this subset will be the same as those revealed by running the entire test suite. This paper presents the first safe regression-test-selection technique that, based on the use of a suitable representation, handles the features of the Java language. Unlike other safe regression test selection techniques, the presented technique also handles incomplete programs. The technique can thus be safely applied in the (very common) case of Java software that uses external libraries or components; the analysis of the external code is not required for the technique to select test cases for such software. The paper also describes Retest, a regression-test-selection system that implements our technique, and a set of empirical studies that demonstrate that the regression-test-selection algorithm can be effective in reducing the size of the test suite.
Authors: Mary Jean Harrold, Georgia Institute of Technology, James A. Jones, Georgia Institute of Technology, Tongyu Li, Georgia Institute of Technology, Donglin Liang, Georgia Institute of Technology, Alessandro Orso, Georgia Institute of Technology, Maikel Pennings, Georgia Institute of Technology, Saurabh Sinha, Georgia Institute of Technology, S. Alexander Spoon, Georgia Institute of Technology, Ashish Gujarathi, Citrix Systems

The Architecture of a UML Virtual Machine

10/18 11:30 - 12:00 | Convention Center Ballroom A
Current software development tools let developers model a software system and generate program code from the models to run the system. However, generating code and installing a non-trivial system induces a time delay between changing the model and executing it that makes rapid model prototyping awkward if not impossible. This paper presents the architecture of a virtual machine for UML that interprets UML models without any intermediate code-generation step. The paper shows how to embed UML in a metalevel architecture so that a key property of model-based systems, the causal connection between models and model instances, is guaranteed. With this architecture, changes to a model have immediate effects on its execution, providing users with rapid feedback about the model's structure and behavior. This approach supports model innovation better than today's code-generation approaches.
Authors: Dirk Riehle, SKYVA International, Steven Fraleigh, SKYVA International, Dirk Bucka-Lassen, Object Oriented, Ltd., Nosa Omorogbe, SKYVA International

Pretenuring for Java

10/18 13:30 - 14:00 | Convention Center Ballroom A
Pretenuring can reduce copying costs in garbage collectors by allocating long-lived objects into regions that the garbage collector will rarely, if ever, collect. We extend previous work on pretenuring as follows. (1) We produce pretenuring advice that is neutral with respect to the garbage collector algorithm and configuration. We thus can and do combine advice from different applications. We find that predictions using object lifetimes at each allocation site in Java programs are accurate, which simplifies the pretenuring implementation. (2) We gather and apply advice to applications and the JalapeŇo JVM, a compiler and run-time system for Java written in Java. Our results demonstrate that building combined advice into JalapeŇo from different application executions improves performance regardless of the application JalapeŇo is compiling and executing. This build-time advice thus gives user applications some benefits of pretenuring without any application profiling. No previous work pretenures in the run-time system. (3) We find that application-only advice also improves performance, but that the combination of build-time and application-specific advice is almost always noticeably better. (4) Our same advice improves the performance of generational and Older First collection, illustrating that it is collector-neutral.
Authors: Stephen M. Blackburn, University of Massachusetts, Sharad Singhai, University of Massachusetts, Matthew Hertz, University of Massachusetts, Kathryn S. McKinley, University of Massachusetts, J. Eliot B. Moss, University of Massachusetts

Controlling Garbage Collection and Heap Growth to Reduce the Execution Time of Java Applications

10/18 14:00 - 14:30 | Convention Center Ballroom A
In systems that support garbage collection, a tension exists between collecting garbage too frequently and not collecting garbage frequently enough. Garbage collection that occurs too frequently may introduce unnecessary overheads at the risk of not collecting much garbage during each cycle. On the other hand, collecting garbage too infrequently can result in applications that execute with a large amount of virtual memory (i.e., with a large footprint) and suffer from increased execution times due to paging. In this paper, we use a large collection of Java applications and the highly tuned and widely used Boehm-Demers-Weiser (BDW) conservative mark-and-sweep garbage collector to experimentally examine the extent to which the frequency of garbage collection impacts an application's execution time, footprint, and pause times. We use these results to devise some guidelines for controlling garbage collection and heap growth in a conservative garbage collector in order to minimize application execution times. Then we describe new strategies for controlling garbage collection and heap growth that impact not only the frequency with which garbage collection occurs but also the points at which garbage collection occurs. Experimental results demonstrate that, when compared with the existing approach used in the standard BDW collector, our new strategy can significantly reduce application execution times. Our goal is to obtain a better understanding of how to control garbage collection and heap growth for an individual application executing in isolation. These results can be applied in a number of high-performance computing and server environments, in addition to some single-user environments. This work should also provide insights into how to make better decisions that impact garbage collection in multi-programmed environments.
Authors: Tim Brecht, University of Waterloo and HP Labs, Eshrat Arjomandi, York University, Chang Li, York University, Hang Pham, York University

An On-the-Fly Reference Counting Garbage Collector for Java

10/18 14:30 - 15:00 | Convention Center Ballroom A
Reference counting is not naturally suitable for running on multiprocessors. The update of pointers and reference counts requires atomic and synchronized operations. We present a novel reference counting algorithm suitable for a multiprocessor that does not require any synchronized operation in its write barrier (not even a compare-and-swap type of synchronization). The algorithm is efficient and may compete with any tracing algorithm. We have implemented our algorithm on SUN's Java Virtual Machine 1.2.2 and ran it on a 4-way IBM Netfinity 8500R server with 550MHz Intel Pentium III Xeon and 2GB of physical memory. It turns out that our algorithm has an extremely low latency and throughput that is comparable to the mark and sweep algorithm used in the original JVM.
Authors: Yossi Levanoni, Microsoft, Erez Petrank, Technion