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.

Canary testing is an emerging technique that offers to minimize the risk of deploying a new version of software. It does so by slowly transferring load from the current to the new ("canary") version. As this ramp-up progresses, a human compares the performance and correctness of the two versions, and assesses whether to abort the canary version. For canary testing to be effective, a plethora of metrics must be analyzed, including CPU utilization and logged errors, across hundreds to thousands of machines. Performing this analysis manually is both time consuming and error prone. In this paper, we present CanaryAdvisor, a tool for automatic canary testing of cloud-based applications. CanaryAdvisor continuously monitors the deployed versions of an application and detects degradations in correctness, performance, and/or scalability. We describe our design and implementation of the CanaryAdvisor and outline open challenges.

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.

When resolving performance problems, a simple histogram of hot call stacks does not cut it, especially given the highly fluid nature of modern deployments. Why bother tuning, when adding a few CPUs via the management console will quickly resolve the problem? The findings of these tools are also presented without any sense of context: e.g. string conversion may be expensive, but only matters if it contributes greatly to the response time of user logins.

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.

Understanding the cause of poor performance in a multi-tier enterprise application is challenging, because a performance bottleneck on any tier may cause the whole system to be under utilized, and to fail its throughput or quality of service goals. This paper presents an approach that focuses on the application server to identify bottlenecks in a multi-tier application that are caused by tiers other then the application server. The approach uses a performance tool, named SLICE, that selectively tracks method invocations that cross tier boundaries, and extracts contextual information associated with these invocations. SLICE also collects information from the operating system's scheduler to determine when a thread is blocked. Using the contextual information from method invocations and the information of when a thread is blocked from the operating system, SLICE computes cross tier delay. Experiments on DayTrader, a multi-tier application, show that performance bottlenecks caused by clients or database servers can be identified using cross tier delay.

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.

Multicore systems increase the complexity of performance analysis by introducing a new source of additional costs: thread migration between cores. This paper explores the cost of thread migration for Java applications. We first present a detailed analysis of the sources of migration overhead and show that they result from a combination of several factors including application behavior (working set size), OS behavior (migration frequency) and hardware characteristics (nonuniform cache sharing among cores). We also present a performance characterization of several multi-threaded Java applications. Surprisingly, our analysis shows that, although significant migration penalizes can be produced in controlled environments, the set of Java applications that we examined do not suffer noticeably from migration overhead when run in a realistic operating environment on an actual multicore platform.

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.

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.

Today's virtual machines (VMs) dynamically optimize an application as it is executing, often employing optimizations that are specialized for the current execution profile. An online phase detector determines when an executing program is in a stable period of program execution (a phase) or is in transition. A VM using an online phase detector can apply specialized optimizations during a phase or reconsider optimization decisions between phases. Unfortunately, extant approaches to detecting phase behavior rely on either offline profiling, hardware support, or are targeted toward a particular optimization. In this work, we focus on the enabling technology of online phase detection. More specifically, we contribute (a) a novel framework for online phase detection, (b) multiple instantiations of the framework that produce novel online phase detection algorithms, (c) a novel client- and machine-independent baseline methodology for evaluating the accuracy of an online phase detector, (d) a metric to compare online detectors to this baseline, and (e) a detailed empirical evaluation, using Java applications, of the accuracy of the numerous phase detectors.

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.

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.

Virtual machines face significant performance challenges beyond those confronted by traditional static optimizers. First, portable program representations and dynamic language features, such as dynamic class loading, force the deferral of most optimizations until runtime, inducing runtime optimization overhead. Second, modular program representations preclude many forms of whole-program interprocedural optimization. Third, virtual machines incur additional costs for runtime services such as security guarantees and automatic memory management. To address these challenges, vendors have invested considerable resources into adaptive optimization systems in production virtual machines. Today, mainstream virtual machine implementations include substantial infrastructure for online monitoring and profiling, runtime compilation, and feedback-directed optimization. As a result, adaptive optimization has begun to mature as a widespread production-level technology. This paper surveys the evolution and current state of adaptive optimization technology in virtual machines.

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.

Abstract This paper develops a formalism that precisely characterizes when class tables are required for C++ memory layouts. A memory layout is a particular choice of data structures for implementing run‐time support for object‐oriented languages. We use this formalism to quantify and evaluate, on a set of benchmarks, the space overhead for a set of C++ memory layouts. In particular, this paper studies the space overhead due to three language features: virtual dispatch, virtual inheritance, and dynamic typing. To date, there has been no scientific quantification or evaluation of C++ memory layouts. Our approach can help C++ implementors. This work has already influenced the memory layout design choices in IBM's Visual Age C++ V5 compiler. Applying our approach to a set of five benchmarks, we demonstrate that the impact of object‐oriented space overhead can vary dramatically between applications (ranging from 0.42% to 99.79% for our benchmarks). In particular, applications whose object space is dominated by instances of classes that heavily use object‐oriented language features will be significantly impacted by the choice of a memory layout. Copyright © 2003 John Wiley & Sons, Ltd.

Reducing application size is important for software that is distributed via the internet, in order to keep download times manageable, and in the domain of embedded systems, where applications are often stored in (Read-Only or Flash) memory. This paper explores extraction techniques such as the removal of unreachable methods and redundant fields, inlining of method calls, and transformation of the class hierarchy for reducing application size. We implemented a number of extraction techniques in Jax , an application extractor for Java, and evaluated their effectiveness on a set of large Java applications. We found that, on average, the class file archives for these benchmarks were reduced to 37.5% of their original size. Modeling dynamic language features such as reflection, and extracting software distributions other than complete applications requires additional user input. We present a uniform approach for supplying this input that relies on MEL, a modular specification language. We also discuss a number of issues and challenges associated with the extraction of embedded systems applications.

Future high-performance virtual machines will improve performance through sophisticated online feedback-directed optimizations. this paper presents the architecture of the Jalapeño Adaptive Optimization System, a system to support leading-edge virtual machine technology and enable ongoing research on online feedback-directed optimizations. We describe the extensible system architecture, based on a federation of threads with asynchronous communication. We present an implementation of the general architecture that supports adaptive multi-level optimization based purely on statistical sampling. We empirically demonstrate that this profiling technique has low overhead and can improve startup and steady-state performance, even without the presence of online feedback-directed optimizations. The paper also describes and evaluates an online feedback-directed inlining optimization based on statistical edge sampling. The system is written completely in Java, applying the described techniques not only to application code and standard libraries, but also to the virtual machine itself.

In an increasingly popular model of software distribution, software is developed in one computing environment and deployed in other environments by transfer over the internet. Extraction tools perform a static whole-program analysis to determine unused functionality in applications in order to reduce the time required to download applications. We have identified a number of scenarios where extraction tools require information beyond what can be inferred through static analysis: software distributions other than complete applications, the use of reflection, and situations where an application uses separately developed class libraries. This paper explores these issues, and introduces a modular specification language for expressing the information required for extraction. We implemented this language in the context of Jax, an industrial-strength application extractor for Java, and present a small case study in which different extraction scenarios are applied to a commercially available library-based application.

Traditional implementations of multiple inheritance bring about not only an overhead in terms of run-time but also a significant increase in object space. For example, the number of compiler-generated fields in a certain object can be as large as quadratic in the number of its subobjects. The problem of efficient object layout is compounded by the need to support two different semantics of multiple inheritance: shared, in which a base class inherited along distinct paths occurs only once in the derived class, and repeated, in which this base has multiple distinct occurrences in the derived. In this theoretical and foundational paper, we introduce two new techniques to optimize memory layout for multiple inheritance. The main ideas behind these techniques are the inlining of virtual bases and bidirectional memory layout. Our techniques never increase time overhead, and usually even decrease it. We show that in some example hierarchies, more than ten-fold reduction in the space overhead can be achieved. We analyze the complexity of the algorithms to apply these techniques, and give theorems to estimate the efficacy of this application. For concreteness, techniques and examples are discussed in the context of C++.

Java programs are routinely transmitted over low-bandwidth network connections as compressed class file archives (i.e., zip files and jar files). Since archive size is directly proportional to download time, it is desirable for applications to be as small as possible. This paper is concerned with the use of program transformations such as removal of dead methods and fields, inlining of method calls, and simplification of the class hierarchy for reducing application size. Such “extraction” techniques are generally believed to be especially useful for applications that use class libraries, since typically only a small fraction of a library's functionality is used. By “pruning away” unused library functionality, application size can be reduced dramatically. We implemented a number of application extraction techniques in Jax, an application extractor for Java, and evaluate their effectiveness on a set of realistic benchmarks ranging from 27 to 2,332 classes (with archives ranging from 56,796 to 3,810,120 bytes). We report archive size reductions ranging from 13.4% to 90.2% (48.7% on average).

Object-oriented applications may contain data members that can be removed from the application without affecting program behavior. Such "dead" data members may occur due to unused functionality in class libraries, or due to the programmer losing track of member usage as the application changes over time. We present a simple and efficient algorithm for detecting dead data members in C++ applications. This algorithm has been implemented using a prototype version of the IBM VisualAge C++ compiler, and applied to a number of realistic benchmark programs ranging from 600 to 58,000 lines of code. For the non-trivial benchmarks, we found that up to 27.3% of the data members in the benchmarks are dead (average 12.5%), and that up to 11.6% of the object space of these applications may be occupied by dead data members at run-time (average 4.4%).

Class libraries are generally designed with an emphasis on versatility and extensibility. Applications that use a library typically exercise only part of the library's functionality. As a result, objects created by the application may contain unused members. We present an algorithm that specializes a class hierarchy with respect to its usage in a program P. That is, the algorithm analyzes the member access patterns for P's variables, and creates distinct classes for variables that access different members. Class hierarchy specialization reduces object size, and is hence primarily a space optimization. However, execution time may also be reduced through reduced object creation/destruction time, and caching/paging effects.

Virtual functions make code easier for programmers to reuse but also make it harder for compilers to analyze. We investigate the ability of three static analysis algorithms to improve C++ programs by resolving virtual function calls, thereby reducing compiled code size and reducing program complexity so as to improve both human and automated program understanding and analysis. In measurements of seven programs of significant size (5000 to 20000 lines of code each) we found that on average the most precise of the three algorithms resolved 71% of the virtual function calls and reduced compiled code size by 25%. This algorithm is very fast: it analyzes 3300 source lines per second on an 80 MHz PowerPC 601. Because of its accuracy and speed, this algorithm is an excellent candidate for inclusion in production C++ compilers.

Development of any large system or artifact requires the coordination of many developers. Development activities can occur concurrently. The goal of coordination is to enhance, not restrict, developer productivity, while ensuring that concurrent development activities do not clash with one another.

This paper presents our experience building an extendible software development environment using the object-oriented paradigm. We have found that object instances provide a natural way to model program constructs, and to capture complex relationships between different aspects of a software system. The object-oriented paradigm can be efficiently implemented on standard hardware and software, and provides some degree of extendibility without requiring major modifications to the existing implementation.

At the core of any sophisticated software development and maintenance environment is a large mass of complex data. The data (the central data of the environment) is composed of smaller sets of data that can be related in complicated and often subtle ways. The user or developer of the environment will be more effective if they are able to deal with conceptual slices, or views, of the large, complex structure. This paper presents an architectural building block for object-based software environments based on the views concept. The building block allows the construction of global abstractions that describe unified behavior of large sets of objects. The basis of the architecture relies on extending the object-oriented paradigm in three steps: (1) defining multiple interfaces in object classes; (2) controlling visibility of instance variables; and (3) allowing multiple copies of an instance variable to occur within an object instance. This paper focuses on the technical aspects of the views approach.