Program Analyses for Bloat Detection and Optimization



Despite the employment of faster CPUs and larger memory systems, the levels of inefficiencies in real-world programs grow surprisingly fast and there is an ever-increasing demand for performance optimization in modern software. Performance and scalability issues are becoming increasingly critical partly due to the pervasive use of object-oriented programming languages. The inefficiencies inherent in the implementation of an object-oriented language as well as the commonly adopted design and implementation principles in the object-oriented community often combine to hurt performance. The community-wide recognition of the importance of abstraction and reuse results in increased emphasis on modular design, declaration of general interfaces, and use of models and patterns. Programmers are taught to focus first and foremost on them, taking it for granted that compilers and run-time systems can remove all the inefficiencies. In a large program that is typically built on top of many layers of frameworks and libraries, a small set of inefficiencies can multiply and quickly get magnified to slow down the system. When the call stack grows to be deep, the usefulness of the dataflow analyses in a dynamic compiler becomes limited and the optimizer can no longer remove these inefficiencies. As a result, many applications suffer from chronic run-time performance problems that significantly affect scalability and performance. This is a serious problem for real-world software systems used every day by thousands of businesses. The pressing need for new optimization techniques can be especially seen as object-orientation goes everywhere into systems of any size. The extensive use of object-oriented languages in the development of memory-constrained applications such as smartphone apps (e.g., Java used in Android and C# used in Windows phones) and data-intensive systems (e.g., Hadoop, Giraph, and Hyracks) introduces numerous research challenges-- these systems have small memory space but large amounts of data to process and inefficiencies in these systems can be significantly exacerbated. The burden of reducing unnecessary work should not be only on the shoulder of hardware designers, especially in the modern era when Moore's dividend becomes less obvious. It strongly calls for higher-level performance optimization techniques that can detect and remove inefficiencies for all categories of object-oriented applications. Our group has an established record on performance optimization for large-scale systems. Our recent efforts focus on the following projects:


(1) Providing efficient infrastructures for detecting bloat

A recent piece of work focuses on the development of a tunable object lifetime profiling technique, called Resurrector [OOPSLA13]. Many existing optimization techniques (such as object pooling and pretenuring) require precise identification of object lifetimes. However, it is particularly challenging to obtain object lifetimes both precisely and efficiently: precise profiling techniques such as Merlin introduce several hundred times slowdown even for small programs while efficient approximation techniques often sacrifice precision and produce less useful lifetime information. Resurrector solves the problem by exploring the middle ground between high precision and high efficiency to find the precision-scalability sweetspot for various optimization techniques. Resurrector's design is motivated by an important observation that the scalability bottleneck of a traditional OLP algorithm (such as Merlin) lies in the need to compute transitive closures on the dead objects (e.g., Merlin's backward pass). Resurrector improves efficiency by completely eliminating this need. Similarly to Merlin, Resurrector first identifies the root dead objects whose reference counts are zero. Instead of computing transitive closures from them, Resurrector exploits object caching and reusing to find dead objects (transitively reachable from the roots) that have non-zero reference counts.


Another infrastructure we have built is a runtime framework that performs abstract dynamic slicing [PLDI10-a, TOSEM14] to identify performance problems that manifest themselves in dataflow activities. Abstract dynamic slicing, a technique that applies dynamic slicing over an abstract domain whose size is limited by bounds independent of the runtime execution. This technique is embedded in the general framework parameterized by the abstract domain. The output of this framework is an abstract dependence graph that contains abstractions of instructions, rather than their actual runtime instances. This new approach is motivated by the observation that a client of dynamic slicing often needs to access only a small portion of the complete execution trace collected by a regular slicing algorithm and thus tremendous effort is wasted on collecting information not used by the client. The runtime (space and time) overhead can be significantly reduced if the slicing algorithm is client aware, that is, it understands what information would be needed by its client and records only such information during the execution. Abstract dynamic slicing makes this possible by asking the analysis developer to provide an abstraction that specifies this knowledge.


(2) Improved performance debugging and testing

Performance problems in a large-scale application are extremely difficult to find. Traditional performance test oracles such as time/memory checks are coarse-grained and subjective; as a result, performance bugs often escape to production runs, hurting software reliability and user experience. We are in the process of developing a general technique, called PerfBlower, that can amplify the effects of a class of performance problems whose symptoms can be described by logical statements over a history of heap updates as well as provide precise diagnostic information. Amplification serves as an automated test oracle because it increases memory consumption significantly for tests that trigger performance problems while having a very small impact on bug-free runs. As a result, developers can easily divide tests into successful and failing runs, and focus their effort on failing tests. Please read our ECOOP'15 paper for details.


Caching/resuing opportunities can often be found in large-scale applications. A big source of run-time performance problems in large-scale, object-oriented applications is the frequent creation of data structures whose lifetimes are disjoint, and whose shapes and data content are always the same. Constructing these data structures and computing the same data values many times is expensive; significant performance improvements can be achieved by reusing their instances, shapes, and/or data values rather than reconstructing them. We first classify caching/reusing opportunities into three categories: instance reusability, shape reusability, and data reusability [OOPSLA12]. We next develop scalable runtime techniques that can quickly detect these opportunities by exploiting cooperative compiler and runtime system support. For example, work from [OOPSLA12] is a technique that piggybacks on GC to find reuse opportunities while Cachetor [FSE13] relies on heavyweight dependence profiling to understand if data values are cacheable.


(3) Adaptive selection of algorithms and data structures

An important source of runtime bloat is the inefficient use of container implementations. Standard libraries of object-oriented languages such as Java and C# contain collection frameworks that provide with users, for each abstract data type (such as List), many different implementations (such as ArrayList and LinkedList), each of which features a different design choice suitable for a specific execution scenario. However, in real-world development, choosing the most appropriate container implementation is challenging. As a result, developers tend to keep using the implementations that are most general or well-known (e.g., HashSet for Set), regardless of whether or not they fit the usage context. We develop a novel container optimization technique, called CoCo, that is able to (1) determine at run time, for each container instance (e.g., a LinkedList object) used in the program, whether or not there exists another container implementation (e.g., ArrayList) that is more suitable for the execution; and (2) automatically and safely switch to this new container implementation (e.g., replace the old LinkedList object with a new ArrayList object online) for increased efficiency.While there exists work (such as Chameleon and Brainy) that could identify Java collection inefficiencies and report them to users for offline inspection, none of these techniques can change implementations online. Details about CoCo can found in the ECOOP'13 paper. In collaboration with the information system group, we are currently developing techniques that can automatically select table joining algorithms for message-based Big Data systems (such as graph processing systems). Details of this project will be reported later.


(4) Static and dynamic detection of Java memory leaks

In managed languages such as Java and C#, developers do not need to worry about memory correctness issues such as dangling pointers and double free errors. However, it remains challenging to avoid leaks. A memory leak in a managed language is caused by keeping unnecessary references to objects that are no longer used. These objects cannot be reclaimed by the garbage collector (GC), often leading to severe performance degradation and even program crashes. We have developed both static and dynamic techniques for memory leak detection. In particular, we propose LeakChaser [PLDI11], a specification-based leak detector, that exploits user insight (expressed in the form of liveness assertions) to narrow down causes of memory leaks. Another attractive direction is to perform static leak detection because it does not rely on any leak-triggering inputs, allowing compile-time tools to find leaks before software is released. A long-standing issue that prevents practical static memory leak detection for Java is that it can be very expensive to statically determine object liveness in large applications. We present a practical static leak detection technique, called LeakChecker [CGO14] that bypasses this problem by considering a common leak pattern. In many cases severe leaks occur in loops where, in each iteration, some objects created by the iteration are unnecessarily referenced by objects external to the loop. These unnecessary references are never used in later loop iterations. Based on this insight, we shift our focus from computing liveness, which is very difficult to achieve precisely and efficiently for large programs, to the easier goal of identifying objects that flow out of a loop but never flow back in.



o   PerfBlower: Quickly Detecting Memory-Related Performance Problems via Amplification,

Lu Fang, Liang Dou, and Guoqing (Harry) Xu.

ECOOP'15: European Conference on Object-Oriented Programming.



o   LeakChecker: Practical Static Memory Leak Detection for Managed Languages,

Dacong Yan, Guoqing (Harry) Xu, Shengqian Yang, and Atanas Rountev.

CGO'14: International Conference on Code Generation and Optimization.



o   Scalable Runtime Bloat Detection Using Abstract Dynamic Slicing,

Guoqing (Harry) Xu, Nick Mitchell, Matthew Arnold, Atanas Rountev, Edith Schonberg, and Gary Sevitsky.

TOSEM'14, ACM Transactions on Software Engineering and Methodology.


o   Resurrector: A Tunable Object Lifetime Profiling Technique for Optimizing Real-World Programs,

Guoqing (Harry) Xu.

OOPSLA'13, ACM SIGPLAN Conference on Object-Oriented Programming Systems, Language, and Applications.



o   Cachetor: Detecting Cacheable Data to Remove Bloat,

Khanh Nguyen and Guoqing (Harry) Xu.

FSE'13, ACM SIGSOFT Symposium on the Foundations of Software Engineering.



o   CoCo: Sound and Adaptive Replacement of Java Collections,

Guoqing (Harry) Xu.

ECOOP'13, European Conference on Object-Oriented Programming.



o   Finding Reusable Data Structures,

Guoqing (Harry) Xu.

OOPSLA'12, ACM SIGPLAN Conference on Object-Oriented Programming Systems, Language, and Applications.



o   Static Detection of Loop-Invariant Data Structures,

Guoqing (Harry) Xu, Dacong Yan, and Atanas Rountev.

ECOOP'12, European Conference on Object-Oriented Programming.



o   LeakChaser: Helping Programmers Narrow Down Causes of Memory Leaks,

Guoqing (Harry) Xu, Michael D. Bond, Feng Qin, and Atanas Rountev,

PLDI'11, ACM SIGPLAN Conference on Programming Language Design and Implementation



o   Finding Low-Utility Data Structures,

Guoqing (Harry) Xu, Nick Mitchell, Matthew Arnold, Atanas Rountev, Gary Sevitsky, and Edith Schonberg,

PLDI'10, ACM SIGPLAN Conference on Programming Language Design and Implementation



o   Detecting Inefficiently-Used Containers to Avoid Bloat,

Guoqing (Harry) Xu and Atanas Rountev,

PLDI'10, ACM SIGPLAN Conference on Programming Language Design and Implementation



o   Go with the Flow: Profiling Copies To Find Runtime Bloat,

Guoqing (Harry) Xu, Matthew Arnold, Nick Mitchell, Atanas Rountev, and Gary Sevitsky,

PLDI'09, ACM SIGPLAN Conference on Programming Language Design and Implementation





o   Lu Fang

o   Khanh Nguyen

o   Harry Xu



o   PerfBlower, a performance problem amplification tool

o   LeakChaser, a specification-based memory leak detector for Java

o   Resurrector: a tunable object lifetime profiling tool based on Jikes RVM




This research is funded in part by NSF under grants CNS-1321179, CCF-140982, and CNS-1613023, and by ONR under grants N00014-14-1-0549 and N00014-16-1-2913.

main page