Estimation of object lifetime using static analysis

Details Estimation of object lifetime using static analysis Estimation of object lifetime using static analysis

2000-12-28

2002-09-24

Mizrahi, Diane D. (Department: 2175)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

06457023

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to computational methods. More particularly this invention relates to the static analysis of the lifetimes of heap-allocated objects in functioning computer programs and the application of this analysis to generational garbage collection of heap memory.
2. Description of the Related Art
Current generational schemes of garbage collection allocate newly created objects on the heap to the youngest generation. If such an object survives a certain number of collections of that generation, it is promoted to an older generation. Older generations are collected less often. Promotion overhead continues to be paid until the object is either collected or it resides in the oldest generation. Generational garbage collection can be combined with various collection schemes, e.g., copying collection, mark-sweep collection, and the amount of overhead depends on the specific scheme.
For example, the primary overhead for a copying generational garbage collection, is the repeated copying of the object until it reaches the oldest generation.
In previous work, profiling of information has been proposed to estimate object lifetime. That estimation has then been used dynamically during the course of collection cycles to choose the proper generation in which to allocate the object. This scheme has been shown to indeed avoid the overhead associated with allocating a long-lived object in the youngest generation and then promoting it to an older generation. But this technique has significant drawbacks and incurs considerable runtime overhead. Profiling involves program instrumentation in order to train executions of a program, and further requires collecting and storing the results for later use. Such a process slows down the execution time, sometime by two order of magnitude, and is impractical for large programs. In addition, the results depends on the training input set.
The document
Generational Stack Collection and Profile
-
Driven Pretenuring,
P. Cheng, R. Harper, and P. Lee, PLDI '98 pp. 162-173. proposes to use profiling to find object lifetimes and employ that information in order to improve a copying generational garbage collector. It discloses an average decrease of 30% in generational garbage collection time, through the avoidance of copying of data from generation to generation. It was noted that a few allocation sites consistently produce data that survive many allocations.
Recently the document
A Study of the Allocation Behavior of the SPECjvm
98
Java Benchmarks,
S. Dieckmann, and Urs Holzle, Proceedings of the 13th European Conference on Object-Oriented Programming (ECOOP' 99), Lisbon, June 1999, Springer Verlag, reports that 1%-40% of SPECjvm98 objects are still live after 100 Kbytes, with jess having the lower range and db on the upper end. Even after one megabyte of allocations, 21% of all allocated bytes are still live in javac, 12% in db and 8% in jack. These graphs show a flat age distribution after a drop at about 50 kbytes lasting until the end of the application. The possibility of eliminating expensive copying of large objects makes knowledge of object lifetime especially beneficial.
In other approaches attempts have been made to increase the efficiency of data flow analysis. Data flow analysis computes information about the potential behavior of a program in terms of the definitions and uses of data objects. Such data flow information is important for optimizing compilers, program environments, and understanding tools. It can also be used in a software-testing system or to provide compiler and runtime support for the parallel execution of programs originally written in sequential languages.
Numerous techniques have been successfully developed for data flow analysis of programs written in languages with only static data structures, such as Fortran. However, data flow analysis for programs written in languages with dynamically allocated data structures, such as C, C++, Fortran 90, Java (TM), and LISP, is more challenging because of pointer-induced aliasing, which occurs when two or more pointer expressions refer to the same storage location.
Aliasing occurs when there exists more than one access path to a storage location. An access path is constructed from variables, pointer dereference operators, and structure field selection operators. In C such an expression would include a variable with a possibly empty sequence of the following operators: “*” (dereference), “.” (field selection), and “→” (dereference and field selection). For purposes of pointer alias analysis, two access paths are “must-aliases” at a statement S if they refer to the same storage location in all execution instances of S. Two access paths are “may-aliases” at S if they refer to the same storage location in some execution instances of S.
A number of factors are known to influence the cost and precision of practical pointer alias analysis, including the use of flow sensitivity techniques, the use of context sensitivity, the manner in which aggregate data objects such as arrays and classes are modeled, the modeling of the heap, and the choice of alias representation. It is known that there is no general solution to the problem of pointer alias analysis, and the art has therefore attempted to improve the efficiency of the analysis using a variety of empirical and theoretical techniques and combinations. The document,
Interprocedural Pointer Alias Analysis,
Hind, Michael et al., ACM Transactions on Programming Languages, Vol. 21, No. 4, July 1999, proposes one combined approach to the analysis of pointer aliasing.
Pointer analysis has been found to be useful in understanding potential reachability connections between objects or references to objects. Recently, there has been a fair amount of work in developing algorithms for escape analysis of objects in Java (TM) programs to determine whether objects are local to the methods where they are created. Escape analysis is a static analysis that determines whether the object is still alive after the call to the method or procedure that created the object. The importance of escape analysis can be appreciated with reference to object oriented languages such as C++ and Java (TM), as their implementations often employ a garbage collector to assist in memory management. Java (TM) in particular relies on a garbage collector for heap-allocated objects. However garbage collectors are notoriously slow. Stack allocation of objects is one way to minimize garbage collection. It is an object of escape analysis to determine which objects can be stack allocated. A further use of escape analysis is to determine if an object is accessed only by a single thread during its lifetime in order to avoid unnecessary synchronization operations in a multithreaded or multiprocessor environment. A representative publication dealing with escape analysis is the document Escape Analysis for Object Oriented Languages. Application to Java (TM), Blanchet; B., OOPSLA 99.
The following two papers present various techniques that statically analyze objects in Java programs to determine whether they are local to the methods where they are created. These algorithms suggest various mapping techniques in applying escape analysis to reachability problems.
The document
Escape Analysis for Java,
J. D. Choi, M. Gupta, M. Serrano, V. O. Sreedhar, and S. Midkiff, OOPSLA '99, pp. 1-19. reports that reachability and escape analysis specifies over 70% of all dynamically created objects as objects that may be allocated on the stack in three out of the ten benchmarks.
The document
Removing Unnecessary Synchronization in Java,
J. Bogda, and U. Holzle, OOPSLA '99, pp. 20-34 discloses a static evaluation of escape analysis. The authors determined the percentage of candidate alias sets that were optimized. An ideal analysis, having no loss of precision, would reach 100% for a single threaded application. For the programs in their benchmark suite (compress, db, jack, javac, jess, mpegaudio, mt

Affiliated with

Also associated with

Rating

Estimation of object lifetime using static analysis does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Estimation of object lifetime using static analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Estimation of object lifetime using static analysis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2837205