Hash-based maps, particularly java.util.HashMap, are pervasive in Java applications and the JVM, making their performance critical. Evaluating optimizations is challenging because performance depends on factors such as operation patterns, key distributions, and resizing behavior. Microbenchmarks are fast and repeatable but often oversimplify workloads, failing to capture the realistic usage patterns. Application benchmarks (e.g., DaCapo, Renaissance) provide realistic usages but are more expensive to run, prone to variability, and dominated by non-HashMap computations, making map-related performance changes difficult to observe. To address this challenge, we propose MapReplay, a benchmarking methodology that combines the realism of application benchmarks with the efficiency of microbenchmarks. MapReplay traces HashMap API usages generating a replay workload that reproduces the same operation sequence while faithfully reconstructing internal map states. This enables realistic and efficient evaluation of alternative implementations under realistic usage patterns. Applying MapReplay to DaCapo-Chopin and Renaissance, the resulting suite, MapReplayBench, reproduces application-level performance trends while reducing experimentation time and revealing insights difficult to obtain from full benchmarks.

With the increasing popularity of Serverless computing and Function as a Service---where typical workloads have a short lifetime---the research community is increasingly focusing on startup performance optimization. To reduce the startup time of managed language runtime systems, related work proposes strategies to move runtime environment initialization ahead-of-time. For instance, GraalVM Native Image allows one to create a binary file from a Java application that embeds a snapshot of the pre-initialized heap memory and can run without instantiating a Java Virtual Machine. However, the program startup needs to be further optimized, because the cloud runtime often starts the program while responding to the request. Thus, the program startup time impacts the service-level agreement. In this paper, we improve the startup time of Native-Image binaries by changing their layout during compilation, reducing I/O traffic. We propose a profile-guided binary-reordering approach and a profiling methodology to obtain the execution-order profiles of methods and objects. Thanks to these profiles, we first reduce page faults related to the code section. Then, we propose three ordering strategies to reduce page faults related to accessing the objects in the heap snapshot. Since the object identities and the heap-snapshot contents are not persistent across Native-Image builds of the same program, we propose a method of matching objects from the profile against the objects in the profile-guided build. Experimental results show that our ordering strategies lead to an average page-fault reduction factor of 1.61× and an average execution-time speedup of 1.59×.

The C++ language continually evolves through formal specifications established by its standards committee, proposing new features to maintain $\mathrm{C}++$ as a relevant programming language while improving usability, performance, and portability across platforms. With the addition of parallel Standard Template Library (STL) algorithms in C++17, programmers can now leverage parallel processing capabilities via vendor-neutral parallel execution policies. This study presents an adaptation of the NAS Parallel Benchmarks (NPB)—a well-established suite of applications for evaluating parallel architectures-by porting its sequential C-style code to use C++ STL abstractions and performance-portable parallelism features. Our goals are to (1) assess the suitability of C++ STL for scientific applications like the ones in the NPB and (2) provide a comparative performance and portability of STL algorithms’ parallel execution policies across different multicore architectures (x86 and AArch64). Results indicate that the performance of parallel STL algorithms is often close to that of optimized handwritten versions (OpenMP, Intel TBB, and FastFlow) on different architectures, with notable shortfalls. Across all NPB benchmarks, the STL algorithms’ geometric mean shows sequential execution times that are between 3.76% and $\mathrm{6. 9 \%}$ higher, while parallel executions may reach a geometric mean of up to $\mathrm{2 1. 2 1 \%}$ higher execution time.

GraalVM Native Image is increasingly used to optimize the startup performance of applications that run on the Java Virtual Machine (JVM), and particularly of Function-as-a-Service and Serverless workloads. Native Image resorts to Ahead-of-Time (AOT) compilation to produce a binary from a JVM application that contains a snapshot of the pre-initialized heap memory, reducing the initialization time and hence improving startup performance. However, this performance improvement is hindered by page faults that occur when accessing objects in the heap snapshot. Related work has proposed profile-guided approaches to reduce page faults by reordering objects in the heap snapshot of an optimized binary based on the order in which objects are first accessed, obtaining this information by profiling an instrumented binary of the same application. This reordering is effective only if objects in the instrumented binary can be matched to the semantically equivalent ones in the optimized binary. Unfortunately, this is very challenging because objects do not have unique identities and the heap-snapshot contents are not persistent across Native-Image builds of the same program. This work tackles the problem of matching heap snapshots, and proposes a novel approach to improve the mapping between semantically equivalent objects in different binaries of a Native-Image application. We introduce the concept of context-augmented heap path (CAHP) —a list of elements that describes a path to an object stored in the heap snapshot. Our approach associates a CAHP to each object in a way that is as unique as possible. Objects with the same CAHP across different binaries are considered semantically equivalent. Moreover, since some semantically equivalent objects may have different CAHPs in the instrumented and optimized binaries (due to nondeterminism in the image-build process and other factors), we present an approach that finds, for each unmatched CAHP in the optimized binary, the most similar CAHP in the instrumented binary, associating the two objects. We integrate our approach into Native Image, reordering the objects stored in the heap snapshot more efficiently using the improved mapping. Our experiments show that our approach leads to much less page faults (2.98× on average) and considerably improves startup time (1.98× on average) w.r.t. the original Native-Image implementation.

In modern cloud applications, data serialization and deserialization (DSD) are common yet expensive operations. Languages such as Java incur significant overhead from DSD operations because of their managed memory, which uses an IO-incompatible, sparse, platform-dependent data layout for storing objects. Can language VMs bypass costly DSD operations by directly operating on an IO-ready binary format? In this paper, we address this question by presenting a new DSD library for Java called HeapBuffers. HeapBuffers maintains a Java-friendly programming model through managed memory, yet it operates on data stored using a dense, platform-independent, memory format. In this way, HeapBuffers data can be used to perform IO operations without the need to convert objects from/to a VM-internal memory representation, thus eliminating the need for expensive DSD operations. Compiler optimizations combined with specialized garbage collection ensure that accessing HeapBuffers data is nearly as efficient as handling regular Java objects. The answer to our question is largely positive: our experiments show that HeapBuffers data can be accessed at high performance and can be used as is to perform IO, making the cost of DSD effectively negligible. IO performance of applications using HeapBuffers is often orders of magnitude faster than that obtained using the prevailing DSD libraries.

Several methods of the Java Class Library (JCL) rely on vectorized intrinsics. While these intrinsics undoubtedly lead to better performance, implementing them is extremely challenging, tedious, error-prone, and significantly increases the effort in understanding and maintaining the code. Moreover, their implementation is platform-dependent. An unexplored, easier-to-implement alternative is to replace vectorized intrinsics with portable Java code using the Java Vector API. However, this is attractive only if the Java code achieves similar steady-state performance as the intrinsics. This paper shows that this is the case. We focus on the hashCode and equals computations for byte arrays. We replace the platform-dependent vectorized intrinsics with pure-Java code employing the Java Vector API, resulting in similar steady-state performance. We show that our Java implementations are easy to fine-tune by exploiting characteristics of the input (i.e., the array length), while such tuning would be much more difficult and cumbersome in a vectorized intrinsic. Additionally, we propose a new vectorized hashCode computation for long arrays, for which a corresponding intrinsic is currently missing. We evaluate the performance of the tuned implementations on four popular benchmark suites, showing that the performance are in line with those of the original OpenJDK 21 with intrinsics. Finally, we describe a general approach to integrate code using the Java Vector API into the core classes of the JCL, which is challenging because premature use of the Java Vector API would crash the JVM during its fragile initialization phase. Our approach can be adopted by developers to modify JCL classes without any changes to the native codebase.

Virtual threads are a new feature of the Java Virtual Machine (JVM) complementing the regular Java threads (called platform threads). Virtual threads promise a significant throughput improvement in workloads that make intensive use of blocking operations, but incur performance overheads in CPU-bound workloads, due to the cost of creating and maintaining the data structures associated with them. Hence, the optimal choice between platform and virtual threads depends on application behavior (which can change significantly during the execution) and on the system running the application. This work-in-progress paper proposes a new framework to automatically and adaptively select the type of threads created by an application, switching between platform and virtual threads as the application's behavior changes over time. The framework monitors several metrics of the running application. Based on these metrics, users can specify criteria for deciding when virtual threads should be preferred over platform threads and vice versa. We present a use case on the Eclipse Jetty web server. Our preliminary evaluation shows that the framework selects the thread type yielding the highest throughput depending on the application behavior, without introducing performance drawbacks.

The Java Vector API is a new module introduced in Java 16, allowing developers to concisely express vector computations. The API promises both high performance, achieved via the runtime compilation of vector operations to hardware vector instructions, and portability. To the best of our knowledge, there is no study evaluating the performance of the new Java Vector API. To bridge this gap, we propose JVBench, to the best of our knowledge, the first open-source benchmark suite for the Java Vector API. JVBench extensively exercises the features introduced by the Java Vector API, resulting in high API coverage. We use JVBench to evaluate the performance and portability of the Java Vector API on multiple architectures supporting different vector instruction sets. We compare the performance of the Java Vector API on our benchmarks w.r.t. other semantically equivalent implementations, including scalar (non-auto-vectorized) Java code as well as Java code auto-vectorized by the Just in Time (JIT) compiler. Finally, we report patterns and anti-patterns on the use of the Java Vector API significantly affecting application performance.

Abstract syntax tree (AST) interpreters allow implementing programming languages in a straight-forward way. However, AST interpreters implemented in object-oriented languages, such as e.g. in Java, often suffer from two serious performance issues. First, these interpreters commonly implement AST nodes by leveraging class inheritance and polymorphism, leading to many polymorphic call sites in the interpreter implementation and hence lowering interpreter performance. Second, widely used implementations of these interpreters throw costly runtime exceptions to model the control flow. Even though Just-in-Time (JIT) compilation mitigates these issues, performance in the first stages of the program execution remains poor.

Abstract Java streams are receiving the attention of developers targeting the Java virtual machine (JVM) as they ease the development of data‐processing logic, while also favoring code extensibility and maintainability through a concise and declarative style based on functional programming. Recent studies aim to shedding light on how Java developers use streams. However, they consider only small sets of applications and mainly apply manual code inspection and static analysis techniques. As a result, the large‐scale dynamic analysis of stream processing remains an open research question. In this article, we present the first large‐scale empirical study on the use of streams in Java code exercised via unit tests. We present stream‐analyzer, a novel dynamic program analysis (DPA) that collects runtime information and key metrics, which enable a fine‐grained characterization of sequential and parallel stream processing. We use a fully automatic approach to massively apply our DPA for the analysis of open‐source software projects hosted on GitHub. Our findings advance the understanding of the use of Java streams. Both the scale of our analysis and the profiling of dynamic information enable us to confirm with more confidence the outcome highlighted at a smaller scale by related work. Moreover, our study reports the popularity of many features of the Stream API and highlights multiple findings about runtime characteristics unique to streams, while also revealing inefficient stream processing and stream misuses. Finally, we present implications of our findings for developers of the Stream API, tool builders and researchers, and educators.

Tracking specific events in a program’s execution, such as object allocation or lock acquisition, is at the heart of dynamic analysis. Despite the apparent simplicity of this task, quantifying these events is challenging due to the presence of compiler optimizations. Profiling perturbs the optimizations that the compiler would normally do—a profiled program usually behaves differently than the original one. In this article, we propose a novel technique for quantifying compiler-internal events in the optimized code, reducing the profiling perturbation on compiler optimizations. Our technique achieves this by instrumenting the program from within the compiler, and by delaying the instrumentation until the point in the compilation pipeline after which no subsequent optimizations can remove the events. We propose two different implementation strategies of our technique based on path-profiling, and a modification to the standard path-profiling algorithm that facilitates the use of the proposed strategies in a modernjust-in-time (JIT)compiler. We use our technique to analyze the behaviour of the optimizations in Graal, a state-of-the-art compiler for the Java Virtual Machine, identifying the reasons behind a performance improvement of a specific optimization, and the causes behind an unexpected slowdown of another. Finally, our evaluation results show that the two proposed implementations result in a significantly lower execution-time overhead w.r.t. a naive implementation.

Abstract Language-integrated query (LINQ) frameworks offer a convenient programming abstraction for processing in-memory collections of data, allowing developers to concisely express declarative queries using popular programming languages. Existing LINQ frameworks rely on the type system of statically typed languages such as C $$^\sharp $$ ♯ or Java to perform query compilation and execution. As a consequence of this design, they do not support dynamic languages such as Python, R, or JavaScript. Such languages are however very popular among data scientists, who would certainly benefit from LINQ frameworks in data-analytics applications. The gap between dynamic languages and LINQ frameworks has been partially bridged by the recent work DynQ, a novel query engine designed for dynamic languages. DynQ is language-agnostic, since it is able to execute SQL queries on all languages supported by the GraalVM platform. Moreover, DynQ can execute queries combining data from multiple sources, namely in-memory object collections as well as on-file data and external database systems. The evaluation of DynQ shows performance comparable with equivalent hand-optimized code, and in line with common data-processing libraries and embedded databases, making DynQ an appealing query engine for standalone analytics applications and for data-intensive server-side workloads. In this work, we extend DynQ addressing the problem of optimizing high-throughput workloads in the context of fluent APIs. In particular, we focus on applications which make use of data-processing libraries mostly for executing many queries on small batches of datasets, e.g., in micro-services, as well as applications which make use of data-processing libraries within recursive functions. For this purpose, we presentreusable compiled queries, a novel approach to query execution which allows reusing the same dynamically compiled code for different queries. As we show in our evaluation, thanks to reusable compiled queries, DynQ can also speed up applications that heavily use data-processing libraries on small datasets using a typical fluent API.

The Java Stream API was introduced in Java 8, allowing developers to express computations in a functional style by defining a pipeline of data-processing operations. Despite the growing importance of this API, there is a lack of benchmarks specifically targeting stream-based applications. Instead of designing and implementing new ad-hoc workloads for the Java Stream API, we propose to automatically translate existing data-processing workloads. To this end, we present S2S, an automatic benchmark generator for the Java Stream API. S2S is a SQL query compiler that converts existing workloads designed for relational databases to stream-based code. We use S2S to generate BSS, the first benchmark suite for the Java Stream API.

The Java Stream API increases developer produc-tivity and greatly simplifies exploiting parallel computation by providing a high-level abstraction on top of complex data pro-cessing, parallelization, and synchronization algorithms. However, the usage of the Java Stream API often incurs significant runtime overhead. Method inlining and the automated translation of code using the Java Stream API into imperative code using loops can reduce such overhead; however, existing approaches and tools are applicable only to sequential stream pipelines, leaving the optimization of parallel streams an open issue. We bridge this gap by presenting a novel method to exploit high-level static analysis to characterize stream pipelines, detect parallel streams, and apply transformations removing the abstraction overhead. We evaluate our method on a set of benchmarks, showing that our approach significantly reduces execution time and memory allocation.

Since Java 8, streams ease the development of data transformations using a declarative style based on functional programming. Some recent studies aim at shedding light on how streams are used. However, they consider only small sets of applications and mainly apply static analysis techniques, leaving the large-scale analysis of dynamic metrics focusing on stream processing an open research question. In this paper, we present the first large-scale empirical study on the use of streams in Java. We present a novel dynamic analysis for collecting runtime information and key metrics that enable the fine-grained characterization of sequential and parallel stream processing. We massively apply our dynamic analysis using a fully automated approach, supported by a distributed infrastructure to mine public software projects hosted on GitHub. Our findings advance the understanding of the use of streams, both confirming some of the results of previous studies at a much larger scale, as well as revealing previously unobserved findings in the use of streams.

Typical Node.js applications extensively rely on packages hosted in the npm registry. As such packages may be used by thousands of other packages or applications, it is important to assess their code coverage. Moreover, increasing code coverage may help detect previously unknown issues. In this paper, we introduce TESA, a new tool that automatically assembles a test suite for any package in the npm registry. The test suite includes 1) tests written for the target package and usually hosted in its development repository, and 2) tests selected from dependent packages. The former tests allow assessing the code coverage of the target package, while the latter ones can increase code coverage by exploiting third-party tests that also exercise code in the target package. We use TESA to assess the code coverage of 500 popular npm packages. Then, we demonstrate that TESA can significantly increase code coverage by including tests from dependent packages. Finally, we show that the test suites assembled by TESA increase the effectiveness of existing dynamic program analyses to identify performance issues that are not detectable when only executing the developer's tests.

Language-integrated query (LINQ) frameworks offer a convenient programming abstraction for processing in-memory collections of data, allowing developers to concisely express declarative queries using general-purpose programming languages. Existing LINQ frameworks rely on the well-defined type system of statically-typed languages such as C#or Java to perform query compilation and execution. As a consequence of this design, they do not support dynamic languages such as Python, R, or JavaScript. Such languages are however very popular among data scientists, who would certainly benefit from LINQ frameworks in data analytics applications. In this work we bridge the gap between dynamic languages and LINQ frameworks. We introduce DynQ, a novel query engine designed for dynamic languages. DynQ is language-agnostic, since it is able to execute SQL queries in a polyglot language runtime. Moreover, DynQ can execute queries combining data from multiple sources, namely in-memory object collections as well as on-file data and external database systems. Our evaluation of DynQ shows performance comparable with equivalent hand-optimized code, and in line with common data-processing libraries and embedded databases, making DynQ an appealing query engine for standalone analytics applications and for data-intensive server-side workloads.

Software performance testing is an essential quality assurance mechanism that can identify optimization opportunities. Automating this process requires strong tool support, especially in the case of Continuous Integration (CI) where tests need to run completely automatically and it is desirable to provide developers with actionable feedback. A lack of existing tools means that performance testing is normally left out of the scope of CI. In this paper, we propose a toolchain - PerfCI - to pave the way for developers to easily set up and carry out automated performance testing under CI. Our toolchain is based on allowing users to (1) specify performance testing tasks, (2) analyze unit tests on a variety of python projects ranging from scripts to full-blown flask-based web services, by extending a performance analysis framework (VyPR) and (3) evaluate performance data to get feedback on the code. We demonstrate the feasibility of our toolchain by using it on a web service running at the Compact Muon Solenoid (CMS) experiment at the world's largest particle physics laboratory --- CERN.

Big-data systems have gained significant momentum, and Apache Spark is becoming a de-facto standard for modern data analytics. Spark relies on SQL query compilation to optimize the execution performance of analytical workloads on a variety of data sources. Despite its scalable architecture, Spark's SQL code generation suffers from significant runtime overheads related to data access and de-serialization. Such performance penalty can be significant, especially when applications operate on human-readable data formats such as CSV or JSON. In this paper we present a new approach to query compilation that overcomes these limitations by relying on run-time profiling and dynamic code generation. Our new SQL compiler for Spark produces highly-efficient machine code, leading to speedups of up to 4.4x on the TPC-H benchmark with textual-form data formats such as CSV or JSON.

With the popularity of Node.js, asynchronous, event-driven programming has become widespread in server-side applications. While conceptually simple, event-based programming can be tedious and error-prone. The complex semantics of the Node.js event loop, coupled with the different flavors of asynchronous execution in JavaScript, easily leads to bugs. This paper introduces a new model called Async Graph to reason about the runtime behavior of applications and their interactions with the Node.js event loop. Based on the model, we have developed AsyncG, a tool to automatically build and analyze the Async Graph of a running application, and to identify bugs related to all sources of asynchronous execution in Node.js. AsyncG is compatible with the latest ECMAScript language features and can be (de)activated at runtime. In our evaluation, we show how AsyncG can be used to identify bugs in real-world Node.js applications.

Today’s availability of open-source software is overwhelming, and the number of free, ready-to-use software components in package repositories such as NPM, Maven, or SBT is growing exponentially. In this paper we address two straightforward yet important research questions: would it be possible to develop a tool to automate dynamic program analysis on public open-source software at a large scale? Moreover, and perhaps more importantly, would such a tool be useful? We answer the first question by introducing NAB, a tool to execute large-scale dynamic program analysis of open-source software in the wild. NAB is fully-automatic, language-agnostic, and can scale dynamic program analyses on open-source software up to thousands of projects hosted in code repositories. Using NAB, we analyzed more than 56K Node.js, Java, and Scala projects. Using the data collected by NAB we were able to (1) study the adoption of new language constructs such as JavaScript Promises, (2) collect statistics about bad coding practices in JavaScript, and (3) identify Java and Scala task-parallel workloads suitable for inclusion in a domain-specific benchmark suite. We consider such findings and the collected data an affirmative answer to the second question.

Established benchmark suites for the Java Virtual Machine (JVM), such as DaCapo, ScalaBench, and SPECjvm2008, lack workloads that take advantage of the parallel programming abstractions and concurrency primitives offered by the JVM and the Java Class Library. However, such workloads are fundamental for understanding the way in which modern applications and data-processing frameworks use the JVM's concurrency features, and for validating new just-in-time (JIT) compiler optimizations that enable more efficient execution of such workloads. We present Renaissance, a new benchmark suite composed of modern, real-world, concurrent, and object-oriented workloads that exercise various concurrency primitives of the JVM. We show that the use of concurrency primitives in these workloads reveals optimization opportunities that were not visible with the existing workloads. We use Renaissance to compare performance of two state-of-the-art, production-quality JIT compilers (HotSpot C2 and Graal), and show that the performance differences are more significant than on existing suites such as DaCapo and SPECjvm2008. We also use Renaissance to expose four new compiler optimizations, and we analyze the behavior of several existing ones. We use Renaissance to compare performance of two state-of-the-art, production-quality JIT compilers (HotSpot C2 and Graal), and show that the performance differences are more significant than on existing suites such as DaCapo and SPECjvm2008. We also use Renaissance to expose four new compiler optimizations, and we analyze the behavior of several existing ones.

Task granularity, i.e., the amount of work performed by parallel tasks, is a key performance attribute of parallel applications. On the one hand, fine-grained tasks (i.e., small tasks carrying out few computations) may introduce considerable parallelization overheads. On the other hand, coarse-grained tasks (i.e., large tasks performing substantial computations) may not fully utilize the available CPU cores, leading to missed parallelization opportunities. In this article, we provide a better understanding of task granularity for task-parallel applications running on a single Java Virtual Machine in a shared-memory multicore. We present a new methodology to accurately and efficiently collect the granularity of each executed task, implemented in a novel profiler (available open-source) that collects carefully selected metrics from the whole system stack with low overhead, and helps developers locate performance and scalability problems. We analyze task granularity in the DaCapo, ScalaBench, and Spark Perf benchmark suites, revealing inefficiencies related to fine-grained and coarse-grained tasks in several applications. We demonstrate that the collected task-granularity profiles are actionable by optimizing task granularity in several applications, achieving speedups up to a factor of 5.90×. Our results highlight the importance of analyzing and optimizing task granularity on the Java Virtual Machine.

Runtime verification (RV) is a field of study which suffers from a lack of dedicated benchmarks. Many published evaluations of RV tools rely on workloads which are not representative of real-world programs. In this paper, we present a methodology to automatically discover relevant open-source projects for evaluating RV tools. This is done by analyzing unit tests on a large number of projects hosted on GitHub. Our evaluation shows that analyzing a large number of open-source projects-instead of a handful of manually selected workloads-provides better insight into the behavior of three state-of-the-art RV tools (JavaMOP, MarQ, and Muffin) based on two metrics (memory utilization and runtime overhead). By monitoring test executions of a large number of projects, we show that none of the evaluated RV tools wins for both metrics.

Spark is increasingly becoming the platform of choice for several big-data analyses mainly due to its fast, fault-tolerant, and in-memory processing model. Despite the popularity and maturity of the Spark framework, tuning Spark applications to achieve high performance remains challenging. In this paper, we present lpt, a novel tool that assists users in improving the level of parallelism of applications running on top of Spark in the local mode. lpt helps users tune the level of parallelism of Spark applications to spawn a number of tasks able to fully exploit the available computing resources. Our evaluation results show that optimizations guided by lpt can achieve speedups up to 2.72x.

Due to its popularity, there is an urgent need for dynamic program-analysis tools for Node.js, helping developers find bugs, performance bottlenecks, and bad coding practices. Frameworks based on code-level instrumentation enable dynamic analyses close to program semantics and are more flexible than Node.js built-in profiling tools. However, existing code-level instrumentation frameworks for JavaScript suffer from enormous overheads and difficulties in instrumenting the built-in module library of Node.js. In this paper, we introduce a new dynamic analysis framework for JavaScript and Node.js called NodeProf. While offering similar flexibility as code-level instrumentation frameworks, NodeProf significantly improves analysis performance while ensuring comprehensive code coverage. NodeProf supports runtime (de)activation of analyses and incurs zero overhead when no analysis is active. NodeProf is based on dynamic instrumentation of the JavaScript runtime and leverages automatic partial evaluation to generate efficient machine code. In addition, NodeProf makes use of the language interoperability provided by the runtime and thus allows dynamic analyses to be written in Java and JavaScript with compatibility to Jalangi, a state-of-the-art code-level JavaScript instrumentation framework. Our experiments show that the peak performance of running the same dynamic analyses using NodeProf can be up to three orders of magnitude faster than Jalangi.

Task granularity, i.e., the amount of work performed by parallel tasks, is a key performance attribute of parallel applications. On the one hand, fine-grained tasks (i.e., small tasks carrying out few computations) may introduce considerable parallelization overheads. On the other hand, coarse-grained tasks (i.e., large tasks performing substantial computations) may not fully utilize the available CPU cores, resulting in missed parallelization opportunities. In this paper, we provide a better understanding of task granularity for applications running on a Java Virtual Machine. We present a novel profiler which measures the granularity of every executed task. Our profiler collects carefully selected metrics from the whole system stack with only little overhead, and helps the developer locate performance problems. We analyze task granularity in the DaCapo and ScalaBench benchmark suites, revealing several inefficiencies related to fine-grained and coarse-grained tasks. We demonstrate that the collected task-granularity profiles are actionable by optimizing task granularity in two benchmarks, achieving speedups up to 1.53x.

A common pitfall when hosting applications in today's cloud environments is that virtual servers often experience varying execution speeds due to the interference from co-located virtual servers degrading the tail sojourn times specified in service level agreements. Motivated by the significance of tail sojourn times for cloud clusters, we develop a model of N parallel virtual server queues, each of which processes jobs in a processor sharing fashion under varying execution speeds governed by Markov-modulated processes. We derive the tail distribution of the workloads for each server and the approximation for the tail sojourn times based on large deviation analysis. Furthermore, we optimize the cluster sizes that fulfill the requirements of target tail sojourn times. Extensive simulation experiments show very good matches to the derived analysis in a variety of scenarios, i.e., large numbers of servers experiencing a high number of different execution speeds, under various traffic intensities, workload variations and cluster sizes. Finally, we apply our proposed analysis to estimating the tail sojourn times of a Wikipedia system hosted in a private cloud, and the testbed results strongly confirm the applicability and accuracy of our analysis.

The analysis of task granularity in parallel applications (i.e., the amount of work to be performed by parallel tasks) is essential to unveil performance problems and to optimize task-parallel applications. Too small task granularities may result in high parallelization overheads, while too large task granularities may indicate missed parallelization opportunities. Despite the importance of task granularity, this metric is not considered by existing profilers for parallel applications on the Java Virtual Machine (JVM). In this paper we present tgp, a novel task-granularity profiler for multi-threaded applications on the JVM. tgp collects bytecode- and hardware-level metrics to characterize task granularity, assisting the developer in diagnosing and locating parallelization shortcomings.

With the popularity of Android, a huge number of Android apps appear in different markets. As some apps pose significant security risks, it is important to support runtime monitoring and verification on Android. Existing runtime verification frameworks only focus on verifying the events within a single process, ignoring that Android is a multi-process system where different components communicate frequently, and thus lack the ability to analyze and monitor behaviors across app processes. In this paper, we introduce our new runtime verification framework for Android, capable of performing runtime verification across multiple Android components in different processes. Our approach features an extended regular expression formalism, allowing one to specify complete analyses covering the whole Android system. We illustrate the use of our framework with an Android service characterization study and a monitor for permission (mis) use in apps.

Managed language platforms such as the Java Virtual Machine or the Common Language Runtime rely on a dynamic compiler to achieve high performance. Besides making optimization decisions based on the actual program execution and the underlying hardware platform, a dynamic compiler is also in an ideal position to perform speculative optimizations. However, these tend to increase the compilation costs, because unsuccessful speculations trigger deoptimization and recompilation of the affected parts of the program, wasting previous work. Even though speculative optimizations are widely used, the costs of these optimizations in terms of extra compilation work has not been previously studied. In this paper, we analyze the behavior of the Graal dynamic compiler integrated in Oracle's HotSpot Virtual Machine. We focus on situations which cause program execution to switch from machine code to the interpreter, and compare application performance using three different deoptimization strategies which influence the amount of extra compilation work done by Graal. Using an adaptive deoptimization strategy, we managed to improve the average start-up performance of benchmarks from the DaCapo, ScalaBench, and Octane benchmark suites, mostly by avoiding wasted compilation work. On a single-core system, we observed an average speed-up of 6.4% for the DaCapo and ScalaBench workloads, and a speed-up of 5.1% for the Octane workloads; the improvement decreases with an increasing number of available CPU cores. We also find that the choice of a deoptimization strategy has negligible impact on steady-state performance. This indicates that the cost of speculation matters mainly during start-up, where it can disturb the delicate balance between executing the program and the compiler, but is quickly amortized in steady state.

Reflective supertype information (RSI) is useful for many instrumentation-based dynamic analyses on the Java Virtual Machine (JVM). On the one hand, while such information can be obtained when performing the instrumentation within the same JVM process executing the instrumented program, in-process instrumentation severely limits the code coverage of the analysis. On the other hand, performing the instrumentation in a separate process can achieve full code coverage, but complete RSI is generally not available, often requiring expensive runtime checks in the instrumented program. Providing accurate and complete RSI in the instrumentation process is challenging because of dynamic class loading and classloader namespaces. In this paper, we present a novel technique to accurately reify complete RSI in a separate instrumentation process. We implement our technique in the dynamic analysis framework DiSL and evaluate it on a task profiler, achieving speedups of up to 45% for an analysis with full code coverage.

Dynamic analysis is crucial for understanding and improving the performance of complex systems. Our work focuses on dynamic analyses on the Java Virtual Machine (JVM). Such analyses often rely on bytecode instrumentation to weave monitoring code into selected methods, so as to collect the desired metrics at runtime. Unfortunately, existing instrumentation frameworks offer limited capabilities. On the one hand, frameworks such as AspectJ that perform the weaving within the observed JVM cannot weave monitoring code within the Java class library, considerably limiting completeness of AspectJ-based analyses. On the other hand, frameworks such as DiSL that perform the weaving in a separate process offer full bytecode coverage, but cannot access certain reflective information that is available in AspectJ. Here, we present an extension of DiSL to expose reflective supertype information within the instrumentation process. This is challenging, because the observed application may make use of custom classloaders and the loaded classes are generally only known upon termination of the application. Our framework guarantees full bytecode coverage, while providing reflective supertype information. We show that our framework can significantly speed up dynamic analyses wrt. the current DiSL release.

Android has become one of the most popular operating systems for mobile devices. As the number of applications for the Android ecosystem grows, so is their complexity, increasing the need for runtime verification on the Android platform. Unfortunately, despite the presence of several runtime verification frameworks for Java bytecode, DEX bytecode used in Android does not benefit from such a wide support. While a few runtime verification tools support applications developed for Android, such tools offer only limited bytecode coverage and may not be able to detect property violations in certain classes. In this paper, we show that ADRENALIN-RV, our new runtime verification tool for Android, overcomes this limitation. In contrast to other frameworks, ADRENALIN-RV weaves monitoring code at load time and is able to instrument all loaded classes. In addition to the default classes inside the application package (APK), ADRENALIN-RV covers both the Android class library and libraries dynamically loaded from the storage, network, or generated dynamically, which related tools cannot verify. Evaluation results demonstrate the increased code coverage of ADRENALIN-RV with respect to other runtime validation tools for Android. Thanks to ADRENALIN-RV, we were able to detect violations that cannot be detected by other tools.

Motivated by the high complexity of today's datacenters, a large body of studies tries to understand workloads and resource utilization in datacenters. However, there is little work on exploring unsuccessful job and task executions. In this article, we study and predict three types of unsuccessful executions in traces of a Google datacenter, namely fail, kill, and eviction. We first quantitatively show their strongly negative impact on machine time and the resulting task slowdown. We analyze patterns of unsuccessful jobs and tasks, particularly focusing on their interdependencies, and we uncover their root causes by inspecting key workload and system attributes. Furthermore, we develop three on-line prediction models that can classify jobs and events into four classes upon arrival time, using independent or nested Neural Networks. We explore different combinations of feature sets and techniques to reduce the computational overhead. Our evaluation results show that the proposed models can accurately classify 94.4 percent of jobs and 76.8 percent of events into four classes.

Nowadays, many virtual execution environments benefit from concurrency offered by the actor model. Unfortunately, while actors are used in many applications, existing profiling tools are not much effective in analyzing the performance of applications using actors. In this paper, we present a new instrumentation-based technique to profile actors in virtual execution environments. Our technique adopts platform-independent profiling metrics that minimize the perturbations induced by the instrumentation logic and allow comparing profiling results across different platforms. In particular, our technique measures the initialization cost, the amount of executed computations, and the messages sent and received by each actor. We implement our technique within a profiling tool for Akka actors on the Java platform. Evaluation results show that our profiling technique helps performance analysis of actor utilization and communication between actors in large-scale computing frameworks.

Message exchange is a central activity in distributed computing frameworks. Nevertheless, past research has paid little attention on profiling techniques and tools for endpoint communication. In this paper, we fill this gap by introducing a new fine-grained profiler for endpoints and communication between them in distributed systems. Our tool aids efficient analysis, optimization, and tuning of endpoint communication in distributed frameworks. The paper presents an overview of our profiler, discusses employed profiling techniques and collected metrics, and shows preliminary results in profiling a well-known distributed computing framework.

Service providers seek scalable and cost-effective cloud solutions for hosting their applications. Despite significant advances facilitating cloud services deployment and management, a number of challenges still remain. Service providers are confronted with time-varying workloads, inter-dependencies between components, performance variability of the procured virtual resources, and cost structures that differ from conventional data centers. Moreover, fulfilling service level agreements (SLAs), such as the throughput and response time percentiles, becomes of paramount importance for ensuring business advantages. In this dissertation paper, we explore service provisioning in clouds from multiple points of view. The aim is to best provide service replicas in the form of VMs to various applications, such that their tail throughputs and tail response times, as well as resource utilization, meet the SLAs in the most cost effective manner. In particular, we develop models, algorithms and replication strategies that consider multi-tier services provisioned in the cloud, investigate how a service provider can opportunistically take advantage of observed cloud performance variability and provide means of guaranteeing tail throughput and response times in the face of the aforementioned performance variability. Overall, this dissertation paper provides not only a multi-faceted approach to exploring several crucial aspects of cloud-hosted services, i.e., cost, tail throughput, and tail response times, but our proposed management strategies are also rigorously validated via trace-driven simulations and extensive experiments.

JavaScript is the most popular programming language for client-side Web applications, and Node.js has popularized the language for server-side computing, too. In this domain, the minimal support for parallel programming remains however a major limitation. In this paper we introduce a novel parallel programming abstraction called Generic Messages (GEMs). GEMs allow one to combine message passing and shared-memory parallelism, extending the classes of parallel applications that can be built with Node.js. GEMs have customizable semantics and enable several forms of thread safety, isolation, and concurrency control. GEMs are designed as convenient JavaScript abstractions that expose high-level and safe parallelism models to the developer. Experiments show that GEMs outperform equivalent Node.js applications thanks to their usage of shared memory.

Systems based on event-loops have been popularized by Node.JS, and are becoming a key technology in the domain of cloud computing. Despite their popularity, such systems support only share-nothing parallelism via message passing between parallel entities usually called workers. In this paper, we introduce a novel parallel programming abstraction called Generic Messages (GEMs), which enables shared-memory parallelism for share-nothing event-based systems. A key characteristic of GEMs is that they enable workers to share state by specifying how the state can be accessed once it is shared. We call this aspect of the GEMs model capability-based parallelism.

Researchers often rely on benchmarks to demonstrate feasibility or efficiency of their contributions. However, finding the right benchmark suite can be a daunting task - existing benchmark suites may be outdated, known to be flawed, or simply irrelevant for the proposed approach. Creating a proper benchmark suite is challenging, extremely time consuming, and also - unless it becomes widely popular - a thankless endeavor. In this paper, we introduce a novel approach to help researchers find relevant workloads for their experimental evaluation needs. Our approach relies on the huge number of open-source projects available in public repositories, and on unit testing having become best practice in software development. Using a repository crawler employing pluggable static and dynamic analyses for filtering and workload characterization, we allow users to automatically find projects with relevant workloads. Preliminary results presented here show that unit tests can provide a viable source of workloads, and that the combination of static and dynamic analyses improves the ability to identify relevant workloads that can serve as the basis for custom benchmark suites.

Summary Bytecode instrumentation is a widely used technique to implement aspect weaving and dynamic analyses in virtual machines such as the Java virtual machine. Aspect weavers and other instrumentations are usually developed independently and combining them often requires significant engineering effort, if at all possible. In this article, we present polymorphic bytecode instrumentation(PBI), a simple but effective technique that allows dynamic dispatch amongst several, possibly independent instrumentations. PBI enables complete bytecode coverage, that is, any method with a bytecode representation can be instrumented. We illustrate further benefits of PBI with three case studies. First, we describe how PBI can be used to implement a comprehensive profiler of inter‐procedural and intra‐procedural control flow. Second, we provide an implementation of execution levels for AspectJ, which avoids infinite regression and unwanted interference between aspects. Third, we present a framework for adaptive dynamic analysis, where the analysis to be performed can be changed at runtime by the user. We assess the overhead introduced by PBI and provide thorough performance evaluations of PBI in all three case studies. We show that pure Java profilers like JP2 can, thanks to PBI, produce accurate execution profiles by covering all code, including the core Java libraries. We then demonstrate that PBI‐based execution levels are much faster than control flow pointcuts to avoid interference between aspects and that their efficient integration in a practical aspect language is possible. Finally, we report that PBI enables adaptive dynamic analysis tools that are more reactive to user inputs than existing tools that rely on dynamic aspect‐oriented programming with runtime weaving. These experiments position PBI as a widely applicable and practical approach for combining bytecode instrumentations. © 2015 The Authors. Software: Practice and Experience Published by John Wiley & Sons Ltd.

Originally developed with a single language in mind, the JVM is now targeted by numerous programming languages—its automatic memory management, just-in-time compilation, and adaptive optimizations—making it an attractive execution platform. However, the garbage collector, the just-in-time compiler, and other optimizations and heuristics were designed primarily with the performance of Java programs in mind. Consequently, many of the languages targeting the JVM, and especially the dynamically typed languages, are suffering from performance problems that cannot be simply solved at the JVM side. In this article, we aim to contribute to the understanding of the character of the workloads imposed on the JVM by both dynamically typed and statically typed JVM languages. To this end, we introduce a new set of dynamic metrics for workload characterization, along with an easy-to-use toolchain to collect the metrics. We apply the toolchain to applications written in six JVM languages (Java, Scala, Clojure, Jython, JRuby, and JavaScript) and discuss the findings. Given the recently identified importance of inlining for the performance of Scala programs, we also analyze the inlining behavior of the HotSpot JVM when executing bytecode originating from different JVM languages. As a result, we identify several traits in the non-Java workloads that represent potential opportunities for optimization. © 2015 The Authors. Software: Practice and Experience Published by John Wiley & Sons Ltd.

While workload collocation is a necessity to increase energy efficiency of contemporary multi-core hardware, it also increases the risk of performance anomalies due to workload interference. Pinning certain workloads to a subset of CPUs is a simple approach to increasing workload isolation, but its effect depends on workload type and system architecture. Apart from common sense guidelines, the effect of pinning has not been extensively studied so far. In this paper we study the impact of CPU pinning on performance interference and energy efficiency for pairs of collocated workloads. Besides various combinations of workloads, virtualization and resource isolation, we explore the effects of pinning depending on the level of background load. The presented results are based on more than 1000 experiments carried out on an Intel-based NUMA system, with all power management features enabled to reflect real-world settings. We find that less common CPU pinning configurations improve energy efficiency at partial background loads, indicating that systems hosting collocated workloads could benefit from dynamic CPU pinning based on CPU load and workload type.

In large-scale data enters, software and hardware failures are frequent, resulting in failures of job executions that may cause significant resource waste and performance deterioration. To proactively minimize the resource inefficiency due to job failures, it is important to identify them in advance using key job attributes. However, so far, prevailing research on datacenter workload characterization has overlooked job failures, including their patterns, root causes, and impact. In this paper, we aim to develop prediction models and mitigation policies for unsuccessful jobs, so as to reduce the resource waste in big data enters. In particular, we base our analysis on Google cluster traces, consisting of a large number of big-data jobs with a high task fan-out. We first identify the time-varying patterns of failed jobs and the contributing system features. Based on our characterization study, we develop an on-line predictive model for job failures by applying various statistical learning techniques, namely Linear Discriminate Analysis (LDA), Quadratic Discriminate Analysis (QDA), and Logistic Regression (LR). Furthermore, we propose a delay-based mitigation policy which, after a certain grace period, proactively terminates the execution of jobs that are predicted to fail. The particular objective of postponing job terminations is to strike a good tradeoffs between resource waste and false prediction of successful jobs. Our evaluation results show that the proposed method is able to significantly reduce the resource waste by 41.9% on average, and keep false terminations of jobs low, i.e., only 1%.

Big-data applications are being increasingly used in today's large-scale data enters for a large variety of purposes, such as solving scientific problems, running enterprise services, and computing data-intensive tasks. Due to the growing scale of these systems and the complexity of running applications, jobs running in big-data systems experience unsuccessful terminations of different nature. While a large body of existing studies sheds light on failures occurred in large-scale data enters, the current literature overlooks the characteristics and the performance impairment of a broader class of unsuccessful executions which can arise due to application failures, dependency violations, machine constraints, job kills, and task pre-emption. Nonetheless, deepening our understanding in this field is of paramount importance, as unsuccessful executions can lower user satisfaction, impair reliability, and lead to a high resource waste. In this paper, we describe the problem of unsuccessful executions in big-data systems, and highlight the critical importance of improving our knowledge on this subject. We review the existing literature on this field, discuss its limitations, and present our own contributions to the problem, along with our research plan for the future.

Motivated by the high system complexity of today's datacenters, a large body of related studies tries to understand workloads and resource utilization in datacenters. However, there is little work on exploring unsuccessful job and task executions. In this paper, we study three types of unsuccessful executions in traces of a Google datacenter, namely fail, kill, and eviction. The objective of our analysis is to identify their resource waste, impacts on application performance, and root causes. We first quantitatively show their strong negative impact on CPU, RAM, and DISK usage and on task slowdown. We analyze patterns of unsuccessful jobs and tasks, particularly focusing on their interdependency. Moreover, we uncover their root causes by inspecting key workload and system attributes such as machine locality and concurrency level. Our results help in the design of low-latency and fault-tolerant big-data systems.

As modern service systems are pressured to provide competitive prices via cost-effective capacity planning, especially in the paradigm of cloud computing, service level agreements (SLAs) end up becoming ever more sophisticated, i.e., fulfilling targets of different percentiles of response times. However, it is no mean feat to predict even the average response times of real systems, or even abstracted queueing systems that typically simplify system details, and it gets even more complicated when trying to manage SLAs defined by various percentiles of response times. To efficiently capture these different percentiles, we first develop a novel and autonomic methodology — termed Burst Based Simulation, which combines burst profiling on real systems with complex, state-dependent simulations. Moreover, based on our methodology, we construct an analysis on SLA management: the prediction of SLA violations given a certain request pattern. We evaluate our approach on two types of service systems, virtualized and bare-metal, with wide ranges of SLAs and traffic loads. Our evaluation results show that our methodology is able to achieve an average error below 15% when predicting different response time percentiles, and accurately capture SLA violations.

To operate systems cost-effectively, cloud providers not only multiplex applications on the shared infrastructure but also dynamically allocate available resources, such as power and cores. Data intensive applications based on the MapReduce paradigm rapidly grow in popularity and importance in the Cloud. Such big data applications typically have high fan-out of components and workload dynamics. It is no mean feat to deploy and further optimize application performance within (stringent) resource budgets. In this paper, we develop a novel solution, OptiCA, that eases the deployment of big data applications on cloud and the control of application components so that desired performance metrics can be best achieved for any given resource budgets, in terms of core capacities. The control algorithm of OptiCA distributes the available core budget across co-executed applications and components, based on their “effective” demands obtained through non-intrusive profiling. Our proposed solution is able to achieve robust performance, i.e., with very minor degradation, in cases where resource budget decreases rapidly.

Big-data applications are becoming the core of today's business operations, featuring complex data structures and high task fan-out. According to the publicly available Google trace, more than 40% of big-data jobs do not reach successful completion. Interestingly, a significant portion of tasks of such failed jobs undergo multiple types of repetitive failed executions and consume a non-negligible amount of resources. To conserve resources for big-data clusters, it is imperative to capture such failed tasks of failed jobs, a very challenging problem due to multiple types of failures associated with tasks and highly uneven tasks distribution. In this paper, we develop an on-line two-level Neural Network (NN) model which can accurately untangle the complex dependencies among tasks and jobs, and predict their execution classes in an extremely dynamic and heterogeneous system. Our proposed NN model predicts first the job class, and secondly three classes of failed tasks of failed jobs, based on a sliding learning window. Furthermore, we develop resource conservation policies that terminate failed tasks of failed jobs after a grace period that is derived from prediction confidences and task execution times. Overall, evaluating our results on a Google cluster trace, we are able to accurately capture failures of failures at big-data clusters, mitigate false negative tasks to 1%, and efficiently save system resources, achieving significant reductions of CPU, memory and disk consumption - as high as 49%.

Many profilers based on bytecode instrumentation yield wrong results in the presence of an optimizing dynamic compiler, either due to not being aware of optimizations such as stack allocation and method inlining, or due to the inserted code disrupting such optimizations. To avoid such perturbations, we present a novel technique to make any profiler implemented at the bytecode level aware of optimizations performed by the dynamic compiler. We implement our approach in a state-of-the-art Java virtual machine and demonstrate its significance with concrete profilers. We quantify the impact of escape analysis on allocation profiling, object life-time analysis, and the impact of method inlining on callsite profiling. We illustrate how our approach enables new kinds of profilers, such as a profiler for non-inlined callsites, and a testing framework for locating performance bugs in dynamic compiler implementations.

Runtime verification validates the correctness of a program's execution trace.Much work has been done on improving the expressiveness and efficiency of runtime verification.However, current approaches require static deployment of the verification logic and are often restricted to a limited set of events that can be captured and analyzed, hindering the adoption of runtime verification in production systems.A popular system for runtime verification in Java, JavaMOP (Monitor-Oriented Programming in Java), suffers from the aforementioned limitations due to its dependence on AspectJ, which supports neither dynamic weaving nor an extensible join-point model.In this paper, we extend the JavaMOP framework with a dynamic deployment API and a new MOP specification translator, which targets the domain-specific aspect language DiSL instead of AspectJ; DiSL offers an open join-point model that allows for extensions.A case study on lambda expressions in Java8 demonstrates the extensibility of our approach.Moreover, in comparison with JavaMOP using load-time weaving, our implementation reduces runtime overhead by 21%, and heap memory usage by 16%, on average.

Runtime verification validates the correctness of a program’s execution trace. Much work has been done on improving the expressiveness and efficiency of runtime verification. However, current approaches require static deployment of the verification logic and are often restricted to a limited set of events that can be captured and analyzed, hindering the adoption of runtime verification in production systems. A popular system for runtime verification in Java, JavaMOP (Monitor-Oriented Programming in Java), suffers from the aforementioned limitations due to its dependence on AspectJ, which supports neither dynamic weaving nor an extensible join-point model. In this article, we extend the JavaMOP framework with a dynamic deployment API and a new MOP specification translator, which targets the domain-specific aspect language DiSL instead of AspectJ; DiSL offers an open join-point model that allows for extensions. A case study on lambda expressions in Java8 demonstrates the extensibility of our approach. Moreover, in comparison with JavaMOP using load-time weaving, our implementation reduces runtime overhead by 32%, and heap memory usage by 13%, on average.

Provisioning strategies relying on CPU load may be suboptimal for many applications, because the relation between CPU load and application performance can be non-linear and complex. With the knowledge of the relation between CPU load and application performance, resource provisioning strategies could be tuned to a particular application, but the required knowledge is difficut to obtain, because classic benchmarking is not suited for performance evaluation of partial-load scenarios. As a remedy, we present Showstopper, a tool capable of achieving and sustaining a predefined partial CPU load (or replay a load trace) by controlling the execution of arbitrary CPU-bound workloads. By analyzing performance interference among applications running in colocated virtual machines, we demonstrate how Showstopper enables systematic and reproducible exploration of the platform- and application-specific relation between CPU load and application performance.

In this paper, we present ParSim, a software tool designed for modeling parallel applications. The tool reproduces a workload, including its parallel characteristics specified by the users, on the target multicore or multiCPU system, and analyzes the collected data. The objective of ParSim is to close the gap between the "generalized" benchmarks, designed for conventional system architectures, and the peculiar needs of parallel environments based on multicore systems. A simple language for the description of parallel features of an application and specific analysis techniques are provided. We present the working context and principles of ParSim, its architecture and its features, and validate our tool through its application on a case study.

SUMMARY Although modern computer hardware offers an increasing number of processing elements organized in nonuniform memory access (NUMA) architectures, prevailing middleware engines for executing business processes, workflows, and Web service compositions have not been optimized for properly exploiting the abundant processing resources of such machines. Amongst others, factors limiting performance are inefficient thread scheduling by the operating system, which can result in suboptimal use of system memory and CPU caches, and sequential code sections that cannot take advantage of multiple available cores. In this article, we study the performance of the JOpera process execution engine on recent multicore machines. We first evaluate its performance without any dedicated optimization for multicore hardware, showing that additional cores do not significantly improve performance, although the engine has a multithreaded design. Therefore, we apply optimizations on the basis of replication together with an improved, hardware‐aware usage of the underlying resources such as NUMA nodes and CPU caches. Thanks to our optimizations, we achieve speedups from a factor of 2 up to a factor of 20 (depending on the target machine) when compared with a baseline execution ‘as is’. Copyright © 2012 John Wiley & Sons, Ltd.

The goal of multi-objective quality-driven service selection (QDSS) is to find service selections for a workflow whose quality-of-service (QoS) values are Pareto-optimal. We consider multiple QoS attributes such as response time, cost, and reliability. A selection is Pareto-optimal if no other selection has better QoS values for some attributes and at least equivalent values for all others. Exact algorithms have been proposed that find all Pareto-optimal selections. They suffer however from exponential complexity. Randomized algorithms scale well but do not offer any formal guarantees on result precision. We present the first approximation scheme for QDSS. It aims at the sweet spot between exact and randomized algorithms: It combines polynomial complexity with formal result precision guarantees. A parameter allows to seamlessly trade result precision against efficiency. We formally analyze complexity and precision guarantees and experimentally compare our algorithm against exact and randomized approaches. Comparing with exact algorithms, our approximation scheme allows to reduce optimization time from hours to seconds. Its approximation error remains below 1.4 percent while randomized algorithms come close to the theoretical maximum.

Cloud computing is a well known paradigm, featuring on-demand provisioning of virtual machines (VMs) with different sizes and images. Systems deployed in the cloud can thus be heterogeneous, i.e., using multiple different types of VM instances. The immediate performance challenge arises: how to best use heterogeneous VM instances such that the experienced performance, i.e., response times, on different VMs are similar. In this paper, we first show to what extent deployed systems are heterogeneous in clouds by collecting data from operational data centers. We also show that response times suffer from high variance across replicas hosted on different VMs. We develop a novel plug&play workload controller, Join-the-Best-Queue (JBQ), which aims to reduce the variance and higher percentile of response-times in heterogeneous environments. With the aid of a testbed hosting part of wikipedia in an operational cloud, we show that JBQ can significantly reduce performance variability across different VMs, compared to prevailing load distributing policies in the Apache web server.

Dynamic analysis tools are often implemented using instrumentation, particularly on managed runtimes including the Java Virtual Machine (JVM). Performing instrumentation robustly is especially complex on such runtimes: existing frameworks offer limited coverage and poor isolation, while previous work has shown that apparently innocuous instrumentation can cause deadlocks or crashes in the observed application. This paper describes ShadowVM, a system for instrumentation-based dynamic analyses on the JVM which combines a number of techniques to greatly improve both isolation and coverage. These centre on the offload of analysis to a separate process; we believe our design is the first system to enable genuinely full bytecode coverage on the JVM. We describe a working implementation, and use a case study to demonstrate its improved coverage and to evaluate its runtime overhead.

The Java Virtual Machine (JVM) today hosts implementations of numerous languages. To achieve high performance, JVM implementations rely on heuristics in choosing compiler optimizations and adapting garbage collection behavior. Historically, these heuristics have been tuned to suit the dynamics of Java programs only. This leads to unnecessarily poor performance in case of non-Java languages, which often exhibit systematic differences in workload behavior. Dynamic metrics characterizing the workload help to identify and quantify useful optimizations, but so far, no cohesive suite of metrics has adequately covered properties that vary systematically between Java and non-Java workloads. We present a suite of such metrics, justifying our choice with reference to a range of guest languages. These metrics are implemented on a common portable infrastructure which ensures ease of deployment and customization.

In this paper we compare different approaches to maintain shadow state for heap objects in Java. We identify dynamic analyses that need to shadow heap objects, and we consider their requirements. We describe three very different approaches in detail: using a hash map, heap tagging, and injecting shadow fields.

JavaScript, the most popular language on the Web, is rapidly moving to the server-side, becoming even more pervasive. Still, JavaScript lacks support for shared memory parallelism, making it challenging for developers to exploit multicores present in both servers and clients. In this paper we present TigerQuoll, a novel API and runtime for parallel programming in JavaScript. TigerQuoll features an event-based API and a parallel runtime allowing applications to exploit a mutable shared memory space. The programming model of TigerQuoll features automatic consistency and concurrency management, such that developers do not have to deal with shared-data synchronization. TigerQuoll supports an innovative transaction model that allows for eventual consistency to speed up high-contention workloads. Experiments show that TigerQuoll applications scale well, allowing one to implement common parallelism patterns in JavaScript.

DiSL is a new domain-specific language for bytecode instrumentation with complete bytecode coverage. It reconciles expressiveness and efficiency of low-level bytecode manipulation libraries with a convenient, high-level programming model inspired by aspect-oriented programming. This paper summarizes the language features of DiSL and gives a brief overview of several dynamic program analysis tools that were ported to DiSL. DiSL is available as open-source under the Apache 2.0 license.

A detailed and accurate characterization of the parallelism of applications is essential for predicting their wall-time on different platforms, both for an application running in isolation and for a set of consolidated applications executing on the same platform. However, prevailing profilers are often based on sampling and do not provide exact information on the parallelism of the profiled application. In this paper we present a novel profiler that logs all thread scheduling activities within the operating system kernel. These logs enable us to accurately characterize applications' parallelism on a given platform by computing the number of threads that are active at each moment. We also present a simple mathematical prediction model to estimate wall-time for program execution on a k2-core machine using profiles collected using a k1-core machine (of the same architecture and running at the same clock speed). We use our profiler to assess the parallelism of several CPU-bound DaCapo benchmarks and evaluate the accuracy of our prediction model.

Today's web services are commonly hosted on clusters of servers that are often located within computing clouds, whose computational and storage resources can be highly heterogeneous. The workload served typically exhibits disparate computation patterns (e.g., CPU-intensive or IO-intensive), that fluctuate both in terms of volume and mix. The system heterogeneity together with workload diversity further exacerbates the challenge of effective distribution of load within a computing cloud. This paper presents a novel, mix-aware load-balancing algorithm, which aims to distribute requests sent by multiple applications in heterogeneous servers such that the application response times are minimized and system resources (e.g., CPU and IO) are equally utilized. To this end, the presented algorithm tries to not only balance the total number of requests seen by each server, but also to shape the requests received by each server into a certain "mix", that is analytically shown to be optimal for response time minimization. Our experimental results---based both on simulation and on a prototype implementation---show that the mix-aware algorithm achieves robust performance in most workload mixes as well as a consistent performance improvement in comparison with one of the most robust load-balancing schemes of the Apache server.

SUMMARY As a key part of reverse engineering, decompilation plays a very important role in software security and maintenance. A number of tools, such as Boomerang and IDA Hex_rays, have been developed to translate executable programs into source code in a relatively high‐level language. Unfortunately, most existing decompilation tools suffer from low accuracy in identifying variables, functions, and composite structures, resulting in poor readability. To address these limitations, we present a practical decompiler called C‐Decompiler for Windows C programs that (i) uses a shadow stack to perform refined data flow analysis, (ii) adopts inter‐basic‐block register propagation to reduce redundant variables, and (iii) recognizes library (i.e., Standard Template Library) functions by signatures. We evaluate and compare the decompilation quality of C‐Decompiler with two existing tools, Boomerang and IDA Hex_rays, considering four aspects: function analysis, variable expansion rate, total percentage reduction, and cyclomatic complexity. Our experimental results show that on average, C‐Decompiler has the highest total percentage reduction of 55.91%, lowest variable expansion rate of 55.79%, and the same cyclomatic complexity as the original source code for each considered application. Furthermore, in our experiments, C‐Decompiler is able to recognize functions with a lower false positive and false negative rate than the other decompilers. A case study and our evaluation results confirm that C‐Decompiler is a practical tool to produce highly readable C‐style code. Copyright © 2012 John Wiley & Sons, Ltd.

There is an emerging trend to deploy services in cloud environments due to their flexibility in providing virtual capacity and pay-as-you-go billing features. Cost-aware services demand computation capacity such as virtual machines (VMs) from a cloud operator according to the workload (i.e., service invocations) and pay for the amount of capacity used following billing contracts. However, as recent empirical studies show, the performance variability, i.e., non-uniform VM performance, is inherently higher than in private hosting platforms, since cloud platforms provide VMs running on top of typically heterogeneous hardware shared by multiple clients. Consequently, the provisioning of service capacity in a cloud needs to consider workload variability as well as varying VM performance. We propose an opportunistic service replication policy that leverages the variability in VM performance, as well as the on-demand billing features of the cloud. Our objective is to minimize the service provisioning costs by keeping a lower number of faster VMs, while maintaining target system utilization. Our evaluation results on traces collected from in-production systems show that the proposed policy achieves significant cost savings and low response times.

Service-oriented systems, consisting of atomic services and their compositions hosted in service composition execution engines (CEEs), are commonly deployed to deliver web applications. As the workloads of applications fluctuate over time, it is economical to autonomously and dynamically adjust system capacity, i.e., the number of replicas for atomic services and CEEs. In this paper, we propose a novel replica provisioning policy, Resos, which adjusts the number of CEE and service replicas periodically based on the predicted workloads such that all replicas are well utilized at the target values. In particular, Resos models the workload balance and dependency between CEE and service replicas by estimating the probability that threads of CEE replicas are not blocked by I/O. Moreover, we derive the analytical bounds of CEE effective utilization and illustrate the cause of low nominal utilization at CEE replicas. We evaluate Resos on a simulated service-oriented system, which hosts CEE and service replicas on multi-threaded servers. The evaluated workload is derived from utilization traces collected from production systems. Through simulation, we demonstrate that Resos effectively reduces the number of required replicas while maintaining target utilization and lowering the response times of requests.

Parallelization is attractive for speeding up dynamic program analysis on multicores. However, inter-thread communication overhead may outweigh any benefit from parallel execution. We propose deferred methods, a high-level Java framework to accelerate dynamic analysis on multicores. To minimize inter-thread communication overhead, invocations to analysis methods are automatically aggregated in thread-local buffers that are processed when full. In contrast to other approaches, our framework supports custom buffer processing strategies, eases pre-processing of buffers to reduce contention on shared data structures, and offers a synchronization mechanism to wait for the completion of previously invoked deferred methods. We also present a novel adaptive buffer processing strategy that parallelizes the analysis only when the observed workload leaves some CPU cores under-utilized. Using a profiler as case study, we show that deferred methods with the adaptive buffer processing strategy yield an average speedup of factor 4.09 on a quad-core machine. The speedup stems both from parallelization and from reduced contention.

Optimal resource allocation and application consolidation on modern multicore systems that host multiple applications is not easy. Striking a balance among conflicting targets such as maximizing system throughput and system utilization while minimizing application response times is a quandary for system administrators. The purpose of this work is to offer a methodology that can automate the difficult process of identifying how to best consolidate workloads in a multicore environment. We develop a simple approach that treats the hardware and the operating system as a black box and uses measurements to profile the application resource demands. The demands become input to a queueing network model that successfully predicts application scalability and that captures the performance impact of consolidated applications on shared on-chip and off-chip resources. Extensive analysis with the widely used DaCapo Java benchmarks on an IBM Power 7 system illustrates the model's ability to accurately predict the system's optimal application mix.

Consolidation of multiple applications with diverse and changing resource requirements is common in multicore systems as hardware resources are abundant and opportunities for better system usage are plenty. Can we maximize resource usage in such a system while respecting individual application performance targets or is it an oxymoron to simultaneously meet such conflicting measures? In this work we provide a solution to the above difficult problem by constructing a queueing-theory based tool that we use to accurately predict application scalability on multicores and that can also provide the optimal consolidation suggestions to maximize system resource usage while meeting simultaneously application performance targets. The proposed methodology is light-weight and relies on capturing application resource demands using standard tools, via nonintrusive low-level measurements. We evaluate our approach on an IBM Power7 system using the DaCapo and SPECjvm benchmark suites where each benchmark exhibits different patterns of parallelism. From 900 different consolidations of application instances, our tool accurately predicts the average iteration time of allocated applications with an average error below 10%.

Modern processor architectures are increasingly complex and heterogeneous, often requiring solutions tailored to the specific characteristics of each processor model. In this paper we address this problem by targeting the AMD Bulldozer processor as case study for specific hardware-oriented performance optimizations. The Bulldozer architecture features an asymmetric simultaneous multithreading implementation with shared floating point units (FPUs) and per-core arithmetic logic units (ALUs). Bulld Over, presented in this paper, improves thread scheduling by exploiting this hardware characteristic to increase performance of floating point-intensive workloads on Linux-based operating systems. Bulld Over is a user-space monitoring tool that automatically identifies FPU-intensive threads and schedules them in a more efficient way without requiring any patches or modifications at the kernel level. Our measurements using standard benchmark suites show that speedups of up to 10% can be achieved by simply allowing Bulld Over to monitor applications, without any modification of the workload.

While often designed with a single language in mind, managed runtimes like the Java virtual machine (JVM) have become the target of not one but many languages, all of which benefit from the runtime's services. One of these services is automatic memory management. In this paper, we compare and contrast the memory behaviour of programs written in Java and Scala, respectively, two languages which both target the same platform: the JVM. We both analyze core object demographics like object lifetimes as well as secondary properties of objects like their associated monitors and identity hash-codes. We find that objects in Scala programs have lower survival rates and higher rates of immutability, which is only partly explained by the memory behaviour of objects representing closures or boxed primitives. Other metrics vary more by benchmark than language.

There is an urgent need for novel programming abstractions to leverage the parallelism in modern multicore machines. We introduce S, a new domain-specific language targeting the server-side scripting of high-performance RESTful Web services. S promotes an innovative programming model based on explicit (control-flow) and implicit (process-level) parallelism control, allowing the service developer to specify which portions of the control-flow should be executed in parallel. For each service, the choice of the best level of parallelism is left to the runtime system. We assess performance and scalability by implementing two non-trivial composite Web services in S. Experiments show that S-based Web services can handle thousands of concurrent client requests on a modern multicore machine.

Modern multicore platforms allow system administrators to reduce the costs of the IT infrastructure by consolidating heterogeneous workloads on the same physical machine. To this end, it is important to develop efficient profiling techniques and accurate performance predictions to avoid violating service level objectives. In this work we present Tresa, a novel tool to automatically characterize workloads and accurately estimate the execution time of different consolidations. These results can be used to optimize consolidations depending on service-level objectives.

SUMMARY Although traditional approaches to code profiling help locate performance bottlenecks, they offer only limited support for removing these bottlenecks. The main reason is the lack of detailed visual runtime information to identify and eliminate computation redundancy. We provide three profiling blueprints that help identify and remove performance bottlenecks. Thestructural distribution blueprintgraphically represents the CPU consumption share for each method and class of an application. Thebehavioral distribution blueprintdepicts the distribution of CPU consumption along method invocations and hints at method candidates for caching optimizations. Thebehavioral evolution blueprintcompares profiles of different versions of a software system and highlights performance‐critical changes in the system. These three blueprints helped us to significantly optimize Mondrian, an open source visualization engine. Our implementation is freely available for the Pharo development environment and has been evaluated in a number of different scenarios. Copyright © 2011 John Wiley & Sons, Ltd.

Object-oriented frameworks are widely used to develop new applications. They provide reusable concepts that are instantiated in application code through potentially complex implementation steps such as subclassing, implementing interfaces, and calling framework operations. Unfortunately, many modern frameworks are difficult to use because of their large and complex APIs and frequently incomplete user documentation. To cope with these problems, developers often use existing framework applications as a guide. However, locating concept implementations in those sample applications is typically challenging due to code tangling and scattering. To address this challenge, we introduce the notion of concept-implementation templates, which summarize the necessary concept-implementation steps and identify them in the sample application code, and a technique, named FUDA, to automatically extract such templates from dynamic traces of sample applications. This paper further presents the results of two experiments conducted to evaluate the quality and usefulness of FUDA templates. The experimental evaluation of FUDA with 14 concepts in five widely used frameworks suggests that the technique is effective in producing templates with relatively few false positives and false negatives for realistic concepts by using two sample applications. Moreover, we observed in a user study with 28 programmers that the use of templates reduced the concept-implementation time compared to when documentation was used.

Modern IDEs such as Eclipse offer static views of the source code, but such views ignore information about the runtime behavior of software systems. Since typical object-oriented systems make heavy use of polymorphism and dynamic binding, static views will miss key information about the runtime architecture. In this paper, we present an approach to gather and integrate dynamic information in the Eclipse IDE with the goal of better supporting typical software maintenance activities. By means of a controlled experiment with 30 professional developers, we show that for typical software maintenance tasks, integrating dynamic information into the Eclipse IDE yields a significant 17.5 percent decrease of time spent while significantly increasing the correctness of the solutions by 33.5 percent. We also provide a comprehensive performance evaluation of our approach.

To avoid data cache trashing between heap-allocated data and other data areas, a distinct object cache has been proposed for embedded real-time Java processors. This object cache uses high associativity in order to statically track different object pointers for worst-case execution-time analysis. However, before implementing such an object cache, an empirical analysis of different organization forms is needed. We use a cross-profiling technique based on aspect-oriented programming in order to evaluate different object cache organizations with standard Java benchmarks. From the evaluation we conclude that field access exhibits some temporal locality, but almost no spatial locality. Therefore, filling long cache lines on a miss just introduces a high miss penalty without increasing the hit rate enough to make up for the increased miss penalty. For an object cache, it is more efficient to fill individual words within the cache line on a miss.

Originally conceived as the target platform for Java alone, the Java Virtual Machine (JVM) has since been targeted by other languages, one of which is Scala. This trend, however, is not yet reflected by the benchmark suites commonly used in JVM research. In this paper, we thus present the design and analysis of the first full-fledged benchmark suite for Scala. We furthermore compare the benchmarks contained therein with those from the well-known DaCapo 9.12 benchmark suite and show where the differences are between Scala and Java code---and where not.

Dynamic updates to running programs improve development productivity and reduce downtime of long-running applications. This feature is however severely limited in current virtual machines for object-oriented languages. In particular, changes to classes often apply only to methods invoked after a class change, but not to active methods on the call stack of threads. Additionally, adding and removing methods as well as fields is often not supported.

Service-oriented architectures (SOAs) provide a successful model for structuring complex distributed software systems, as they reduce the cost of ownership and ease the creation of new applications by composing existing services. However, currently, the development of service-oriented applications requires many manual tasks and prevailing infrastructure is often based on centralized components that are central points of failure and easily become bottlenecks. In this paper, we promote self-organizing SOA as a new approach to overcome these limitations. Self-organizing SOA integrates research results in the areas of autonomic and service oriented computing. We consider self-organizing features for the whole life-cycle of a service-oriented application, from the creation to the execution, optimization, and monitoring.

Abstract Many profilers for virtual execution environments, such as the Java virtual machine (JVM), are implemented with low‐level bytecode instrumentation techniques, which is tedious, error‐prone, and complicates maintenance and extension of the tools. In order to reduce the development time and cost, we promote building profilers for the JVM using high‐level aspect‐oriented programming (AOP). We show that the use of aspects yields concise profilers that are easy to develop, extend, and maintain, because low‐level instrumentation details are hidden from the tool developer. In order to build efficient profilers, we introduce inter‐advice communication, an extension to common AOP languages that enables efficient data passing between advices that are woven into the same method using local variables. We illustrate our approach with two case studies. First, we show that an existing, instrumentation‐based tool for listener latency profiling can be easily recast as an aspect. Second, we present an aspect for comprehensive calling context profiling. In order to reduce profiling overhead, our aspect parallelizes application execution and profile creation, resulting in a speedup of 110% on a machine with more than two cores, compared with a primitive, non‐parallel approach. Copyright © 2011 John Wiley & Sons, Ltd.

Performance and scalability of service-oriented applications, such as Web service compositions or business processes, depend on the dynamically bound services. In order to handle an increasing number of clients, load-balancing techniques are important. In this paper we assume the presence of multiple functionally equivalent services and explore different load-balancing algorithms to dynamically select service bindings with the goal to reduce average service response time. Using mathematical queueing models of service performance and simulation, we compare different service selection algorithms, including Static Lottery, Round-Robin, and Shortest-Queue. Furthermore, we propose linear and quadratic Dynamic Lottery service selection algorithms, which assign and periodically update service selection probabilities according to monitored average service response time. Our simulation environment models both stateless and stateful services and offers a wide range of service performance models with different degrees in the variation of service response time. While the Shortest-Queue algorithm performs best in simulation settings with only stateless services or low variance of service response time, the Round-Robin and Dynamic Lottery algorithms work best in settings with stateful services and high variance of service performance.

Middleware for web service orchestration, such as runtime engines for executing business processes, workflows, or web service compositions, can easily become performance bottlenecks when the number of concurrent service requests increases. Many existing process execution engines have been designed to address scalability with distribution and replication techniques. However, the advent of modern multicore machines, comprising several chip multi-processors each offering multiple cores and often featuring a large shared cache, offers the opportunity to redesign the architecture of process execution engines in order to take full advantage of the underlying hardware resources. In this paper we present an innovative process execution engine architecture. Its design takes into account the specific constraints of multicore machines and scales well on different processor architectures, as shown by our extensive performance evaluation. A key feature of the design is self-configuration at startup according to the type and number of available CPUs. We show that our design makes efficient use of the available resources and can scale to run thousands of concurrent business process instances per second, highlighting the potential and the benefits for multicore-awareness in the design of scalable process execution engines.

Commercial services for provisioning software components and virtual infrastructure in the cloud are emerging. For customers, this creates a multitude of possibilities for outsourcing part of the IT-stack to third parties in order to run their applications. These possibilities are associated with different running costs, so cloud customers have to determine the optimal solution. In this paper, we present and experimentally evaluate an algorithm that solves the corresponding optimization problem. We assume that applications are described as templates, fixing the deployment structure and constraining the properties of the used soft- and hardware components. Different parts of the application may be outsourced to different providers and several levels of outsourcing can be considered. However, dependencies between different parts of the application have to be respected. Our algorithm decomposes the application graph in a first step-in order to discover all suitable cloud provisioning services from a registry. It determines the optimal solution by representing the problem as constraint optimization problem that can be solved by an existing solver implementation.

Dynamically adaptive systems propose adaptation by means of variants that are specified in the system model at design time and allow for a fixed set of different runtime configurations. However, in a dynamic environment, unanticipated changes may result in the inability of the system to meet its quality requirements. To allow the system to react to these changes we propose a solution for automatically evolving the system model by integrating new variants and periodically validating existing ones based on updated quality parameters. To illustrate our approach we present a BPEL based framework using a service composition model to represent the system functional requirements. Our framework estimates Quality of Service (QoS) values based on information provided by our monitoring mechanism, ensuring that changes in QoS are reflected in the system model. We show how the evolved model can be used at runtime to increase the system's autonomic capabilities and delivered QoS.

Aspect-oriented programming provides a convenient high-level model to define several kinds of dynamic analyses, in particular thanks to recent advances in exhaustive weaving in core libraries. Casting dynamic analyses as aspects allows the use of a single weaving infrastructure to apply different analyses to the same base program, simultaneously. However, even if dynamic analysis aspects are mutually independent, their mere presence perturbates the observations of others: this is due to the fact that aspectual computation is potentially visible to all aspects. Because current aspect composition approaches do not address this kind of computational interference, combining different analysis aspects yields at best unpredictable results. It is also impossible to flexibly combine various analyses, for instance to analyze an analysis aspect. In this paper we show how the notion of execution levels makes it possible to effectively address these composition issues. In order to realize this approach, we explore the practical and efficient integration of execution levels in a mainstream aspect language, AspectJ. We report on a case study of composing two out-of-the-box analysis aspects in a variety of ways, highlighting the benefits of the approach.

While dynamic code evolution in object-oriented systems is an important feature supported by dynamic languages, there is currently only limited support for dynamic code evolution in high-performance, state-of-the-art runtime systems for statically typed languages, such as the Java Virtual Machine. In this tool demonstration, we present the Dynamic Code Evolution VM, which is based on a recent version of Oracle's state-of-the-art Java HotSpot(TM) VM and allows unlimited changes to loaded classes at runtime. Based on the Dynamic Code Evolution VM, we developed an enhanced version of the Mantisse GUI builder (which is part of the NetBeans IDE) that allows adding GUI components without restarting the application under development. Furthermore, we redesigned the dynamic AOP framework HotWave to take advantage of the enhanced dynamic code evolution capabilities. The new version, HotWave2, now supports most AspectJ constructs, including around() advice and static cross-cutting. We will demonstrate both the enhanced Mantisse GUI builder as well as HotWave2, weaving several aspects for dynamic analysis in sizable applications at runtime.

SOABench is a framework for the automatic generation, execution and analysis of testbeds for evaluating the performance of service-oriented middleware. Testbeds can be characterized in terms of the composite services to execute, the workload to generate, the deployment configuration to use, the performance metrics to gather, the data analyses to perform on them, and the reports to produce.

Middleware for Web service compositions, such as BPEL engines, provides the execution environment for services as well as additional functionalities, such as monitoring and self-tuning. Given its role in service provisioning, it is very important to assess the performance of middleware in the context of a SOA. This paper presents SOABench, a framework for the automatic generation and execution of testbeds for benchmarking middleware for composite Web services and for assessing the performance of existing SOA infrastructures. SOABench defines a testbed model characterized by the composite services to execute, the workload to generate, the deployment configuration to use, the performance metrics to gather, the data analyses to perform on them, and the reports to produce. We have validated SOABench by benchmarking the performance of different BPEL engines.

Abstract Calling context profiling is an important technique for analyzing the performance of object‐oriented software with complex inter‐procedural control flow. The Calling Context Tree (CCT) is a common data structure that stores dynamic metrics, such as CPU time, separately for each calling context. As CCTs may comprise millions of nodes, there is a need for a condensed visualization that eases the localization of performance bottlenecks. In this article, we discussCalling Context Ring Charts(CCRCs), a compact visualization for CCTs, where callee methods are represented in ring segments surrounding the caller's ring segment. In order to reveal hot methods, their callers, and callees, the ring segments can be sized according to a chosen dynamic metric. We describe two case studies where CCRCs help us to detect and fix performance problems in applications. A performance evaluation also confirms that our implementation can efficiently handle large CCTs. Copyright © 2010 John Wiley & Sons, Ltd.

Dynamic aspect-oriented programming (AOP) enables runtime adaptation of aspects, which is important for building sophisticated, aspect-based software engineering tools, such as adaptive profilers or debuggers that dynamically modify instrumentation code in response to user interactions. Today, many AOP frameworks for Java, notably AspectJ, focus on aspect weaving at compile-time or at load-time, and offer only limited support for aspect adaptation and reweaving at runtime. In this paper, we introduce HotWave, an AOP framework based on AspectJ for standard Java Virtual Machines (JVMs). HotWave supports dynamic (re)weaving of previously loaded classes, and it ensures that all classes loaded in a JVM can be (re)woven, including the classes of the standard Java class library. HotWave features a novel mechanism for inter-advice communication, enabling efficient data passing between advices that are woven into the same method. We explain HotWave's programming model and discuss our implementation techniques. As case study, we present an adaptive, aspect-based profiler that leverages HotWave's distinguishing features.

Developing tools for profiling, debugging, testing, and reverse engineering is error-prone, time-consuming, and therefore costly when using low-level techniques, such as bytecode instrumentation. As a solution to these problems, we promote tool development in Java using high-level aspect-oriented programming (AOP). We demonstrate that the use of aspects yields compact tools that are easy to develop and extend. As enabling technology, we rely on HotWave, a new tool for dynamic and comprehensive aspect weaving. HotWave reconciles compatibility with existing virtual machine and AOP technologies. It provides support for runtime adaptation of aspects and reweaving of previously loaded code, as well as the ability to weave aspects into all methods executing in a Java Virtual Machine, including methods in the standard Java class library. HotWave also features a new mechanism for efficiently passing data between advices that are woven into the same method. We demonstrate the benefits of HotWave's distinguishing features with two case studies in the area of profiling.

REMAN is a reputation management infrastructure for composite Web services. It supports the aggregation of client feedback on the perceived QoS of external services, using reputation mechanisms to build service rankings. Changes in rankings are pro-actively notified to composite service clients to enable self-tuning properties in their execution.

Mainstream IDEs such as Eclipse support developers in managing software projects mainly by offering static views of the source code. Such a static perspective neglects any information about runtime behavior. However, object-oriented programs heavily rely on polymorphism and late-binding, which makes them difficult to understand just based on their static structure. Developers thus resort to debuggers or profilers to study the system's dynamics. However, the information provided by these tools is volatile and hence cannot be exploited to ease the navigation of the source space. In this paper we present an approach to augment the static source perspective with dynamic metrics such as precise runtime type information, or memory and object allocation statistics. Dynamic metrics can leverage the understanding for the behavior and structure of a system. We rely on dynamic data gathering based on aspects to analyze running Java systems. By solving concrete use cases we illustrate how dynamic metrics directly available in the IDE are useful. We also comprehensively report on the efficiency of our approach to gather dynamic metrics.

Maintaining object-oriented systems that use inheritance and polymorphism is difficult, since runtime information, such as which methods are actually invoked at a call site, is not visible in the static source code. We have implemented Senseo, an Eclipse plugin enhancing Eclipse's static source views with various dynamic metrics, such as runtime types, the number of objects created, or the amount of memory allocated in particular methods.

Developing and maintaining tools for profiling, debugging, testing, and reverse engineering can be difficult when using low-level techniques, such as bytecode instrumentation. We promote tool development in Java using high-level aspect-oriented programming. We demonstrate that the use of aspects yields concise tools that are easy to develop, extend, and maintain, because low-level instrumentation details are hidden from the developer. We introduce MAJOR, a new tool for comprehensive aspect weaving, which ensures that aspects are woven into all classes executing in a Java Virtual Machine, including those in the standard Java class library. MAJOR includes the pluggable module CARAJillo, which supports efficient access to a complete and customizable calling context representation. Both distinguishing features of MAJOR - comprehensive aspect weaving and efficient access to complete calling information - are essential in the aforementioned domains.

Calling context profiling is an important technique for locating hotspots in programs. The prevailing data structure is the Calling Context Tree (CCT) that provides dynamic metrics for each calling context. Existing approaches to calling context profiling in Java either limit portability due to the use of native code or of a modified Java Virtual Machine, create incomplete and inaccurate CCTs, or cause excessive overhead. In this paper, we introduce Complete Calling Context Profiling (CCCP), a new approach that reconciles completeness and accuracy of the created CCTs, portability, and moderate overhead. CCCP relies on a generic bytecode instrumentation framework ensuring comprehensive bytecode coverage, including also the standard Java class library. In order to reduce the overhead of accessing the current CCT node, CCCP transforms code such that the caller passes its CCT node to the callee as a special method argument, while ensuring compatibility with native code, reflection, and stack introspection. We use the resulting CCTs for a detailed analysis of the dynamic behavior of Java systems and present a thorough analysis of the origin of runtime overheads.

Performance evaluation of embedded software is essential in an early development phase so as to ensure that the software will run on the embedded device's limited computing resources. Prevailing approaches either require the deployment of the software on the embedded target, which can be tedious and may be impossible in an early development phase, or rely on simulation, which can be very slow. In this paper we present CProf, a customizable cross-profiler for embedded Java processors. It allows the developer to profile the embedded software in the host environment, completely decoupled from the target system, in a standard Java Virtual Machine, but the generated profiles represent the execution time metric of the target system. CProf enables calling context cross-profiling and customizable online processing of profiling data. Furthermore, it supports pluggable CPU cycle estimation and cache simulation strategies, easing the reconfiguration for different target processors. Using the Java Optimized Processor JOP as target, CProf's cross-profiles have only a small percent error below 3.3%.

Abstract Many read‐intensive systems where fast access to data is more important than the rate at which data can change make use of multidimensional index structures, like the generalized search tree (GiST). Although in these systems the indexed data are rarely updated and read access is highly concurrent, the existing concurrency control mechanisms for multidimensional index structures are based on locking techniques, which cause significant overhead. In this article we present the multiversion‐GiST (MVGiST), an in‐memory mechanism that extends the GiST with multiversion concurrency control. The MVGiST enables lock‐free read access and ensures a consistent view of the index structure throughout a reader's series of queries, by creating lightweight, read‐only versions of the GiST that share unchanging nodes among themselves. An example of a system with high read to write ratio, where providing wait‐free queries is of utmost importance, is a large‐scale directory that indexes web services according to their input and output parameters. A performance evaluation shows that for low update rates, the MVGiST significantly improves scalability w.r.t. the number of concurrent read accesses when compared with a traditional, locking‐based concurrency control mechanism. We propose a technique to control memory consumption and confirm through our evaluation that the MVGiST efficiently manages memory. Copyright © 2009 John Wiley & Sons, Ltd.

Abstract Virtual execution environments, such as the Java virtual machine, promote platform‐independent software development. However, when it comes to analyzing algorithm complexity and performance bottlenecks, available tools focus on platform‐specific metrics, such as the CPU time consumption on a particular system. Other drawbacks of many prevailing profiling tools are high overhead, significant measurement perturbation, as well as reduced portability of profiling tools, which are often implemented in platform‐dependent native code. This article presents a novel profiling approach, which is entirely based on program transformation techniques, in order to build a profiling data structure that provides calling‐context‐sensitive program execution statistics. We explore the use of platform‐independent profiling metrics in order to make the instrumentation entirely portable and to generate reproducible profiles. We implemented these ideas within a Java‐based profiling tool called JP. A significant novelty is that this tool achieves complete bytecode coverage by statically instrumenting the core runtime libraries and dynamically instrumenting the rest of the code. JP provides a small and flexible API to write customized profiling agents in pure Java, which are periodically activated to process the collected profiling information. Performance measurements point out that, despite the presence of dynamic instrumentation, JP causes significantly less overhead than a prevailing tool for the profiling of Java code. Copyright © 2008 John Wiley & Sons, Ltd.

Abstract Performance evaluation of embedded software is essential in an early development phase so as to ensure that the software will run on the embedded device's limited computing resources. The prevailing approaches either require the deployment of the software on the embedded target, which can be tedious and may be impossible in an early development phase, or rely on simulation, which can be very slow. In this article, we introduce a customizable cross‐profiling framework for embedded Java processors, including processors featuring a method cache. The developer profiles the embedded software in the host environment, completely decoupled from the target system, on any standard Java virtual machine, but the generated profiles represent the execution time metric of the target system. Our cross‐profiling framework is based on bytecode instrumentation. We identify several pointcuts in the execution of bytecode that need to be instrumented in order to estimate the CPU cycle consumption on the target system. An evaluation using the JOP embedded Java processor as target confirms that our approach reconciles high profile accuracy with moderate overhead. Our cross‐profiling framework also enables the performance evaluation of new processor architectures before they are implemented. As a case study, we explore the performance impact of various processor design choices and optimizations, such as different cache sizes or pipeline organizations, and come up with an improved processor design that yields speedups of up to 40% on standard Java benchmarks. Copyright © 2009 John Wiley & Sons, Ltd.

Performance evaluation of embedded software is essential in an early development phase so as to ensure that the software will run on the embedded device's limited computing resources. Prevailing approaches either require the deployment of the software on the embedded target, which can be tedious and may be impossible in an early development phase, or rely on simulation, which can be very slow. In this paper, we introduce a customizable cross-profiling framework for embedded Java processors, including processors featuring a method cache. The developer profiles the embedded software in the host environment, completely decoupled from the target system, on any standard Java Virtual Machine, but the generated profiles represent the execution time metric of the target system. Our cross-profiling framework is based on bytecode instrumentation. We identify several pointcuts in the execution of bytecode that need to be instrumented in order to estimate the CPU cycle consumption on the target system. An evaluation using the JOP embedded Java processor as target confirms that our approach reconciles high profile accuracy with moderate overhead. Our cross-profiling framework also enables the rapid evaluation of the performance impact of possible optimizations, such as different caching strategies.

The dependability of composite services is largely affected by their constituent Web services. Composite services have to operate in an open and dynamically changing environment in order to leverage the best performing services available at the moment. Hence, there is the need for an efficient mechanism to provide reliable service rankings. In this paper we present a novel, generic, and customizable reputation infrastructure to automatically and transparently monitor the execution of composite services, taking both functional and non-functional properties into account. The experienced Web service quality-of-service is communicated to a configurable reputation mechanism that publishes service rankings. Our reputation infrastructure supports notifications upon changes in service reputation, enabling self-tuning and self-healing properties in the execution of composite services. We implemented our architecture using standard technologies, such as BPEL and JavaEE. Performance measurements show that our infrastructure causes only moderate overhead.

Web service directories are shared resources that have to accommodate a high number of concurrent read requests, whereas updates are relatively infrequent. To allow for the automatic composition of complex web services based on those contained in a directory, read requests may involve a series of queries which require a consistent view of the data. We have developed an efficient web service directory that is based on the Multiversion Generalised Search Tree (MVGiST), an integration of a multidimensional index structure with multiversion concurrency control. The MVGiST is able to index web services according to their input and output parameters, supports a high level of concurrent read requests, and guarantees consistency across multiple subsequent read queries. In this paper we evaluate the performance and scalability of the MVGiST and compare it with a traditional, locking-based concurrency control mechanism.

Service-level agreements (SLAs) establish a contract between service providersand clients concerning Quality of Service (QoS) parameters. Without properpenalties, service providers have strong incentives to deviate from theadvertised QoS, causing losses to the clients. Reliable QoS monitoring (andproper penalties computed on the basis of delivered QoS) are thereforeessential for the trustworthiness of a service-oriented environment. In thispaper, we present a novel QoS monitoring mechanism based on quality ratings from theclients. A reputation mechanism collects the ratings and computes theactual quality delivered to the clients. The mechanism provides incentives forthe clients to report honestly, and pays special attention to minimizing costand overhead1.

Java and the Java virtual machine (JVM) are a predominant programming language and deployment platform for complex, component-oriented systems. In current standard Java runtime systems, the failure of a single component can have significant impacts on other components. In the worst case, a malicious or erroneous component may crash the whole system. In this paper we explain why current standard JVMs are not suited to build secure and reliable component execution platforms. As main deficiencies, we identify the lack of proper component isolation and the absence of resource management mechanisms. We discuss the challenges of integrating these missing features and compare the strengths and limitations of various approaches to tackle these issues.

Traditional, centralized workflow orchestration often leads to inefficient routing of messages. To solve this problem, we present a novel scheme to execute workflows in a fully decentralized way. We introduce service invocation triggers, a lightweight infrastructure that routes messages directly from the producing service to the consuming one, enabling fully decentralized workflow orchestration.

Code instrumentation is finding more and more practical applications, but the required program transformations are often difficult to implement, due to the lack of dedicated, high-level tools. In this paper we present a novel instrumentation framework that supports the partial evaluation of compiled Java code transformation templates, with the goal of efficiently measuring chosen dynamic bytecode and control flow metrics. This framework, as well as the instrumentation code it generates, is implemented in pure Java and hence completely platform-independent. We show the benefits of our approach in several application areas, such as platform-independent resource management and profiling of software components.

Traditional, centralized orchestration of composite Web services often leads to inefficient routing of messages. To solve this problem, we present a novel scheme to execute composite Web services in a fully decentralized way. We introduce service invocation triggers, a lightweight infrastructure that routes messages directly from the producing service to the consuming one, enabling fully decentralized orchestration. An evaluation confirms that decentralized orchestration can significantly reduce the network traffic when compared with centralized orchestration

Recent algorithms for automated service composition issue many complex queries to service directories. As service directories are shared resources, they may become performance bottlenecks. In order to increase scalability, we introduce a compact directory digest, which is distributed to clients and includes all information needed for automated service composition. Therefore, complex directory queries during service composition can be avoided. We encode a directory digest as a zero-suppressed reduced ordered binary decision diagram (ZDD). In several steps, we refine a simple service composition algorithm in order to leverage the ZDD representation. Introducing specialized ZDD operations, we achieve a service composition algorithm that scales very well with an increasing size of the directory digest

This article presents a novel framework for the sampling-based profiling of Java programs, which relies on program transformation techniques. We exploit bytecode instruction counting to regularly activate a user-defined profiling agent, which processes the current call stack. This approach has several advantages, such as making the instrumentation entirely portable, generating reproducible profiles, and enabling a fine-grained adjustment of the sampling rate. Our framework offers a flexible API to write portable profiling agents in pure Java. While the overhead due to our profiling scheme is comparable to the overhead caused by prevailing, timing-based profilers, the resulting profiles are much more accurate. Copyright © 2006 John Wiley & Sons, Ltd.

Service directories are a key component of distributed systems where shared information must be managed efficiently. For a directory with a large numbers of entries, the result set of a query may be large, too. In this case, it is important to order the results according to heuristics and to retrieve them incrementally. Our contribution is an integrated directory system specially adapted to large-scale service discovery and composition. We introduce DirQL, a flexible query language for the matching and ranking of service descriptions. As results are incrementally retrieved, our system is able to lazily compute the result set based on: 1) the organization of the directory as a special balanced search tree that has an extra "intersection" discriminator, 2) a scheme for transforming the original query into one taking into account the tree structure of the directory, and 3) the organization of partial results in a heap structure sorted according to the transformed query. We also report on experimental results regarding the usage of the directory by a composition engine solving randomly generated problems.

Service matchmaking and composition has recently drawn increasing attention in the research community. Most existing algorithms construct chains of services based on exact matches of input/output types. However, this does not work when the available services only cover a part of the range of the input type. We present an algorithm that also allows partial matches and composes them using switches that decide on the required service at runtime based on the actual data type. We report experiments on randomly generated composition problems that show that using partial matches can decrease the failure rate of the integration algorithm using only complete matches by up to 7 times with no increase in the number of directory accesses required. This shows that composition with partial matches is an essential and useful element of Web service composition.

In this paper we introduce a novel scheme for portable CPU accounting and control in Java, which is based on program transformation techniques at the bytecode level and can be used with every standard Java Virtual Machine. In our approach applications, middleware, and the standard java runtime libraries (i.e., the Java Development Kit, or JDK) are modified in order to expose details regarding the execution of threads. This paper presents the details of how we re-engineer Java bytecode for CPU management, including the strategies developed for transforming the JDK itself in a fully portable way.

Service matchmaking and composition has recently drawn increasing attention in the research community. Most existing algorithms construct chains of services based on exact matches of input/output types. However, this does not work when the available services only cover a part of the range of the input type. We present an algorithm that also allows partial matches and composes them using switches that decide on the required service at runtime based on the actual data type. We report experiments on randomly generated composition problems that show that using partial matches can decrease the failure rate of the integration algorithm using only complete matches by up to 7 times with no increase in the number of directory accesses required. This shows that composition with partial matches is an essential and useful element of web service composition.

This paper presents the design of an autonomous station, which executes dynamically uploaded applications. The hardware of the autonomous station is based on a Java processor. Hence, the system software and applications are implemented in pure Java. We are relying on mobile agent technology for the distribution of applications to the station, as well as for remote maintenance and configuration.

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.