Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-07-31
2003-10-21
Rones, Charles (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06636866
ABSTRACT:
BACKGROUND OF THE INVENTION
Field of the Invention
The present invention relates to the implementation of a computer programming language, and, in particular, the implementation of an object-oriented programming language.
Description of the Related Art
Object-oriented programming languages use classes to describe objects created by the program during execution. Two examples of object-oriented programming languages are Java and C++.
In Java, a class consists of a set of data members. For example, a Java class declaration is in the form:
class X {
int a;
int b;
int c;
int d;
};
Class X has four data members, named a, b, c, and d. The execution of a program that contains this class declaration may create a number of instances of this class, also referred to as objects of type X.
The computer executing the program will allocate memory for each object. Eventually, the memory allocated for the created objects may be reclaimed through the “garbage collection process,” when the objects are no longer used by the program. The garbage collection process clears the objects from memory whereby the once allocated memory is now available for use. In other languages without garbage collection, such as C++, unnecessary objects must be explicitly freed or deallocated.
An important component of implementing a computer programming language is selecting a suitable representation of objects, which includes determining how much memory must be allocated for an object of a class and determining where every member of a class will be located. In a straight forward implementation of the language, every object of type X that is created will have the four data members, namely a, b, c, and d. If an integer member is 4 bytes long, for example, an object of type X will use 16 bytes for the data members.
In addition, the object may require more bytes for other purposes. One other such purpose may be for storing a pointer to the description of the class to which it belongs.
For simplicity, defined herein, the size of an object refers to the size (i.e. bytes of memory) required for the data members of the objects.
In conventional object-oriented programming languages, a specific amount of memory (i.e. number of byes) is allocated for each object based on the number of members in each class. The specific amount of memory is allocated regardless of whether the various members which comprise a class are ever used. For example, if a specific member of a class is never used, the program will still allocate the same amount of memory as if the member were used. Consequently, memory is wasted (i.e. not available for use) by the allocation (i.e reservation) of memory for the member never used.
Certain optimized implementations, such as the ones described by Tip et al. (Frank Tip, Jong-Deok Choi, John Field, G. Ramalingam, Slicing class hierarchies in C++, in Proceedings of the Eleventh Annual Conference on Object Oriented Programming Systems, Languages, and Applications, 1996, pp. 179-197), as well as Tip and Sweeney (Frank Tip and Peter Sweeney, Class hierarchy specialization, in Proceedings of the Twelfth Annual Conference on Object Oriented Programming Systems, Languages, and Applications, 1997, pp. 271-285), might eliminate some unused data members from the representation.
For example, if an analysis of the program indicates that the data member “c” of objects of type X is never used, then data member “c” can be eliminated from all objects of type X. Consequently, removing member “c” can reduce the size of an object of type X from 16 to 12 bytes. The method described by Tip et al. performs this kind of optimization.
However, if the data member “c” of some objects of type X is used, and the data member “c” of other objects of type X is unused, Tip and Sweeney generate two specialized versions of class X. One first specialized version of class X is for the first collection of objects of type X for which the data member “c” is used. A second specialized version of type x is for a second collection of objects of type X for which the data member “c” is unused. The data member “c” can then be eliminated from the representation of members of the second collection of objects.
While these two methods described by Tip et al. and Tip and Sweeney address the situation when a member of an object is never used, these methods fail to optimize a situation in which various members are used only for part of the lifetime of an object.
For example, often a program has multiple phases Data members “a” and “b” of objects of type X might be used only during phase
1
of the program, while data members “c” and “d” might be used only during phase
2
of the program. The earlier optimizations are not applicable in such a situation because all four members of objects of type X are used. Consequently, no member can be eliminated from the representation of objects of type X.
Thus, the conventional methods fail to provide an optimization method of implementation of objects exploiting the fact that the members of an object are not all in use through out the lifetime of the object.
SUMMARY OF THE INVENTION
It is, therefore, an object of the present invention to provide a method and system for optimizing the implementation of objects in which various members representing the object are not all in use throughout the lifetime of the object.
Optimization of the implementation of objects, according to one embodiment, includes statically identifying various collections of objects that may be created during program execution and identifying the lifetimes of the various members of objects belonging to these collections. A second step includes using the lifetime information to generate representations of objects belonging to these collections. Memory requirements are optimized by having members which do not have overlapping lifetimes, share the same memory location.
In addition, the present invention optimizes implementation of objects by breaking objects into multiple fragments. In one embodiment, implementation of an object is represented by several different blocks of memory rather than a single contiguous block of memory as is the case when implementing an object using a conventional method. The various blocks contain a subsets of members that represent an object. Each block of memory used to represent an object is an “object fragment.” Blocks of memory may be allocated and freed independent of the other blocks. As a result, the amount of memory required to represent an object may increase or decrease during the lifetime of the object, as the set of members of the object that are alive changes during program execution.
The invention, in one form thereof, is a method for processing an object-oriented program having objects belonging to a plurality of classes. Each of the plurality of classes have a plurality of members. The method includes identifying a lifetime associated with one or more members of said plurality of members and identifying a set of members in one of the plurality of classes such that no two members in the said set of members have overlapping lifetimes. In one further embodiment, each member of the said set of members is located at the same offset within objects belonging to the one class.
The invention, in another form thereof, is a system for processing an object-oriented program having objects belonging to a plurality of classes. Each of the plurality of classes have a plurality of members. The system includes means for identifying a lifetime associated with one or more members of the plurality of members and identifying a set of members in one of said plurality of classes such that no two members in the set of members have overlapping lifetimes In one further embodiment, each member of the set of members is located at the same offset within objects belonging to the one class.
The invention, in another form thereof, is a system for processing an object-oriented program having objects belonging to a plurality of classes. Each class of the plurality of classes have a plurality of members. The sy
International Business Machines - Corporation
Ludwin, Esq. Richard M.
McGinn & Gibb PLLC
Rones Charles
Wu Yicun
LandOfFree
System and method for object representation in an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for object representation in an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for object representation in an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3159581