title: OoLALA: an object oriented analysis and design of numerical linear algebra

authors:
Mikel Luján
T. L. Freeman
John R. Gurd

abstract: In this paper we review the design of a sequential object oriented linear algebra library, OOLALA. Several designs are proposed and used to classify existing sequential object oriented libraries. The classification is based on the way that matrices and matrix operations are represented. OOLALA's representation of matrices is capable of dealing with certain matrix operations that, although mathematically valid, are not handled correctly by existing libraries. OOLALA also enables implementations of matrix calculations at various abstraction levels ranging from the relatively low-level abstraction of a Fortran BLAS-like implementation to higher-level abstractions that hide many implementation details. OOLALA addresses a wide range of numerical linear algebra functionality while the reviewed object oriented libraries concen trate on parts of such functionality. We include some preliminary performance results for a Java implementation of OOLALA.


venue: oopsla

title: Improving the Java memory model using CRF

authors:
Jan-Willem Maessen
Arvind
Xiaowei Shen

abstract: This paper describes alternative memory semantics for Java programs using an enriched version of the Commit/Reconcile/Fence (CRF) memory model [16]. It outlines a set of reasonable practices for safe multithreaded programming in Java. Our semantics allow a number of optimizations such as load reordering that are currently prohibited. Simple thread-local algebraic rules express the effects of optimizations at the source or bytecode level. The rules focus on reordering source-level operations; they yield a simple dependency analysis algorithm for Java. An instruction-by-instruction translation of Java memory operations into CRF operations captures thread interactions precisely. The fine-grained synchronization of CRF means the algebraic rules are easily derived from the translation. CRF can be mapped directly to a modern architecture, and is thus a suitable target for optimizing memory coherence during code generation.


title: Exclusion for composite objects

authors:
James Noble
David Holmes
John Potter

abstract: Designing concurrent object-oriented programs is hard. Correct programs must coordinate multiple threads accessing composite objects, using low-level mechanisms such as locks and read-write sets. Efficient programs must balance the complexity and overhead of the coordination mechanisms against the increased performance possible through concurrency. A method-level algebra of exclusion provides a succinct description of the conditions under which a thread must be excluded from a component of a composite object. Using the algebra, programmers can check whether their programs meet their exclusion requirements, can eliminate redundant exclusion controls, and can remove synchronisation overhead by reducing concurrency.


title: Towards agent-oriented assistance for framework instantiation

authors:
Alvaro Ortigosa
Marcelo Campo
Roberto Moriyón

abstract: In this work we present a tool for assisting object-oriented framework instantiation based on Intelligent Agent technology. Differently from other approaches, the user is able to select the functionality needed for the new application, and based on this selection an agent elaborates a sequence of programming activities that should be carried out in order to implement it. In addition, the agent guides the execution of the activities according to the framework design. To enable this behavior, the framework need to be documented following the SmartBooks method, which extends traditional framework documentation with instantiation rules. In this paper we present an example of an instantiation environment built based on these ideas and the main characteristics of the SmartBooks method for documenting frameworks through instantiation knowledge rules.


title: A formal specification of JavaTM class loading

authors:
Zhenyu Qian
Allen Goldberg
Alessandro Coglio

abstract: The Java Virtual Machine (JVM) has a novel and powerful mechanism to support lazy, dynamic class loading according to user-definable policies. Class loading directly impacts type safety, on which the security of Java applications is based. Conceptual bugs in the loading mechanism were found in earlier versions of the JVM that lead to type violations. A deeper understanding of the class loading mechanism, through such means as formal analysis, will improve our confidence that no additional bugs are present.The work presented in this paper provides a formal specification of (the relevant aspects of) class loading in the JVM and proves its type safety. Our approach to proving type safety is different from the usual ones since classes are dynamically loaded and full type information may not be statically available. In addition, we propose an improvement in the interaction between class loading and bytecode verification, which is cleaner and enables lazier loading.


title: An Aristotelian understanding of object-oriented programming

authors:
Derek Rayside
Gerard T. Campbell

abstract: The folklore of the object-oriented programming community at times maintains that object-oriented programming has drawn inspiration from philosophy, specically that of Aristotle. We investigate this relation, first of all, in the hope of attaining a better understanding of object-oriented programming and, secondly, to explain aspects of Aristotelian logic to the computer science research community (since it differs from first order predicate calculus in a number of important ways). In both respects we endeavour to contribute to the theory of objects, albeit in a more philosophical than mathematical fashion.


title: Safely creating correct subclasses without seeing superclass code

authors:
Clyde Ruby
Gary T. Leavens

abstract: A major problem for object-oriented frameworks and class libraries is how to provide enough information about a superclass, so programmers can safely create new subclasses without giving away the superclass's code. Code inherited from the superclass can call down to methods of the subclass, which may cause nontermination or unexpected behavior. We describe a reasoning technique that allows programmers, who have no access to the code of the superclass, to determine both how to safely override the superclass's methods and when it is safe to call them. The technique consists of a set of rules and some new forms of specification. Part of the specification would be generated automatically by a tool, a prototype of which is planned for the formal specification language JML. We give an example to show the kinds of problems caused by method overrides and how our technique can be used to avoid them. We also argue why the technique is sound and give guidelines for library providers and programmer...


title: Quicksilver: a quasi-static compiler for Java

authors:
Mauricio J. Serrano
Rajesh Bordawekar
Samuel P. Midkiff
Manish Gupta

abstract: This paper presents the design and implementation of the Quicksilver1 quasi-static compiler for Java. Quasi-static compilation is a new approach that combines the benefits of static and dynamic compilation, while maintaining compliance with the Java standard, including support of its dynamic features. A quasi-static compiler relies on the generation and reuse of persistent code images to reduce the overhead of compilation during program execution, and to provide identical, testable and reliable binaries over different program executions. At runtime, the quasi-static compiler adapts pre-compiled binaries to the current JVM instance, and uses dynamic compilation of the code when necessary to support dynamic Java features. Our system allows interprocedural program optimizations to be performed while maintaining binary compatibility. Experimental data obtained using a preliminary implementation of a quasi-static compiler in the Jalapeño JVM clearly demonstrates the benefits of our approach: we achieve a runtime compilation cost comparable to that of baseline (fast, non-optimizing) compilation, and deliver the runtime program performance of the highest optimization level supported by the Jalapeño optimizing compiler. For the SPECjvm98 benchmark suite, we obtain a factor of 104 to 158 reduction in the runtime compilation overhead relative to the Jalapeño optimizing compiler. Relative to the better of the baseline and the optimizing Jalapeño compilers, the overall performance (taking into account both runtime compilation and execution costs) is increased by 9.2% to 91.4% for the SPECjvm98 benchmarks with size 100, and by 54% to 356% for the (shorter running) SPECjvm98 benchmarks with size 10.


title: Practical virtual method call resolution for Java

authors:
Vijay Sundaresan
Laurie J. Hendren
Chrislain Razafimahefa
Raja Vallée-Rai
Patrick Lam
Etienne Gagnon
Charles Godin

abstract: This paper addresses the problem of resolving virtual method and interface calls in Java bytecode. The main focus is on a new practical technique that can be used to analyze large applications. Our fundamental design goal was to develop a technique that can be solved with only one iteration, and thus scales linearly with the size of the program, while at the same time providing more accurate results than two popular existing linear techniques, class hierarchy analysis and rapid type analysis.We present two variations of our new technique, variable-type analysis and a coarser-grain version called declared-type analysis. Both of these analyses are inexpensive, easy to implement, and our experimental results show that they scale linearly in the size of the program.We have implemented our new analyses using the Soot frame-work, and we report on empirical results for seven benchmarks. We have used our techniques to build accurate call graphs for complete applications (including libraries) and we show that compared to a conservative call graph built using class hierarchy analysis, our new variable-type analysis can remove a significant number of nodes (methods) and call edges. Further, our results show that we can improve upon the compression obtained using rapid type analysis.We also provide dynamic measurements of monomorphic call sites, focusing on the benchmark code excluding libraries. We demonstrate that when considering only the benchmark code, both rapid type analysis and our new declared-type analysis do not add much precision over class hierarchy analysis. However, our finer-grained variable-type analysis does resolve significantly more call sites, particularly for programs with more complex uses of objects.


title: Scalable propagation-based call graph construction algorithms

authors:
Frank Tip
Jens Palsberg

abstract: Propagation-based call graph construction algorithms have been studied intensively in the 199Os, and differ primarily in the number of sets that are used to approximate run-time values of expressions. In practice, algorithms such as RTA that use a single set for the whole program scale well. The scalability of algorithms such as 0-CFA that use one set per expression remains doubtful.In this paper, we investigate the design space between RTA and 0-CFA. We have implemented various novel algorithms in the context of Jax, an application extractor for Java, and shown that they all scale to a 325,000-line program. A key property of these algorithms is that they do not analyze values on the run-time stack, which makes them efficient and easy to implement. Surprisingly, for detecting unreachable methods, the inexpensive RTA algorithm does almost as well as the seemingly more powerful algorithms. However, for determining call sites with a single target, one of our new algorithms obtains the current best tradeoff between speed and precision.


title: Parametric polymorphism in Java: an approach to translation based on reflective features

authors:
Mirko Viroli
Antonio Natali

abstract: The introduction of parametric polymorphism in Java with translation approaches has been shown to be of considerable interest, allowing the definition of extensions of Java on top of the existing Virtual Machines. Homogeneous translations furthermore, seem to be more useful than heterogeneous, avoiding the continuous increase of library code with redundant information. At this time however, homogeneous approaches aren't as flexible as heterogeneous, with extensions failing to integrate well with base language typing. In this paper, using some of the features of the Core Reflection of Java, we introduce a homogeneous translation in which run-time information about instantiation of type-parameters is carried, allowing full integration of parame-terized types with Java typing. Performance overhead is greatly decreased using a brand new translation technique based on the deferring of the management of type information at load-time. The same power and flexibility of previous heterogeneous approaches is obtained while maintaining homogeneous translation advantages.


title: Sealed calls in Java packages

authors:
Ayal Zaks
Vitaly Feldman
Nava Aizikowitz

abstract: Ø�Ö��Ø×�ÙÖ�Ø�ÐÝÌ��ÔÖÓ�Ð�Ñ�×�×Ô���ÐÐÝ��ÆÙÐØ�ÓÖ �ÝÒ�Ñ�Ð�Ò�Ù���××Ù��×Â�Ú����Ù×�����Ø�ÓÒ�ÐØ�Ö��Ø × ��Ø�ÖÑ�Ò�Ò�Ø��ÔÓØ�ÒØ��ÐØ�Ö��Ø×Ó�Ú�ÖØÙ�ÐÑ�Ø�Ó��ÒÚÓ � Ø�ÓÒ×�×�××�ÒØ��Ð�ÓÖ�ÒØ�ÖÔÖÓ��ÙÖ�ÐÓÔØ�Ñ�Þ�Ø�ÓÒ×Ó�Ó���Ø ÓÖ��ÒØ��ÔÖÓ�Ö�Ñ×ÁØ�×��Ò�Ö�ÐÐÝ��Ö�ØÓ��Ø�ÖÑ�Ò�×Ù � Â�Ú�Ó���ØÓÖ��ÒØ��ÔÖÓ�Ö�ÑÑ�Ò��ÒØ�ÖÔÖÓ��ÙÖ�Ð�Ò�Ð �Ù���×Ö�Ô��Ø��ÐÝÚ�Ð���Ø�Ø��ÓÔØ�Ñ�Þ�Ø�ÓÒ×�ØÖÙÒØ�Ñ � Ø��Ø�Ò��Ð��ÒØ�ÖÔÖÓ��ÙÖ�ÐÓÔØ�Ñ�Þ�Ø�ÓÒ×�ÓÖ�ÝÒ�Ñ�Ð�Ò Ó�Ú�ÖØÙ�Ð�ÐÐ×Ñ�Ý�ÔÔ��Ö�ØÖÙÒØ�Ñ��ÙÖÖ�ÒØÑ���Ò�×Ñ × Ý×�×�ÐÐ��Ú�ÖØÙ�Ð�Þ�Ø�ÓÒÑ�Ø�Ó��ÒÐ�Ò�Ò�Ð�××���Ö�Ö�Ý �Ö�Ô��ÐÐ�Ö�Ô�×��Ð��Ô����� Ì��×Ô�Ô�Ö���Ö�××�×Ø��×ÔÖ����Ñ�ÒØ�ÝÔÖÓÔÓ×�Ò��ÒÓÚ�Ð Ø��Ò�ÕÙ��ÓÖÓÒ×�ÖÚ�Ø�Ú���Ú�ÖØÙ�Ð�Þ�Ø�ÓÒ�Ò�ÐÝ×�×Û�� � �ÔÔÐ��×ØÓ�×��Ò�¬�ÒØÒÙÑ��ÖÓ�Ú�ÖØÙ�Ð�ÐÐ×�ÒÂ�Ú�ÔÖÓ Ö�Ð�Ø��×�ÙÖ�ØÝ���ØÙÖ�Ó�Â�Ú�¬Ð��Ö��Ú�×ÇÒ�Ú�Ö���ÓÙÖ �Ö�Ñ×ÍÒÐ���ÔÖ�Ú�ÓÙ×ÛÓÖ�ÓÙÖØ��Ò�ÕÙ�Ö�ÕÙ�Ö�×Ò��Ø��Ö �Ö���×��ÓÒØ����Ø�ÖÑ�Ò�Ø�ÓÒÓ�Ø��ÔÓØ�ÒØ��ÐØ�Ö��Ø×Ó � ÁÒØ�ÖÔÖÓ��ÙÖ�ÐÓÔØ�Ñ�Þ�Ø�ÓÒ×Ó�Ó���ØÓÖ��ÒØ��ÔÖÓ�Ö�Ñ×


title: Efficient Implementation of Java Interfaces: Invokeinterface Considered Harmless

authors:
Bowen Alpern
Anthony Cocchi
Stephen J. Fink
David Grove
Derek Lieber

abstract: Single superclass inheritance enables simple and efficient table-driven virtual method dispathc. 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.


title: A Core Calculus for Java Exceptions

authors:
Davide Ancona
Giovanni Lagorio
Elena Zucca

abstract: In this paper we present a simple calculus (called CJE) in ourder to fully investigate the exception mechanism of Java, and in particular its interaction with inheritance, which turns out to be non trivial. Moreover, we show that the type system for the calculus directly dirven by the Java language specification (called FULL) uses too many types, in the sense that there are different types which rpovide exactly the same information. Hence, we obtain from FULL a simplified type system called MIN where equivalent types have been identified. We show that 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


title: The Java Syntactic Extender

authors:
Jonathan Bachrach
Keith Playford

abstract: 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 sytems, 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


title: Portable Resource Control in Java: The J-SEAL2 Approach

authors:
Walter Binder
Jarle Hulaas
Alex Villazón

abstract: Preventing abusive resource consumption is indispensable for all kinds of systems that execute untrusted mobile coee, such as mobile object sytems, 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 specificlly on prevention of denial-of-service attacks orginating from hostile or poorly implemented mobile code.


title: Pretenuring for Java

authors:
Stephen M. Blackburn
Sharad Singhai
Matthew Hertz
Kathryn S. McKinley
J. Eliot B. Moss

abstract: Pretenuring can reduce copying costs in garbage collectors by allocating long-lived objects into regions that the garbage collector with 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 prgroams 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 colleciton, illustrating that it is collector neutral.


title: A Parameterized Type System for Race-Free Java Programs

authors:
Chandrasekhar Boyapati
Martin C. Rinard

abstract: ... 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 dierent 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.


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

authors:
Tim Brecht
Eshrat Arjomandi
Chang Li
Hang Pham

abstract: 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 BoehmDemers -Weiser conservative 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 our new strategy can significantly reduce application execution times. 1


title: Multitasking without Compromise: A Virtual Machine Evolution

authors:
Grzegorz Czajkowski
Laurent Daynès

abstract: The multitasking virtual machine (called from now on simply MVM) is a modification of the Java virtual machine. It enables safe, secure, and scalable multitasking. Safety is achieved by strict isolation of application from one another. Resource control 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 and with competitive performance characteristics

awards: Most Influential OOPSLA Paper (awarded 2011)


title: Modular Mixin-Based Inheritance for Application Frameworks

authors:
Dominic Duggan
Ching-Ching Techaubol

abstract: 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 sybtyping 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.


title: On Objects and Events

authors:
Patrick Th. Eugster
Rachid Guerraoui
Christian Heide Damm

abstract: 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 mechnisms: (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 by the rmic precompiler for remote method invocations in Java


title: Contract Soundness for Object-Oriented Languages

authors:
Robert Bruce Findler
Matthias Felleisen

abstract: 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 caller failed to establish the proper context. If a post-condition doesn't hold, the procedure failed to compute the expected result.


title: Encapsulating Objects with Confined Types

authors:
Christian Grothoff
Jens Palsberg
Jan Vitek

abstract: 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 encapulation 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 sublasses 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 t infer confinement on a corpus of 46,000 classes (115 MB) in 6 minutes


title: Regression Test Selection for Java Software

authors:
Mary Jean Harrold
James A. Jones
Tongyu Li
Donglin Liang
Alessandro Orso
Maikel Pennings
Saurabh Sinha
Steven Alexander Spoon
Ashish Gujarathi

abstract: 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 regressiontest -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


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

authors:
Michele Lanza
Stéphane Ducasse

abstract: The reengineering and reverse engineering of software systems is gaining importance in software industry, because the accelerated turnover 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 which we call the class blueprint. We have validated the categorization on several case studies, two of which we present here.


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

authors:
Yossi Levanoni
Erez Petrank

abstract: 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 complete with any tracing algorithm.


title: Jiazzi: New-Age Components for Old-Fashioned Java

authors:
Sean McDirmid
Matthew Flatt
Wilson C. Hsieh

abstract: 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 becuase 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 becuase 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.


title: Incremental Computation of Complex Objects Queries

abstract: 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 comprehension. This makes the problems with incremental computation less complicated and thus allows us to decribe 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 iplemented efficiently.


title: A Study of Exception Handling and Its Dynamic Optimization in Java

authors:
Takeshi Ogasawara
Hideaki Komatsu
Toshio Nakatani

abstract: Optimizing exception handling is critical for programs that frequently throw exceptions. We observed that there are many such exception-intensive programs iin various categories of Java programs. There are two commonly used exception handling techniques, 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.


title: Object-Oriented Composition Untangled

authors:
Klaus Ostermann
Mira Mezini

abstract: Object-oriented languages come with pre-defined composition mechansims, 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 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 explicity expressed design decisions, and less sensitive to requirement changes.


title: Dynamic Optimistic Interprocedural Analysis: A Framework and an Application

authors:
Igor Pechtchanski
Vivek Sarkar

abstract: 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 be used in the context of dynamic class loading and dynamic compilation, and includes mechanisms for event notification (on class loading and method compilaton) 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 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 number of methods and fields analyzed was in the 2.7x-4.6x and 1.6-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 bytecode bytes/millisecond (about 2.5x-5.4x faster than the Jalapeño baseline compiler)


title: Object Race Detection

authors:
Christoph von Praun
Thomas R. Gross

abstract: We present an on-the-fly mechanism that detects access conflicts in executions of multi-threaded 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 fo 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 mechanism that incurred an overhead of about a factor of 2-80 in time and up to a factor of 2 in space.


title: The Architecture of a UML Virtual Machine

authors:
Dirk Riehle
Steven Fraleigh
Dirk Bucka-Lassen
Nosa Omorogbe

abstract: 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 awkard 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 casual 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.


title: Points-To Analysis for Java using Annotated Constraints

authors:
Atanas Rountev
Ana L. Milanova
Barbara G. Ryder

abstract: The goal of point-to analysis for Java is to determine the set of objects pointed 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 point-to analysis for Java based on Andersen's point-to analysis for C [5]. We implement the analysis by using a constraint-based approach which employs annotated inclusion constraints. Constraint annotations allow us 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 albe to perform practical and precies points-to analysis for Java


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

authors:
Toshio Suganuma
Toshiaki Yasue
Motohiro Kawahito
Hideaki Komatsu
Toshio Nakatani

abstract: 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 exectuion. When necessary, detailed information on runtime behavior is collected by dynmiacally 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 improvement


title: Visitor Combination and Traversal Control

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


title: Partial Method Compilation using Dynamic Profile Information

abstract: 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. Futhermore, 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


title: Efficient Subtyping Tests with PQ-Encoding

authors:
Yoav Zibin
Joseph Gil

abstract: Subtyping tests, i.e., determining whether one type is a subtype of another, are a frequent operation during the execution of objectoriented 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.


title: Alias annotations for program understanding

authors:
Jonathan Aldrich
Valentin Kostadinov
Craig Chambers

abstract: One of the primary challenges in building and evolving large object-oriented systems is understanding aliasing between objects. Unexpected aliasing can lead to broken invariants, mistaken assumptions, security holes, and surprising side effects, all of which may lead to software defects and complicate software evolution.This paper presents AliasJava, a capability-based alias annotation system for Java that makes alias patterns explicit in the source code, enabling developers to reason more effectively about the interactions in a complex system. We describe our implementation, prove the soundness of the annotation system, and give an algorithm for automatically inferring alias annotations. Our experience suggests that the annotation system is practical, that annotation inference is efficient and yields appropriate annotations, and that the annotations can express important invariants of data structures and of software architectures.


title: Online feedback-directed optimization of Java

authors:
Matthew Arnold
Michael Hind
Barbara G. Ryder

abstract: This paper describes the implementation of an online feedback-directed optimization system. The system is fully automatic; it requires no prior (offline) profiling run. It uses a previously developed low-overhead instrumentation sampling framework to collect control flow graph edge profiles. This profile information is used to drive several traditional optimizations, as well as a novel algorithm for performing feedback-directed control flow graph node splitting. We empirically evaluate this system and demonstrate improvements in peak performance of up to 17% while keeping overhead low, with no individual execution being degraded by more than 2% because of instrumentation.


title: Reconsidering custom memory allocation

authors:
Emery D. Berger
Benjamin G. Zorn
Kathryn S. McKinley

abstract: Programmers hoping to achieve performance improvements often use custom memory allocators. This in-depth study examines eight applications that use custom allocators. Surprisingly, for six of these applications, a state-of-the-art general-purpose allocator (the Lea allocator) performs as well as or better than the custom allocators. The two exceptions use regions, which deliver higher performance (improvements of up to 44%). Regions also reduce programmer burden and eliminate a source of memory leaks. However, we show that the inability of programmers to free individual objects within regions can lead to a substantial increase in memory consumption. Worse, this limitation precludes the use of regions for common programming idioms, reducing their usefulness.We present a generalization of general-purpose and region-based allocators that we call reaps. Reaps are a combination of regions and heaps, providing a full range of region semantics with the addition of individual object deletion. We show that our implementation of reaps provides high performance, outperforming other allocators with region-like semantics. We then use a case study to demonstrate the space advantages and software engineering benefits of reaps in practice. Our results indicate that programmers needing fast regions should use reaps, and that most programmers considering custom allocators should instead use the Lea allocator.

awards: Most Influential OOPSLA Paper (awarded 2012)


title: BuddyCache: high-performance object storage for collaborative strong-consistency applications in a WAN

authors:
Magnus E. Bjornsson
Liuba Shrira

abstract: Collaborative applications provide a shared work environment for groups of networked clients collaborating on a common task. They require strong consistency for shared persistent data and efficient access to fine-grained objects. These properties are difficult to provide in wide area networks because of high network latency.BuddyCache is a new transactional caching approach that improves the latency of access to shared persistent objects for collaborative strong-consistency applications in high-latency network environments. The challenge is to improve performance while providing the correctness and availability properties of a transactional caching protocol in the presence of node failures and slow peers.We have implemented a BuddyCache prototype and evaluated its performance. Analytical results, confirmed by measurements of the BuddyCache prototype using the multi-user 007 benchmark indicate that for typical Internet latencies, e.g. ranging from 40 to 80 milliseconds round trip time to the storage server, peers using BuddyCache can reduce by up to 50% the latency of access to shared objects compared to accessing the remote servers directly.


title: Ownership types for safe programming: preventing data races and deadlocks

authors:
Chandrasekhar Boyapati
Robert Lee
Martin C. Rinard

abstract: This paper presents a new static type system for multithreaded programs; well-typed programs in our system are guaranteed to be free of data races and deadlocks. Our type system allows programmers to partition the locks into a fixed number of equivalence classes and specify a partial order among the equivalence classes. The type checker then statically verifies that whenever a thread holds more than one lock, the thread acquires the locks in the descending order.Our system also allows programmers to use recursive tree-based data structures to describe the partial order. For example, programmers can specify that nodes in a tree must be locked in the tree order. Our system allows mutations to the data structure that change the partial order at runtime. The type checker statically verifies that the mutations do not introduce cycles in the partial order, and that the changing of the partial order does not lead to deadlocks. We do not know of any other sound static system for preventing deadlocks that allows changes to the partial order at runtime.Our system uses a variant of ownership types to prevent data races and deadlocks. Ownership types provide a statically enforceable way of specifying object encapsulation. Ownership types are useful for preventing data races and deadlocks because the lock that protects an object can also protect its encapsulated objects. This paper describes how to use our type system to statically enforce object encapsulation as well as prevent data races and deadlocks. The paper also contains a detailed discussion of different ownership type systems and the encapsulation guarantees they provide.


title: Performance and scalability of EJB applications

authors:
Emmanuel Cecchet
Julie Marguerite
Willy Zwaenepoel

abstract: We investigate the combined effect of application implementation method, container design, and efficiency of communication layers on the performance scalability of J2EE application servers by detailed measurement and profiling of an auction site server.We have implemented five versions of the auction site. The first version uses stateless session beans, making only minimal use of the services provided by the Enterprise JavaBeans (EJB) container. Two versions use entity beans, one with container-managed persistence and the other with bean-managed persistence. The fourth version applies the session fasade pattern, using session beans as a fasade to access entity beans. The last version uses EJB 2.0 local interfaces with the session fasade pattern. We evaluate these different implementations on two popular open-source EJB containers with orthogonal designs. JBoss uses dynamic proxies to generate the container classes at run time, making an extensive use of reflection. JOnAS pre-compiles classes during deployment, minimizing the use of reflection at run time. We also evaluate the communication optimizations provided by each of these EJB containers.The most important factor in determining performance is the application implementation method. EJB applications with session beans perform as well as a Java servlets-only implementation and an order-of-magnitude better than most of the implementations based on entity beans. The fine-granularity access exposed by the entity beans limits scalability. Use of session fasade beans improves performance for entity beans, but only if local communication is very efficient or EJB 2.0 local interfaces are used. Otherwise, session fasade beans degrade performance.For the implementation using session beans, communication cost forms the major component of the execution time on the EJB server. The design of the container has little effect on performance. With entity beans, the design of the container becomes important. In particular, the cost of reflection affects performance. For implementations using session fasade beans, local communication cost is critically important. EJB 2.0 local interfaces improve the performance by avoiding the communication layers for local communications.


title: Ownership, encapsulation and the disjointness of type and effect

authors:
David G. Clarke
Sophia Drossopoulou

abstract: Ownership types provide a statically enforceable notion of object-level encapsulation. We extend ownership types with computational effects to support reasoning about object-oriented programs. The ensuing system provides both access control and effects reporting. Based on this type system, we codify two formal systems for reasoning about aliasing and the disjointness of computational effects. The first can be used to prove that evaluation of two expressions will never lead to aliases, while the latter can be used to show the non-interference of two expressions.


title: Language-specific make technology for the Java programming language

abstract: Keeping the code of a Java application consistent (code is consistent if all of the project classes can be recompiled together without errors) prevents late linking errors, and thus may significantly improve development turnaround time. In this paper we describe a make technology for the Java programming language, that is based on smart dependency checking, guarantees consistency of the project code, and at the same time reduces the number of source code recompilations to the minimum. After project code consistency is initially assured by complete recompilation, the information extracted from the binary classes is stored in a so-called project database. Whenever the source code for some class C is changed, its recompiled binary is compared to the old version of C preserved in the project database. As a result, we find a minimum subset of classes that depend on C and may be affected by the particular change made to it. These are recompiled in turn, and absence of compilation errors at this phase guarantees the consistency of the new project code. To determine which dependent classes to recompile, we categorize all source incompatible changes, and for each category establish a criterion for finding the smallest possible subset of dependent classes.


title: Design pattern implementation in Java and aspectJ

authors:
Jan Hannemann
Gregor Kiczales

abstract: AspectJ implementations of the GoF design patterns show modularity improvements in 17 of 23 cases. These improvements are manifested in terms of better code locality, reusability, composability, and (un)pluggability.The degree of improvement in implementation modularity varies, with the greatest improvement coming when the pattern solution structure involves crosscutting of some form, including one object playing multiple roles, many objects playing one role, or an object playing roles in multiple pattern instances.


title: Lock reservation: Java locks can mostly do without atomic operations

authors:
Kiyokuni Kawachiya
Akira Koseki
Tamiya Onodera

abstract: Because of the built-in support for multi-threaded programming, Java programs perform many lock operations. Although the overhead has been significantly reduced in the recent virtual machines, One or more atomic operations are required for acquiring and releasing an object's lock even in the fastest cases.This paper presents a novel algorithm called lock reservation. It exploits thread locality of Java locks, which claims that the locking sequence of a Java lock contains a very long repetition of a specific thread. The algorithm allows locks to be reserved for threads. When a thread attempts to acquire a lock, it can do without any atomic operation if the lock is reserved for the thread. Otherwise, it cancels the reservation and falls back to a conventional locking algorithm.We have evaluated an implementation of lock reservation in IBM's production virtual machine and compiler. The results show that it achieved performance improvements up to 53% in real Java programs.


title: An analyzable annotation language

authors:
Sarfraz Khurshid
Darko Marinov
Daniel Jackson

abstract: The Alloy Annotation Language (AAL) is a language (under development) for annotating Java code based on the Alloy modeling language. It offers a syntax similar to the Java Modeling Language (JML), and the same opportunities for generation of run-time assertions. In addition, however, AAL offers the possibility of fully automatic compile-time analysis. Several kinds of analysis are supported, including: checking the code of a method against its specification; checking that the specification of a method in a subclass is compatible with the specification in the superclass; and checking properties relating method calls on different objects, such as that the equals methods of a class (and its overridings) induce an equivalence. Using partial models in place of code, it is also possible to analyze object-oriented designs in the abstract: investigating, for example, a view relationship amongst objects.The paper gives examples of annotations and such analyses. It presents (informally) a systematic translation of annotations into Alloy, a simple first-order logic with relational operators. By doing so, it makes Alloy's automatic analysis, which is based on state-of-the-art SAT solvers, applicable to the analysis of object-oriented programs, and demonstrates the power of a simple logic as the basis for an annotation language.


title: Portable serialization of CORBA objects: a reflective approach

authors:
Marc-Olivier Killijian
Juan-Carlos Ruiz-Garcia
Jean-Charles Fabre

abstract: The objective of this work is to define, implement and illustrate a portable serialization technique for CORBA objects. We propose an approach based on reflection: through open compilers facilities the internal state of CORBA objects is obtained and transformed into a language independent format using CORBA mechanisms. This state can be restored and used by objects developed using different languages and running on different software platforms. A tool was developed and applied to a Chat application as a case study. The proposed technique is used to exchange state information between a C++ and a Java incarnation of this CORBA service. An observer tool enables the object state to be displayed and analyzed by the user. The applicability of this technique to various domains is discussed. Beyond the interest of language reflection, we finally advocate that operating system and middleware reflection would also be powerful concepts to extend the work presented in this paper.


title: Access rights analysis for Java

authors:
Larry Koved
Marco Pistoia
Aaron Kershenbaum

abstract: Java 2 has a security architecture that protects systems from unauthorized access by mobile or statically configured code. The problem is in manually determining the set of security access rights required to execute a library or application. The commonly used strategy is to execute the code, note authorization failures, allocate additional access rights, and test again. This process iterates until the code successfully runs for the test cases in hand. Test cases usually do not cover all paths through the code, so failures can occur in deployed systems. Conversely, a broad set of access rights is allocated to the code to prevent authorization failures from occurring. However, this often leads to a violation of the "Principle of Least Privilege"This paper presents a technique for computing the access rights requirements by using a context sensitive, flow sensitive, interprocedural data flow analysis. By using this analysis, we compute at each program point the set of access rights required by the code. We model features such as multi-threading, implicitly defined security policies, the semantics of the Permission.implies method and generation of a security policy description. We implemented the algorithms and present the results of our analysis on a set of programs. While the analysis techniques described in this paper are in the context of Java code, the basic techniques are applicable to access rights analysis issues in non-Java-based systems.


title: Workflow enactment with continuation and future objects

abstract: An increasing number of software developers are turning to workflow to separate the logic and the control aspects in their applications, thus making them more amenable to change. However, in spite of recent efforts to standardize and provide reusable workflow components, many developers build their own. This is a challenging endeavor and involves solving problems which seem incompatible with the object paradigm and current object-oriented programming languages. In the context of an object-oriented workflow framework, this paper demonstrates a novel approach that resolves this impedance mismatch with techniques drawn from programming language theory. This successful cross-pollination narrows the gap between the results of decades of research in programming languages and developers working hard to cope with change.


title: Multiple instances and symbolic variables in executable sequence charts

authors:
Rami Marelly
David Harel
Hillel Kugler

abstract: We extend live sequence charts (LSCs), a highly expressive variant of sequence diagrams, and provide the extension with an executable semantics. The extension involves support for instances that can bind to multiple objects and symbolic variables that can bind to arbitrary values. The result is a powerful executable language for expressing behavioral requirements on the level of inter-object interaction. The extension is implemented in full in our play-engine tool, with which one can execute the requirements directly without the need to build or synthesize an intra-object system model. It seems that in addition to many advantages in testing and requirements engineering, for some kinds of systems this could lead to the requirements actually serving as the final implementation.


title: Integrating independent components with on-demand remodularization

authors:
Mira Mezini
Klaus Ostermann

abstract: This paper proposes language concepts that facilitate the separation of an application into independent reusable building blocks and the integration of pre-build generic software components into applications that have been developed by third party vendors. A key element of our approach are on-demand remodularizations, meaning that the abstractions and vocabulary of an existing code base are translated into the vocabulary understood by a set of components that are connected by a common collaboration interface. This general concept allows us to mix-and-match remodularizations and components on demand.


title: A constraint-based architecture for local search

authors:
Laurent Michel
Pascal Van Hentenryck

abstract: Combinatorial optimization problems are ubiquitous in numerous practical applications. Yet most of them are challenging, both from computational complexity and programming standpoints. Local search is one of the main approaches to address these problems. However, it often requires sophisticated incremental algorithms and data structures, and considerable experimentation. This paper proposes a constraint-based, object-oriented, architecture to reduce the development time of local search algorithms significantly. The architecture consists of declarative and search components. The declarative component includes invariants, which maintain complex expressions incrementally, and differentiable objects, which maintain properties that can be queried to evaluate the effect of local moves. Differentiable objects are high-level modeling concepts, such as constraints and functions, that capture combinatorial substructures arising in many applications. The search component supports various abstractions to specify heuristics and meta-heuristics. We illustrate the architecture with the language Comet and several applications, such as car sequencing and the progressive party problem. The applications indicate that the architecture allows for very high-level modeling of local search algorithms, while preserving excellent performance.


title: Incommunicado: efficient communication for isolates

authors:
Krzysztof Palacz
Jan Vitek
Grzegorz Czajkowski
Laurent Daynès

abstract: Executing computations in a single instance of safe language virtual machine can improve performance and overall platform scalability. It also poses various challenges. One of them is providing a fast inter-application communication mechanism. In addition to being efficient, such a mechanism should not violate any functional and non-functional properties of its environment, and should also support enforcement of application-specific security policies. This paper explores the design and implementation of a communication substrate for applications executing within a single Java virtual machine modified to enable safe and interference-free execution of isolated computations. Designing an efficient extension that does not break isolation properties and at the same time pragmatically offers an intuitive API has proven non-trivial. This paper demonstrates a set of techniques that lead to at least an eight-fold performance improvement over the in-process inter-application communication using standard mechanisms offered by the Java platform.


title: GCspy: an adaptable heap visualisation framework

authors:
Tony Printezis
Richard E. Jones

abstract: GCspy is an architectural framework for the collection, transmission, storage and replay of memory management behaviour. It makes new contributions to the understanding of the dynamic memory behaviour of programming languages (and especially object-oriented languages that make heavy demands on the performance of memory managers). GCspy's architecture allows easy incorporation into any memory management system: it is not limited to garbage-collected languages. It requires only small changes to the system in which it is incorporated but provides a simple to use yet powerful data-gathering API. GCspy scales to allow very large heaps to be visualised effectively and efficiently. It allows already-running, local or remote systems to be visualised and those systems to run at full speed outside the points at which data is gathered. GCspy's visualisation tool presents this information in a number of novel ways.Deep understanding of program behaviour is essential to the design of the next generation of garbage collectors and explicit allocators. Until now, no satisfactory tools have been available to assist the implementer in gaining an understanding of heap behaviour. GCspy has been demonstrated to be a practical solution to this dilemma. It has been used to analyse production Java virtual machines running applications of realistic sizes. Its use has revealed important insights into the interaction between application program and JVM and has led to the development of better garbage collectors.


title: Towards a formalization for COM part i: the primitive calculus

abstract: We introduce in this paper a typed calculus intended to capture the execution model of COM. The innovation of this calculus is to model very low-level aspects of the COM framework, specifically the notion of interface pointers. This is handled by specifying an allocation semantics for the calculus, thereby modeling heap allocation of interfaces explicitly. Having an explicit way of talking about interface pointers allows us to model in a reasonable way the notions of interface sharing and object identity. We introduce a type system that can be used to disambiguate between specification and implementation of interfaces. The type system moreover can capture a notion of COM conformance, that is, the legality of COM components. We discuss extensions of the calculus to handle subtyping of interfaces, dynamic interface negotiation and aggregation.


title: Creating and preserving locality of java applications at allocation and garbage collection times

authors:
Yefim Shuf
Manish Gupta
Hubertus Franke
Andrew W. Appel
Jaswinder Pal Singh

abstract: The growing gap between processor and memory speeds is motivating the need for optimization strategies that improve data locality. A major challenge is to devise techniques suitable for pointer-intensive applications. This paper presents two techniques aimed at improving the memory behavior of pointer-intensive applications with dynamic memory allocation, such as those written in Java. First, we present an allocation time object placement technique based on the recently introduced notion of prolific (frequently instantiated) types. We attempt to co-locate, at allocation time, objects of prolific types that are connected via object references. Then, we present a novel locality based graph traversal technique. The benefits of this technique, when applied to garbage collection (GC), are twofold: (i) it improves the performance of GC due to better locality during a heap traversal and (ii) it restructures surviving objects in a way that enhances locality. On multiprocessors, this technique can further reduce overhead due to synchronization and false sharing. The experimental results, on a well-known suite of Java benchmarks (SPECjvm98 [26], SPECjbb2000 [27], and jOlden [4]), from an implementation of these techniques in the Jikes RVM [1], are very encouraging. The object co-allocation technique improves application performance by up to 21% (10% on average) in the Jikes RVM configured with a non-copying mark-and-sweep collector. The locality-based traversal technique reduces GC times by up to 20% (10% on average) and improves the performance of applications by up to 14% (6% on average) in the Jikes RVM configured with a copying semi-space collector. Both techniques combined can improve application performance by up to 22% (10% on average) in the Jikes RVM configured with a non-copying mark-and-sweep collector.


title: Implementing distribution and persistence aspects with aspectJ

authors:
Sérgio Soares
Eduardo Laureano
Paulo Borba

abstract: This paper reports our experience using AspectJ, a generalpurpose aspect-oriented extension to Java, to implement distribution and persistence aspects in a web-based information system. This system was originally implemented in Java and restructured with AspectJ. Our main contribution is to show that AspectJ is useful for implementing several persistence and distribution concerns in the application considered, and other similar applications. We have also identified a few drawbacks in the language and suggest some minor modifications that could significantly improve similar implementations. Despite the drawbacks, we argue that the AspectJ implementation is superior to the pure Java implementation. Some of the aspects implemented in our experiment are abstract and constitute a simple aspect framework. The other aspects are application specific but we suggest that different implementations might follow the same aspect pattern. The framework and the pattern allow us to propose architecture-specific guidelines that provide practical advice for both restructuring and implementing certain kinds of persistent and distributed applications with AspectJ.


title: Sifting out the mud: low level C++ code reuse

authors:
Bjorn De Sutter
Bruno De Bus
Koenraad De Bosschere

abstract: More and more computers are being incorporated in devices where the available amount of memory is limited. This contrasts with the increasing need for additional functionality and the need for rapid application development. While object-oriented programming languages, providing mechanisms such as inheritance and templates, allow fast development of complex applications, they have a detrimental effect on program size. This paper introduces new techniques to reuse the code of whole procedures at the binary level and a supporting technique for data reuse. These techniques benefit specifically from program properties originating from the use of templates and inheritance. Together with our previous work on code abstraction at lower levels of granularity, they achieve additional code size reductions of up to 38% on already highly optimized and compacted binaries, without sacrificing execution speed. We have incorporated these techniques in Squeeze++, a prototype link-time binary rewriter for the Alpha architecture, and extensively evaluate them on a suite of 8 real-life C++ applications. The total code size reductions achieved post link-time (i.e. without requiring any change to the compiler) range from 27 to 70%, averaging at around 43%.


title: Write barrier removal by static analysis

authors:
Karen Zee
Martin C. Rinard

abstract: We present a new analysis for removing unnecessary write barriers in programs that use generational garbage collection. To our knowledge, this is the first static program analysis for this purpose. Our algorithm uses a pointer analysis to locate assignments that always create a reference from a younger object to an older object, then transforms the program to remove the write barriers normally associated with such assignments. We have implemented two transformations that reorder object allocations; these transformations can significantly increase the effectiveness of our write barrier removal algorithm.Our base technique assumes that the collector promotes objects in age order. We have developed an extension that enables the optimistic removal of write barriers, with the collector lazily adding each newly promoted object into a remembered set of objects whenever the compiler may have removed write barriers involving the object at statements that have yet to execute. This mechanism enables the application of our technique to virtually any memory management system that uses write barriers to enable generational garbage collection.Results from our implemented system show that our technique can remove substantial numbers of write barriers from the majority of the programs in our benchmark set, producing modest performance improvements of up to 6% of the overall execution time. Moreover, by dynamically instrumenting the executable, we are able to show that for six of our nine benchmark programs, our analysis is close to optimal in the sense that it removes the write barriers for almost all assignments that do not, in the observed execution, create a reference from an older object to a younger object. Finally, our results show that the overhead of our optimistic extension is negligible.


title: Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching

authors:
Yoav Zibin
Joseph Gil

abstract: The dispatching problem can be solved very efficiently in the single-inheritance~(SI) setting. In this paper we show how to extend one such solution to the multiple-inheritance~(MI) setting. This generalization comes with an increase to the space requirement by a small factor of κ This factor can be thought of as a metric of the complexity of the topology of the inheritance hierarchy.On a data set of~35 hierarchies totaling some~64 thousand types, our dispatching data structure, based on a novel type slicing technique, exhibits very significant improvements over previous dispatching techniques, not only in terms of the time for creating the underlying data structure, but also in terms of total space used.The cost is in the dispatching time, which is no longer constant, but doubly logarithmic in the number of types. Conversely, by using a simple binary search, dispatching time is logarithmic in the number of different implementations. In practice dispatching uses one indirect branch and, on average, only~2.5 binary branches.Our results also have applications to the space-efficient implementation of the more general problem of dispatching multi-methods.A by-product of our type slicing technique is an incremental algorithm for constant-time subtyping tests with favorable memory requirements. (The incremental version of the subtyping problem is to maintain the subtyping data structure in presence of additions of types to the inheritance hierarchy.)


title: A first-class approach to genericity

authors:
Eric E. Allen
Jonathan Bannet
Robert Cartwright

abstract: This paper describes how to add first-class generic types---including mixins---to strongly-typed OO languages with nominal subtyping such as Java and C#. A generic type system is "first-class" if generic types can appear in any context where conventional types can appear. In this context, a mixin is simply a generic class that extends one of its type parameters, e.g., a class C that extends T. Although mixins of this form are widely used in Cpp (via templates), they are clumsy and error-prone because Cpp treats mixins as macros, forcing each mixin instantiation to be separately compiled and type-checked. The abstraction embodied in a mixin is never separately analyzed.Our formulation of mixins using first-class genericity accommodates sound local (class-by-class) type checking. A mixin can be fully type-checked given symbol tables for each of the classes that it directly references---the same context in which Java performs incremental class compilation. To our knowledge, no previous formal analysis of first-class genericity in languages with nominal type systems has been conducted, which is surprising because nominal subtyping has become predominant in mainstream object-oriented programming languages.What makes our treatment of first-class genericity particularly interesting and important is the fact that it can be added to the existing Java language without any change to the underlying Java Virtual Machine. Moreover, the extension is backward compatible with legacy Java source and class files. Although our discussion of a practical implementation strategy focuses on Java, the same implementation techniques could be applied to other object-oriented languages such as C# or Eiffel that support incremental compilation, dynamic class loading, and nominal subtyping.


title: An on-the-fly mark and sweep garbage collector based on sliding views

authors:
Hezi Azatchi
Yossi Levanoni
Harel Paz
Erez Petrank

abstract: With concurrent and garbage collected languages like Java and C# becoming popular, the need for a suitable non-intrusive, efficient, and concurrent multiprocessor garbage collector has become acute. We propose a novel mark and sweep on-the-fly algorithm based on the sliding views mechanism of Levanoni and Petrank. We have implemented our collector on the Jikes Java Virtual Machine running on a Netfinity multiprocessor and compared it to the concurrent algorithm and to the stop-the-world collector supplied with Jikes JVM. The maximum pause time that we measured with our benchmarks over all runs was 2ms. In all runs, the pause times were smaller than those of the stop-the-world collector by two orders of magnitude and they were also always shorter than the pauses of the Jikes concurrent collector. Throughput measurements of the new garbage collector show that it outperforms the Jikes concurrent collector by up to 60%. As expected, the stop-the-world does better than the on-the-fly collectors with results showing about 10% difference.On top of being an effective mark and sweep on-the-fly collector standing on its own, our collector may also be used as a backup collector (collecting cyclic data structures) for the Levanoni-Petrank reference counting collector. These two algorithms perfectly fit sharing the same allocator, a similar data structure, and a similar JVM interface.


title: Mostly concurrent garbage collection revisited

authors:
Katherine Barabash
Yoav Ossia
Erez Petrank

abstract: The mostly concurrent garbage collection was presented in the seminal paper of Boehm et al. With the deployment of Java as a portable, secure and concurrent programming language, the mostly concurrent garbage collector turned out to be an excellent solution for Java's garbage collection task. The use of this collector is reported for several modern production Java Virtual Machines and it has been investigated further in academia.In this paper, we present a modification of the mostly concurrent collector, which improves the throughput, the memory footprint, and the cache behavior of the collector without foiling the other good qualities (such as short pauses and high scalability). We implemented our solution on the IBM production JVM and obtained a performance improvement of up to 26.7%, a reduction in the heap consumption by up to 13.4%, and no substantial change in the (short) pause times. The modified algorithm was subsequently incorporated into the IBM production JVM.


title: Applying traits to the smalltalk collection classes

authors:
Andrew P. Black
Nathanael Schärli
Stéphane Ducasse

abstract: Traits are a programming language technology that promote the reuse of methods between unrelated classes. This paper reports on a refactoring of the Smalltalk collections classes using traits. The original collection classes contained much duplication of code; traits let us remove all of it. We also found places where the protocols of the collections lacked uniformity; traits allowed us to correct these non-uniformities without code duplication.Traits also make it possible to reuse fragments of collection code outside of the existing hierarchy; for example, they make it easy to convert other collection-like things into true collections. Our refactoring reduced the number of methods in the collection classes by approximately 10 per cent. More importantly, understandability maintainability and reusability of the code were significantly improved.


title: Ulterior reference counting: fast garbage collection without a long wait

authors:
Stephen M. Blackburn
Kathryn S. McKinley

abstract: General purpose garbage collectors have yet to combine short pause times with high throughput. For example, generational collectors can achieve high throughput. They have modest average pause times, but occasionally collect the whole heap and consequently incur long pauses. At the other extreme, concurrent collectors, including reference counting, attain short pause times but with significant performance penalties. This paper introduces a new hybrid collector that combines copying generational collection for the young objects and reference counting the old objects to achieve both goals. It restricts copying and reference counting to the object demographics for which they perform well. Key to our algorithm is a generalization of deferred reference counting we call Ulterior Reference Counting. Ulterior reference counting safely ignores mutations to select heap objects. We compare a generational reference counting hybrid with pure reference counting, pure mark-sweep, and hybrid generational mark-sweep collectors. This new collector combines excellent throughput, matching a high performance generational mark-sweep hybrid, with low maximum pause times.


title: Lazy modular upgrades in persistent object stores

authors:
Chandrasekhar Boyapati
Barbara Liskov
Liuba Shrira
Chuang-Hue Moh
Steven Richman

abstract: Persistent object stores require a way to automatically upgrade persistent objects. Automatic upgrades are a challenge for such systems. Upgrades must be performed in a way that is efficient both in space and time, and that does not stop application access to the store. In addition, however, the approach must be modular: it must allow programmers to reason locally about the correctness of their upgrades similar to the way they would reason about regular code. This paper provides solutions to both problems. The paper first defines upgrade modularity conditions that any upgrade system must satisfy to support local reasoning about upgrades. The paper then describes a new approach for executing upgrades efficiently while satisfying the upgrade modularity conditions. The approach exploits object encapsulation properties in a novel way. The paper also describes a prototype implementation and shows that our upgrade system imposes only a small overhead on application performance.


title: Heap compression for memory-constrained Java environments

authors:
Guangyu Chen
Mahmut T. Kandemir
Narayanan Vijaykrishnan
Mary Jane Irwin
Bernd Mathiske
Mario Wolczko

abstract: Java is becoming the main software platform for consumer and embedded devices such as mobile phones, PDAs, TV set-top boxes, and in-vehicle systems. Since many of these systems are memory constrained, it is extremely important to keep the memory footprint of Java applications under control.The goal of this work is to enable the execution of Java applications using a smaller heap footprint than that possible using current embedded JVMs. We propose a set of memory management strategies to reduce heap footprint of embedded Java applications that execute under severe memory constraints. Our first contribution is a new garbage collector, referred to as the Mark-Compact-Compress (MCC) collector, that allows an application to run with a heap smaller than its footprint. An important characteristic of this collector is that it compresses objects when heap compaction is not sufficient for creating space for the current allocation request. In addition to employing compression, we also consider a heap management strategy and associated garbage collector, called MCL (Mark-Compact-Lazy Allocate), based on lazy allocation of object portions. This new collector operates like the conventional Mark-Compact (MC) collector, but takes advantage of the observation that many Java applications create large objects, of which only a small portion is actually used. In addition, we also combine MCC and MCL, and present MCCL (Mark-Compact-Compress-Lazy Al-locate), which outperforms both MCC and MCL.We have implemented these collectors using KVM, and performed extensive experiments using a set of ten embedded Java applications. We have found our new garbage collection strategies to be useful in two main aspects. First, they reduce the minimum heap size necessary to execute an application without out-of-memory exception. Second, our strategies reduce the heap occupancy. That is, at a given time, they reduce the heap memory requirement of the application being executed. We have also conducted experiments with a more aggressive object compression strategy and discussed its main advantages.


title: Saving the world from bad beans: deployment-time confinement checking

authors:
David G. Clarke
Michael Richmond
James Noble

abstract: The Enterprise JavaBeans (EJB) framework requires developers to preserve architectural integrity constraints when writing EJB components. Breaking these constraints allows components to violate the transaction protocol, bypass security mechanisms, disable object persistence, and be susceptible to malicious attacks from other EJBs. We present an object confinement discipline that allows static verification of components' integrity as they are deployed into an EJB server. The confinement rules are simple for developers to understand, require no annotation to the code of EJB components, and can be efficiently enforced in existing EJB servers.


title: MJ: a rational module system for Java and its applications

authors:
John Corwin
David F. Bacon
David Grove
Chet Murthy

abstract: While Java provides many software engineering benefits, it lacks a coherent module system and instead provides only packages (which are primarily a name space mechanism) and classloaders (which are very low-level). As a result, large Java applications suffer from unexpected interactions between independent components, require complex CLASSPATH definitions, and are often extremely complex to install and maintain. We have implemented a module system for Java called MJ that is implemented with class loaders, but provides a much higher-level interface. High-level properties can be specified in a module definition and are enforced by the module system as new modules are loaded. To experimentally validate the ability of MJ to properly handle the complex module inter-relationships found in large Java server systems, we replaced the classloader mechanisms of Apache Tomcat 4.1.18 [27] with 30 MJ modules. The modified Tomcat is functionally identical to the original, but requires no CLASSPATH definitions, and will operate correctly even if user code loads a different version of a module used by Tomcat, such as the Xerces XML parser [31]. Furthermore, by making a small change to the Java core libraries enabled by MJ, we obtained a 30% performance improvement in a servlet microbenchmark.


title: Automatic detection and repair of errors in data structures

authors:
Brian Demsky
Martin C. Rinard

abstract: We present a system that accepts a specification of key data structure consistency constraints, then dynamically detects and repairs violations of these constraints, enabling the program to continue to execute productively even in the face of otherwise crippling errors. Our experience using our system indicates that the specifications are relatively easy to develop once one understands the data structures. Furthermore, for our set of benchmark applications, our system can effectively repair inconsistent data structures and enable the program to continue to operate successfully.


title: Dynamic metrics for java

authors:
Bruno Dufour
Karel Driesen
Laurie J. Hendren
Clark Verbrugge

abstract: In order to perform meaningful experiments in optimizing compilation and run-time system design, researchers usually rely on a suite of benchmark programs of interest to the optimization technique under consideration. Programs are described as numeric, memory-intensive, concurrent, or object-oriented, based on a qualitative appraisal, in some cases with little justification. We believe it is beneficial to quantify the behaviour of programs with a concise and precisely defined set of metrics, in order to make these intuitive notions of program behaviour more concrete and subject to experimental validation. We therefore define and measure a set of unambiguous, dynamic, robust and architecture-independent metrics that can be used to categorize programs according to their dynamic behaviour in five areas: size, data structure, memory use, concurrency, and polymorphism. A framework computing some of these metrics for Java programs is presented along with specific results demonstrating how to use metric data to understand a program's behaviour, and both guide and evaluate compiler optimizations.


title: How java programs interact with virtual machines at the microarchitectural level

authors:
Lieven Eeckhout
Andy Georges
Koenraad De Bosschere

abstract: Java workloads are becoming increasingly prominent on various platforms ranging from embedded systems, over general-purpose computers to high-end servers. Understanding the implications of all the aspects involved when running Java workloads, is thus extremely important during the design of a system that will run such workloads. In other words, understanding the interaction between the Java application, its input and the virtual machine it runs on, is key to a succesful design. The goal of this paper is to study this complex interaction at the microarchitectural level, e.g., by analyzing the branch behavior, the cache behavior, etc. This is done by measuring a large number of performance characteristics using performance counters on an AMD K7 Duron microprocessor. These performance characteristics are measured for seven virtual machine configurations, and a collection of Java benchmarks with corresponding inputs coming from the SPECjvm98 benchmark suite, the SPECjbb2000 benchmark suite, the Java Grande Forum benchmark suite and an open-source raytracer, called Raja with 19 scene descriptions. This large amount of data is further analyzed using statistical data analysis techniques, namely principal components analysis and cluster analysis. These techniques provide useful insights in an understandable way.From our experiments, we conclude that (i) the behavior observed at the microarchitectural level is primarily determined by the virtual machine for small input sets, e.g., the SPECjvm98 s1 input set; (ii) the behavior can be quite different for various input sets, e.g., short-running versus long-running benchmarks; (iii) for long-running benchmarks with few hot spots, the behavior can be primarily determined by the Java program and not the virtual machine, i.e., all the virtual machines optimize the hot spots to similarly behaving native code; (iv) in general, the behavior of a Java application running on one virtual machine can be significantly different from running on another virtual machine. These conclusions warn researchers working on Java workloads to be careful when using a limited number of Java benchmarks or virtual machines since this might lead to biased conclusions.


title: Declaring and checking non-null types in an object-oriented language

authors:
Manuel Fähndrich
K. Rustan M. Leino

abstract: Distinguishing non-null references from possibly-null references at the type level can detect null-related errors in object-oriented programs at compile-time. This paper gives a proposal for retrofitting a language such as C# or Java with non-null types. It addresses the central complications that arise in constructors, where declared non-null fields may not yet have been initialized, but the partially constructed object is already accessible. The paper reports experience with an implementation for annotating and checking null-related properties in C# programs.


title: A comparative study of language support for generic programming

authors:
Ronald Garcia
Jaakko Järvi
Andrew Lumsdaine
Jeremy G. Siek
Jeremiah Willcock

abstract: Many modern programming languages support basic generic programming, sufficient to implement type-safe polymorphic containers. Some languages have moved beyond this basic support to a broader, more powerful interpretation of generic programming, and their extensions have proven valuable in practice. This paper reports on a comprehensive comparison of generics in six programming languages: C++, Standard ML, Haskell, Eiffel, Java (with its proposed generics extension), and Generic C. By implementing a substantial example in each of these languages, we identify eight language features that support this broader view of generic programming. We find these features are necessary to avoid awkward designs, poor maintainability, unnecessary run-time checks, and painfully verbose code. As languages increasingly support generics, it is important that language designers understand the features necessary to provide powerful generics and that their absence causes serious difficulties for programmers.


title: Language support for lightweight transactions

authors:
Tim Harris
Keir Fraser

abstract: Concurrent programming is notoriously difficult. Current abstractions are intricate and make it hard to design computer systems that are reliable and scalable. We argue that these problems can be addressed by moving to a declarative style of concurrency control in which programmers directly indicate the safety properties that they require. In our scheme the programmer demarks sections of code which execute within lightweight software-based transactions that commit atomically and exactly once. These transactions can update shared data, instantiate objects, invoke library features and so on. They can also block, waiting for arbitrary boolean conditions to become true. Transactions which do not access the same shared memory locations can commit concurrently. Furthermore, in general, no performance penalty is incurred for memory accesses outside transactions.We present a detailed design of this proposal along with an implementation and evaluation. We argue that the resulting system (i) is easier for mainstream programmers to use, (ii) prevents lock-based priority-inversion and deadlock problems and (iii) can offer performance advantages.

awards: Most Influential OOPSLA Paper (awarded 2013)


title: Connectivity-based garbage collection

authors:
Martin Hirzel
Amer Diwan
Matthew Hertz

abstract: We introduce a new family of connectivity-based garbage collectors (Cbgc) that are based on potential object-connectivity properties. The key feature of these collectors is that the placement of objects into partitions is determined by performing one of several forms of connectivity analyses on the program. This enables partial garbage collections, as in generational collectors, but without the need for any write barrier.The contributions of this paper are 1) a novel family of garbage collection algorithms based on object connectivity; 2) a detailed description of an instance of this family; and 3) an empirical evaluation of Cbgc using simulations. Simulations help explore a broad range of possibilities for Cbgc, ranging from simplistic ones that determine connectivity based on type information to oracular ones that use run-time information to determine connectivity. Our experiments with the oracular Cbgc configurations give an indication of the potential for Cbgc and also identify weaknesses in the realistic configurations. We found that even the simplistic implementations beat state-of-the-art generational collectors with respect to some metrics (pause times and memory footprint).


title: Effectiveness of cross-platform optimizations for a java just-in-time compiler

authors:
Kazuaki Ishizaki
Mikio Takeuchi
Kiyokuni Kawachiya
Toshio Suganuma
Osamu Gohda
Tatsushi Inagaki
Akira Koseki
Kazunori Ogata
Motohiro Kawahito
Toshiaki Yasue
Takeshi Ogasawara
Tamiya Onodera
Hideaki Komatsu
Toshio Nakatani

abstract: This paper describes the system overview of our Java Just-In-Time (JIT) compiler, which is the basis for the latest production version of IBM Java JIT compiler that supports a diversity of processor architectures including both 32-bit and 64-bit modes, CISC, RISC, and VLIW architectures. In particular, we focus on the design and evaluation of the cross-platform optimizations that are common across different architectures. We studied the effectiveness of each optimization by selectively disabling it in our JIT compiler on three different platforms: IA-32, IA-64, and PowerPC. Our detailed measurements allowed us to rank the optimizations in terms of the greatest performance improvements with the smallest compilation times. The identified set includes method inlining only for tiny methods, exception check eliminations using forward dataflow analysis and partial redundancy elimination, scalar replacement for instance and class fields using dataflow analysis, optimizations for type inclusion checks, and the elimination of merge points in the control flow graphs. These optimizations can achieve 90% of the peak performance for two industry-standard benchmark programs on these platforms with only 34% of the compilation time compared to the case for using all of the optimizations.