To understand, debug, and predict the performance of complex software systems, we develop the concept of probabilistic performance annotations. In essence, we annotate components (e.g., methods) with a relation between a measurable performance metric, such as running time, and one or more features of the input or the state of that component. We use two forms of regression analysis: regression trees and mixture models. Such relations can capture non-trivial behaviors beyond the more classic algorithmic complexity of a component. We present a method to derive such annotations automatically by generalizing observed measurements. We illustrate the use of our approach on three complex systems---the ownCloud distributed storage service; the MySQL database system; and the x264 video encoder library and application---producing non-trivial characterizations of the performance. Notably, we isolate a performance regression and identify the root cause of a second performance bug in MySQL.

Developers of performance sensitive production software are in a dilemma: performance regression tests are too costly to run at each commit, but skipping the tests delays and complicates performance regression detection. Ideally, developers would have a system that predicts whether a given commit is likely to impact performance and suggests which tests to run to detect a potential performance regression. Prior approaches towards this problem require static or dynamic analyses that limit their generality and applicability. This paper presents an approach that is simple and general, and that works surprisingly well for real applications.

Summary form only given. Performance is critical to datacenter applications: a poorly performing application provides poor experience to end users and also wastes hardware resources (network, disk, CPU). Unfortunately, these applications are huge (serving each user request can involve hundreds to thousands of machines) and complex (many interacting components often developed and managed by different teams). Thus, these applications are notoriously hard to understand and optimize. This talk distills key insights from our experience in analyzing and optimizing datacenter applications (particularly Gmail) at Google.

SUMMARY While profiling is invaluable for debugging performance problems that affect the common case, it is of little help in tracking performance problems that affect the slowest 1% of the operations (i.e., long‐tail latencies). For Web service providers, these long‐tail latencies affect both the cost of the service and the user experience. Because interactions between operations are often responsible for long‐tail latency, we must analyze fine‐grained traces to investigate their cause. Unfortunately, analyzing traces is difficult because one needs to reason over long chains of events and because this reasoning often requires significant domain knowledge about what the event sequences mean. This paper shows how we can use formulas in linear‐temporal logic to analyze traces. Given these formulas, our system searches through traces to find matches for these formulas and extracts relevant information from the matches. We demonstrate that our system is scalable and enables us to investigate long‐tail performance problems at Google. Copyright © 2014 John Wiley & Sons, Ltd.

Research has shown that correctly conducting and analysing computer performance experiments is difficult. This paper investigates what is necessary to conduct successful computer performance evaluation by attempting to repeat a prior experiment: the comparison between two Linux schedulers.

A static analysis design is sufficient if it can prove the property of interest with an acceptable number of false alarms. Ultimately, the only way to confirm that an analysis design is sufficient is to implement it and run it on real-world programs. If the evaluation shows that the design is insufficient, the designer must return to the drawing board and repeat the process--wasting expensive implementation effort over and over again. In this paper, we make the observation that there is a minimal range of code needed to prove a property of interest under an ideal static analysis; we call such a range of code a validation scope. Armed with this observation, we create a dynamic measurement framework that quantifies validation scopes and thus enables designers to rule out insufficient designs at lower cost. A novel attribute of our framework is the ability to model aspects of static reasoning using dynamic execution measurements. To evaluate the flexibility of our framework, we instantiate it on an example property--null dereference errors--and measure validation scopes on real-world programs. We use a broad range of metrics that capture the difficulty of analyzing programs along varying dimensions. We also examine how validation scopes evolve as developers fix null dereference errors and as code matures. We find that bug fixes shorten validation scopes, that longer validation scopes are more likely to be buggy, and that overall validation scopes are remarkably stable as programs evolve.

Abstract Because software continues to grow in size and complexity, programmers increasingly rely on productivity tools to understand, debug, and modify their programs. These tools typically use program analyses to produce information for the programmer. This is problematic because it is based on the assumption that the programmer and program analyses all use the same vocabulary. If the programmer and analyses did not use the same vocabulary then the results of the analyses will be meaningless to the programmer. For example, ‘v124 may be NULL’ does not mean much to the programmer but ‘myStack may be NULL’ is meaningful. Often, the programmer and analyses prefer different vocabularies. While the programmer prefers his programs' source code, an analysis will prefer a simplified representation. Unfortunately, writing an analysis that works on the source code is difficult because the analysis must deal with the idiosyncracies of the source language (e.g. nested classes). In comparison, writing an analysis on SSA form is easy but the output of the analysis is not meaningful to the programmer; it must somehow be translated into something the programmer understands. We present a system, RTalk, that makes it easy to support both the programmers' and the analysis' needs. RTalk generates a translator between the programmers' and the analysis' vocabulary. Thus both the programmer and the analysis can use the vocabulary most natural to them. We demonstrate the effectiveness of RTalk by describing program understanding and program optimization tools that we have already built using RTalk. Copyright © 2011 John Wiley & Sons, Ltd.

Abstract The performance of a program often varies significantly over the course of the program's run. Thus, to understand the performance of a program it is valuable to look not just at end‐to‐end metrics (e.g. total number of cache misses) but also the time‐varying performance of the program. Unfortunately, analyzing time‐varying performance is both cumbersome and difficult. This paper makes three contributions, all geared toward helping others in working with traces. First, it describes a system, the TraceAnalyzer, designed specifically for working with performance traces; a performance trace captures the time‐varying performance of a program run. Second, it describes lessons that we have learned from many years of working with these traces. Finally, it uses a case study to demonstrate how we have used the TraceAnalyzer to understand a performance anomaly. Copyright © 2010 John Wiley & Sons, Ltd.

Performance analysts profile their programs to find methods that are worth optimizing: the "hot" methods. This paper shows that four commonly-used Java profilers (xprof , hprof , jprofile, and yourkit) often disagree on the identity of the hot methods. If two profilers disagree, at least one must be incorrect. Thus, there is a good chance that a profiler will mislead a performance analyst into wasting time optimizing a cold method with little or no performance improvement.

Abstract Modern systems are enormously complex; many applications today comprise millions of lines of code, make extensive use of software frameworks, and run on complex, multi‐tiered, run‐time systems. Understanding the performance of these applications is challenging because it depends on the interactions between the many software and the hardware components. This paper describes and evaluates an interactive and iterative methodology, temporal vertical profiling, for understanding the performance of applications. There are two key insights behind temporal vertical profiling. First, we need to collect and reason across information from multiple layers of the system before we can understand an application's performance. Second, application performance changes over time and thus we must consider the time‐varying behavior of the application instead of aggregate statistics. We have developed temporal vertical profiling from our own experience of analyzing performance anomalies and have found it very helpful for methodically exploring the space of hardware and software components. By representing an application's behavior as a set of metrics, where each metric is represented as a time series, temporal vertical profiling provides a way to reason about performance across system layers, regardless of their level of abstraction, and independent of their semantics. Temporal vertical profiling provides a methodology to explore a large space of metrics, hundreds of metrics even for small benchmarks, in a systematic way. Copyright © 2010 John Wiley & Sons, Ltd.

This paper presents a surprising result: changing a seemingly innocuous aspect of an experimental setup can cause a systems researcher to draw wrong conclusions from an experiment. What appears to be an innocuous aspect in the experimental setup may in fact introduce a significant bias in an evaluation. This phenomenon is called measurement bias in the natural and social sciences.

Modern object-oriented languages have complex features that cause programmers to overspecify their programs. This overspecification hinders automatic optimizers, since they must preserve the overspecified semantics. If an optimizer knew which semantics the programmer intended, it could do a better job.

Prior work has found call path profiles to be useful for optimizers and programmer-productivity tools. Unfortunately, previous approaches for collecting path profiles are expensive: they need to either execute additional instructions (to track calls and returns) or they need to walk the stack. The state-of-the-art techniques for call path profiling slow down the program by 7% (for C programs) and 20% (for Java programs). This paper describes an innovative technique that collects minimal information from the running program and later (offline) infers the full call paths from this information.

We show two severe problems with the state of the art in empirical computer system performance evaluation, observer effect and measurement context bias, and we outline the path toward a solution.

With programs getting larger and often more complex with each new release, programmers need all the help they can get in understanding and transforming programs. Fortunately, modern development environments, such as Eclipse, incorporate tools for understanding, navigating, and transforming programs. These tools typically use program analyses to extract relevant properties of programs.

Modern programs make extensive use of reusable software libraries. For example, a study of a number of large Java applications shows that between 17% and 30% of the classes in those applications use container classes defined in the java.util package. Given this extensive code reuse in Java programs, it is important for the interfaces of reusable classes to be well documented. An interface is well documented if it satisfies the following requirements: (1) the documentation completely describes how to use the interface; (2) the documentation is clear; (3) the documentation is unambiguous; and (4) any deviation between the documentation and the code is machine detectable. Unfortunately, documentation in natural language, which is the norm, does not satisfy the above requirements. Formal specifications can satisfy them but they are difficult to develop, requiring significant effort on the part of programmers. To address the practical difficulties with formal specifications, we describe and evaluate a tool to help programmers write and debug algebraic specifications. Given an algebraic specification of a class, our interpreter generates a prototype that can be used within an application like a regular Java class. When running an application that uses the prototype, the interpreter prints error messages that tell the developer in which way the specification is incomplete or inconsistent with a hand-coded implementation of the class. We use case studies to demonstrate the usefulness of our system.

In the above titled paper (ibid., vol. 33, no. 8, pp. 526-543, Aug 07), there were several mistakes. The corrections are presented here.

Performance analysts commonly use trace-based data containing hardware and software metrics to understand performance. The trace data is generated by instrumenting the code to increment a counter when an event occurs and to collect hardware and software metrics in a trace. Unfortunately, the act of collecting a trace can perturb the behavior that the trace is frying to capture. In this paper, we gain an understanding of perturbation due to measurement instrumentation of the system. We identify two mechanisms to quantify perturbation: inner and outer perturbation. Using inner perturbation, a performance analyst can determine when a run is perturbed by collecting too much information. Using outer perturbation, the performance analyst can determine if she can use the data from multiple runs as if the data were all from a single run. Our evaluation of these mechanisms lead to two results. First, we are surprised to find that even with minimal instrumentation overhead, which increased instructions executed by less than 3%, high perturbation resulted, which prevented one from correctly reasoning about metrics within a trace or across traces. Second, the instrumentation of different software metrics interact in subtle, and not always obvious, ways making the impact of instrumentation on perturbation difficult, if not impossible, to predict. Finally, we outline a methodology for collecting data while avoiding perturbation. When inner perturbation occurs, the performance analyst can spread out the data collection over multiple runs. When outer perturbation occurs, she can try different strategies for spreading out the data collection over multiple runs.

The performance of computer systems varies over the course of their execution. A system may perform well during some parts of its execution and poorly during others. To understand why a system behaves in this way performance analysts need to study its time-varying behavior. Fortunately, modern microprocessors support hardware performance monitors which enable performance analysts to collect time-varying metrics with relative ease. Unfortunately, even though modern microprocessors can collect hundreds of metrics, they can collect only a few of these metrics simultaneously. Prior work has proposed time-interpolation techniques for circumventing this limitation. Time interpolation collects different metrics at different points in time, either within the same trace (multiplexing) or in different traces (trace alignment), and interpolates the results to allow reasoning across all metrics at the same points in time. This paper introduces and uses a novel approach for evaluating time interpolation techniques. This evaluation leads to insights that improve both multiplexing and trace-alignment. Specifically, this paper (i) improves the effectiveness and applicability of the best performing trace alignment technique in prior work; and (ii) introduces criteria that performance analysts can use to determine whether or not to trust multiplexing or trace alignment results for their particular situation. Finally, this paper evaluates time interpolation techniques by exploring their performance in a wide variety of situations and on programs written in two different programming languages, C and Java, and on two different architectures, Pentium 4 and POWER4.

Pointer analysis benefits many useful clients, such as compiler optimizations and bug finding tools. Unfortunately, common programming language features such as dynamic loading, reflection, and foreign language interfaces, make pointer analysis difficult. This article describes how to deal with these features by performing pointer analysis online during program execution. For example, dynamic loading may load code that is not available for analysis before the program starts. Only an online analysis can analyze such code, and thus support clients that optimize or find bugs in it. This article identifies all problems in performing Andersen's pointer analysis for the full Java language, presents solutions to these problems, and uses a full implementation of the solutions in a Java virtual machine for validation and performance evaluation. Our analysis is fast: On average over our benchmark suite, if the analysis recomputes points-to results upon each program change, most analysis pauses take under 0.1 seconds, and add up to 64.5 seconds.

Modern JVM implementations interleave execution with compilation of “hot” methods to achieve reasonable performance. Since compilation overhead impacts the execution time of the application and induces run-time pauses, we explore offloading compilation onto a compilation server. In this article, we present the design, implementation, and evaluation of a compilation server that compiles and optimizes Java bytecodes on behalf of its clients. We show that the compilation server provides the following benefits for our benchmark programs: (i) lower execution time by reducing the compilation overhead and by enabling more aggressive optimizations; (ii) lower memory allocation by eliminating allocations due to optimizing compilation and the footprint of the optimizing compiler; (iii) lower execution time of the application due to sharing of profile information across different runs of the same application and runs of different applications. We implemented the compilation server in Jikes RVM, and our results indicate that it can reduce running time by an average of 20.5%, interruptions due to compilation by an average of 81.0%, and dynamic memory allocation by 8.6% for our benchmark programs. Simulation results indicate that our current implementation of the compilation server can handle more than 50 concurrent clients while still allowing them to outperform the best performing adaptive configuration.

Modern programs make extensive use of reusable software libraries. For example, we found that 17% to 30% of the classes in a number of large Java applications use the container classes from the java.util package. Given this extensive code reuse in Java programs, it is important for the reusable interfaces to have clear and unambiguous documentation. Unfortunately, most documentation is expressed in English, and therefore does not always satisfy these requirements. Worse yet, there is no way of checking that the documentation is consistent with the associated code. Formal specifications present an alternative which does not suffer from these problems; however, formal specifications are notoriously hard to write. To alleviate this difficulty, we have implemented a tool which automatically derives documentation in the form of formal specifications. Our tool probes Java classes by invoking them on dynamically generated tests and captures the information observed during their execution as algebraic axioms. While the tool is not complete or correct from a formal perspective we demonstrate that it discovers many useful axioms when applied to container classes. These axioms then form an initial formal documentation of the class they describe.

For many performance analysis problems, the ability to reason across traces is invaluable. However, due to non-determinism in the OS and virtual machines, even two identical runs of an application yield slightly different traces. For example, it is unlikely that two identical runs of an application will suffer context switches at exactly the same points. These sorts of variations across traces make it difficult to reason across traces. This paper describes and evaluates an algorithm, dynamic time warping (DTW) that can be used to align traces, thus enabling us to reason across traces. While DTW comes from prior work our use of DTW is novel. Also we describe and evaluate an enhancement to DTW that significantly improves the quality of its alignments. Our results show that for applications whose performance varies significantly over time, DTW does a great job at aligning the traces. For applications whose performance stays largely constant for significant periods of time, the original DTW does not perform well; however, our enhanced DTW performs much better.

Current literature states that the undergraduate curriculum can no longer afford the luxury of a traditional compiler construction course. Nevertheless, there is an increasing need for an understanding of how to design and implement domain-specific languages. This paper presents a modern course in compiler construction, designed to provide a student with the capability of quickly constructin robust processors for a variety of language-related applications.

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

Abstract Compiler optimizations are difficult to implement and add complexity to a compiler. For this reason, compiler writers are selective about implementing them: they implement only the ones that they believe will be beneficial. To support compiler writers in this, we describe a method for measuring the cost and benefits of compiler optimizations, both individually and in synergy with other optimizations. We demonstrate our method by presenting results for the optimizations implemented in the Jikes Research Virtual Machine on the PowerPC and IA32 platforms. Copyright © 2006 John Wiley & Sons, Ltd.

Library developers who have to evolve a library to accommodate changing requirements often face a dilemma: Either they implement a clean, efficient solution but risk breaking client code, or they maintain compatibility with client code, but pay with increased design complexity and thus higher maintenance costs over time.We address this dilemma by presenting a lightweight approach for evolving application programming interfaces (APIs), which does not depend on version control or configuration management systems. Instead, we capture API refactoring actions as a developer evolves an API. Users of the API can then replay the refactorings to bring their client software components up to date.We present catchup!, an implementation of our approach that captures and replays refactoring actions within an integrated development environment semi-automatically. Our experiments suggest that our approach could be valuable in practice.

Last year at OOPSLA we presented a methodology, vertical profiling, for understanding the performance of object-oriented programs. The key insight behind this methodology is that modern programs run on top of many layers (virtual machine, middleware, etc) and thus we need to collect and combine information from all layers in order to understand system performance. Although our methodology was able to explain previously unexplained performance phenomena, it was extremely labor intensive. In this paper we describe and evaluate techniques for automating two significant activities of vertical profiling: trace alignment and correlation. Trace alignment aligns traces obtained from separate runs so that one can reason across the traces. We are not aware of any prior approach that effectively and automatically aligns traces. Correlation sifts through hundreds of metrics to find ones that have a bearing on a performance anomaly of interest. In prior work we found that statistical correlation was only sometimes effective. We have identified highly-effective approaches for both activities.For aligning traces we explore dynamic time warping, and for correlation we explore eight correlators based on statistical correlation, distance measures, and piecewise linear segmentation. Although we explore these activities in the context of vertical profiling, both activities are widely applicable in the performance analysis area.

Last year we described the PL-Detective, a system for building exercises and demonstrations in a programming languages course. One of the main goals of the PL-Detective was to provide an experimental environment with which students could interact in order to discover the information that they needed to complete the exercise. In this paper we evaluate the PL-Detective with respect to this goal. We present data from a class of 29 groups of two or three students that used the PL-Detective for 11 exercises. Our data shows that students are both effective and efficient at getting information from the PL-Detective.

Despite their benefits, programmers rarely use formal specifications, because they are difficult to write and they require an up front investment in time. To address these issues, we present a tool that helps programmers write and debug algebraic specifications. Given an algebraic specification, our tool instantiates a prototype that can be used just like any regular Java class. The tool can also modify an existing application to use the prototype generated by the interpreter instead of a hand-coded implementation. The tool improves the usability of algebraic specifications in the following ways: (i) A programmer can run an algebraic specification to study its behavior. The tool reports in which way a specification is incomplete for a client application. (ii) The tool can check whether a specification and a hand-coded implementation behave the same for a particular run of a client application. (iii) A prototype can be used when a hand-coded implementation is not yet available. Two case studies demonstrate how to use the tool.

Generics offer significant software engineering benefits since they provide code reuse without compromising type safety. Thus generics will be added to the Java language in the next release. While this extension to Java will help programmers when they are writing new code, it will not help legacy code unless it is rewritten to use generics. In our experience, manually modifying existing programs to use generics is complex and can be error prone and labor intensive.

Object-oriented programming languages provide a rich set of features that provide significant software engineering benefits. The increased productivity provided by these features comes at a justifiable cost in a more sophisticated runtime system whose responsibility is to implement these features efficiently. However, the virtualization introduced by this sophistication provides a significant challenge to understanding complete system performance, not found in traditionally compiled languages, such as C or C++. Thus, understanding system performance of such a system requires profiling that spans all levels of the execution stack, such as the hardware, operating system, virtual machine, and application.

The educational literature recognizes that people go through a number of stages in their intellectual development. During the first stage, called received knowledge or dualism, people expect knowledge to be handed to them by authority figures (thus "received") and think in terms of black and white (thus "dualism"). Our experience indicates that many computer science students are at this first stage of learning. To help students move beyond this stage, we describe a system and strategy, the PL-detective, to be used in a "concepts of programming languages" course. Assignments using this system directly confront students with the notion that there are often multiple equally good answers and that discussion with students (rather than asking the instructor) is an effective way of learning how to reason.

Our industrial advisory boards tell us that our students are well prepared technically, but they lack important group work skills. Simply adding project courses and requiring that assignments be done in groups has not improved the situation. A careful study of student culture in Computer Science has uncovered barriers to collaboration, which can be overcome only by pervasive changes in the way we approach our curriculum.

The educational literature recognizes that people go through a number of stages in their intellectual development. During the first stage, called received knowledge or dualism , people expect knowledge to be handed to them by authority figures (thus “received”) and think in terms of black and white (thus “dualism”). Our experience indicates that many computer science students are at this first stage of learning. To help students move beyond this stage, we describe a system and strategy, the PL-Detective, to be used in a Concepts of Programming Languages course. Assignments using this system directly confront students with the notion that they can create knowledge via interactions with the PL-Detective and that discussion with students (rather than asking the instructor) is an effective way of learning how to reason. We present experimental results that show that the PL-Detective is effective in helping students move beyond the stage of received knowledge.

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

Concepts taught in large, lower-division computer science courses are carefully explained in standard textbooks. Thus we hypothesized that the classroom experience should not consist primarily of a restatement of those explanations by the professor. Instead, it should provide an opportunity for the students to learn through a process of conversation among themselves and with the professor. We were able to establish such a process in a sophomore-level course with an enrollment of 116 students. This change led to a doubling of the percentage of A and A- grades compared to historical values.

While caches are effective at avoiding most main-memory accesses, the few remaining memory references are still expensive. Even one cache miss per one hundred accesses can double a program's execution time. To better tolerate the data-cache miss latency, architects have proposed various speculation mechanisms, including load-value prediction. A load-value predictor guesses the result of a load so that the dependent instructions can immediately proceed without having to wait for the memory access to complete. To use the prediction resources most effectively, speculation should be restricted to loads that are likely to miss in the cache and that are likely to be predicted correctly. Prior work has considered hardware- and profile-based methods to make these decisions. Our work focuses on making these decisions at compile time. We show that a simple compiler classification is effective at separating the loads that should be speculated from the loads that should not. We present results for a number of C and Java programs and demonstrate that our results are consistent across programming languages and across program inputs.

In industry, programmers work in groups to design and implement substantial pieces of software. In contrast, most programs that students write in classes are toy programs involving little or no group work. To address this discrepancy, we have developed a software infrastructure that aims to teach group work skills to students in computer science courses and also enables students to tackle larger and more significant projects. We are in the process of deploying this infrastructure in a three course sequence at the University of Colorado: Data Structures---Programming Languages---Compiler Construction.

The effectiveness of garbage collectors and leak detectors in identifying dead objects depends on theaccuracyof their reachability traversal. Accuracy has two orthogonal dimensions: (i) whether the reachability traversal can distinguish between pointers and nonpointers (type accuracy), and (ii) whether the reachability traversal can identify memory locations that will be dereferenced in the future (liveness accuracy). This article presents an experimental study of the importance of type and liveness accuracy for reachability traversals. We show that liveness accuracy reduces the reachable heap size by up to 62% for our benchmark programs. However, the simpler liveness schemes (e.g., intraprocedural analysis of local variables) are largely ineffective for our benchmark runs: one must analyze global variables using interprocedural analysis to obtain significant benefits. Type accuracy has an insignificant impact on a garbage collector's ability to find unreachable objects in our benchmark runs. We report results for programs written in C, C++, and Eiffel.

Abstract Pointer traversals pose significant overhead to the execution of object‐oriented programs, since every access to an object's state requires a pointer dereference. Eliminating redundant pointer traversals reduces both instructions executed as well as redundant memory accesses to relieve pressure on the memory subsystem. We describe an approach to elimination of redundant access expressions that combines partial redundancy elimination (PRE) with type‐based alias analysis (TBAA). To explore the potential of this approach we have implemented an optimization framework for Java class files incorporating TBAA‐based PRE over pointer access expressions. The framework is implemented as a class‐file‐to‐class‐file transformer; optimized classes can then be run in any standard Java execution environment. Our experiments demonstrate improvements in the execution of optimized code for several Java benchmarks running in diverse execution environments: the standard interpreted JDK virtual machine, a virtual machine using ‘just‐in‐time’ compilation, and native binaries compiled off‐line (‘way‐ahead‐of‐time’). Overall, however, our experience is of mixed success with the optimizations, mainly because of the isolation between our optimizer and the underlying execution environments which prevents more effective cooperation between them. We isolate the impact of access path PRE using TBAA, and demonstrate that Java's requirement of precise exceptions can noticeably impact code‐motion optimizations like PRE. Copyright © 2001 John Wiley & Sons, Ltd.

Object-oriented programming languages provide many software engineering benefits, but these often come at a performance cost. Object-oriented programs make extensive use of method invocations and pointer dereferences, both of which are potentially costly on modern machines. We show how to use types to produce effective, yet simple, techniques that reduce the costs of these features in Modula-3, a statically typed, object-oriented language. Our compiler performs type-based alias analysis to disambiguate memory references. It uses the results of the type-based alias analysis to eliminate redundant memory references and to replace monomorphic method invocation sites with direct calls. Using limit, static, and running time evaluation, we demonstrate that these techniques are effective, and sometimes perfect for a set of Modula-3 benchmarks.

We describe a novel approach to obtaining type-accurate information for garbage collection in a hardware and language independent way. Our approach uses a run-time analysis to propagate pointer/non-pointer information from significant type events (such as allocation, which always returns a pointer). We use this technique to perform a detailed comparison of garbage collectors with different levels of accuracy and explicit deallocation on a range of C programs. We take advantage of the portability of our approach to conduct our experiments on three hardware platforms, Alpha/Digital UNIX 4.0D, Pentium/Linux 2.2, and SPARC/Solaris 2. We find that the choice of hardware platform (which includes the architecture, operating system, and libraries) greatly affects whether or not type accuracy enhances a garbage collector's ability to reclaim objects.

The SUIF Explorer is an interactive parallelization tool that is more effective than previous systems in minimizing the number of lines of code that require programmer assistance. First, the interprocedural analyses in the SUIF system is successful in parallelizing many coarse-grain loops, thus minimizing the number of spurious dependences requiring attention. Second, the system uses dynamic execution analyzers to identify those important loops that are likely to be parallelizable. Third, the SUIF Explorer is the first to apply program slicing to aid programmers in interactive parallelization. The system guides the programmer in the parallelization process using a set of sophisticated visualization techniques.This paper demonstrates the effectiveness of the SUIF Explorer with three case studies. The programmer was able to speed up all three programs by examining only a small fraction of the program and privatizing a few variables.

This paper evaluates three alias analyses based on programming language types. The first analysis uses type compatibility to determine aliases. The second extends the first by using additional high-level information such as field names. The third extends the second with a flow-insensitive analysis. Although other researchers suggests using types to disambiguate memory references, none evaluates its effectiveness. We perform both static and dynamic evaluations of type-based alias analyses for Modula-3, a statically-typed type-safe language. The static analysis reveals that type compatibility alone yields a very imprecise alias analysis, but the other two analyses significantly improve alias precision. We use redundant load elimination (RLE) to demonstrate the effectiveness of the three alias algorithms in terms of the opportunities for optimization, the impact on simulated execution times, and to compute an upper bound on what a perfect alias analysis would yield. We show modest dynamic improvements for (RLE), and more surprisingly, that on average our alias analysis is within 2.5% of a perfect alias analysis with respect to RLE on 8 Modula-3 programs. These results illustrate that to explore thoroughly the effectiveness of alias analyses, researchers need static, dynamic, and upper-bound analysis. In addition, we show that for type-safe languages like Modula-3 and Java, a fast and simple alias analysis may be sufficient for many applications.

To use modern hardware effectively, compilers need extensive control-flow information. Unfortunately, the frequent method invocations in object-oriented languages obscure control flow. In this paper, we describe and evaluate a range of analysis techniques to convert method invocations into direct calls for statically-typed object-oriented languages and thus improve control-flow information in object-oriented languages. We present simple algorithms for type hierarchy analysis, aggregate analysis, and interprocedural and intraprocedural type propagation. These algorithms are also fast, O(|procedures| * ∑pprocedure np * vp) worst case time (linear in practice) for our slowest analysis, where np is the size of procedure p and vp is the number of variables in procedure p, and are thus practical for use in a compiler. When they fail, we introduce cause analysis to reveal the source of imprecision and suggest where more powerful algorithms may be warranted. We show that our simple analyses perform almost as well as an oracle that resolves all method invocations that invoke only a single procedure.

Heap allocation with copying garbage collection is a general storage management technique for programming languages. It is believed to have poor memory system performance. To investigate this, we conducted an in-depth study of the memory system performance of heap allocation for memory systems found on many machines. We studied the performance of mostly functional Standard ML programs which made heavy use of heap allocation. We found that most machines support heap allocation poorly. However, with the appropriate memory system organization, heap allocation can have good performance. The memory system property crucial for achieving good performance was the ability to allocate and initialize a new object into the cache without a penalty. This can be achieved by having subblock by placement with a subblock size of one word with a write-allocate policy, along with fast page-mode writes or a write buffer. For caches with subblock placement, the data cache overhead was under 9% for a 64K or larger data cache; without subblock placement the overhead was often higher than 50%.

Heap allocation with copying garbage collection is believed to have poor memory subsystem performance. We conducted a study of the memory subsystem performance of heap allocation for memory subsystems found on many machines. We found that many machines support heap allocation poorly. However, with the appropriate memory subsystem organization, heap allocation can have good memory subsystem performance.

We consider the problem of supporting compacting garbage collection in the presence of modern compiler optimizations. Since our collector may move any heap object, it must accurately locate, follow, and update all pointers and values derived from pointers. To assist the collector, we extend the compiler to emit tables describing live pointers, and values derived from pointers, at each program location where collection may occur. Significant results include identification of a number of problems posed by optimizations, solutions to those problems, a working compiler, and experimental data concerning table sizes, table compression, and time overhead of decoding tables during collection. While gc support can affect the code produced, our sample programs show no significant changes, the table sizes are a modest fraction of the size of the optimized code, and stack tracing is a small fraction of total gc time. Since the compiler enhancements are also modest, we conclude that the approach is practical.