Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2002-04-03
2004-04-27
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06728738
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of computer science. More particularly, the present invention relates to determining the lifetime of objects in a garbage-collected system.
BACKGROUND OF THE INVENTION
In computer science, garbage collection refers to the recovery of pooled computer storage that is being used by a program when that program no longer needs the storage. The garbage collection routine searches memory for data that are no longer active in order to reclaim the space. This frees the storage for use by other programs (or processes within a program). It also ensures that a program using increasing amounts of pooled storage does not reach a quota.
Garbage collection routines are typically encoded when a program is created. In some cases, the routines may even be embedded into hardware or flash memory. Thus, it is increasingly important to verify that the most efficient and accurate garbage collection routines are found before they are implemented, as modification after implementation may be difficult or impossible. Since different programs have different optimal garbage collection routines, it is important to test garbage collection techniques on specific programs before implementation.
Performance analysis of the garbage collection technique during creation or fine-tuning allows the developer to test the efficiency and accuracy of the technique. Typically, the lifetime of the objects is measured by forcing a complete garbage collection after each mutation of the object graph.
FIG. 1
is a diagram illustrating an example of an object graph. Roots
100
,
102
may point to objects
104
,
106
. Each time the object graph changes, there is the potential that one or more of the objects may “die”. An object is considered dead if it is no longer reachable from a root. Forcing a garbage collection after each mutation fully updates the system, thus information on when an object dies can easily be recorded.
Additionally, it is often useful to have precise lifetime information in order to analyze the program itself, such as by providing a histogram of the lifetimes of various objects within the program.
However, measuring the lifetime of each object in this manner is fairly processor-intensive. The time it takes to run a garbage collection grows in proportion to the size of the object graph. In order to avoid this overhead, it is typical to only force a garbage collection periodically, for example after every thousand mutations. However, there is significant loss in precision in the lifetime analysis when this periodic measurement is undertaken.
What is needed is a solution for effectively and efficiently computing precise object lifetimes.
BRIEF DESCRIPTION OF THE INVENTION
The analysis of the lifetime of objects in a garbage-collected system may be accomplished quickly and effectively using reference counts and cyclic garbage analysis. A reference count is maintained for each of the objects to indicate the number of incoming pointers. Each time the graph structure is altered, the reference counts are updated. Timestamps are recorded each time the reference count for objects change. If a reference count goes to zero, the corresponding object may be indicated as dead. A garbage collection need only be run once (perhaps at the end), and after it is run the system may indicate which objects are cyclic garbage. The timestamps for objects which are cyclic garbage are then reviewed in reverse chronological order. For each timestamp found, the corresponding object and any object reachable from the corresponding object are indicated as dead. These objects are then removed from the set of cyclic garbage.
REFERENCES:
patent: 4775932 (1988-10-01), Oxley et al.
patent: 5446901 (1995-08-01), Owicki et al.
patent: 5968136 (1999-10-01), Saulpaugh et al.
patent: 6094664 (2000-07-01), Ungar
patent: 2002/0073103 (2002-06-01), Bottomley et al.
patent: 2003/0084266 (2003-05-01), Knippel et al.
patent: 2003/0105777 (2003-06-01), Seidl et al.
Hertz, M., et al.“Error-Free Garbage Collection Traces: How to Cheat and Not Get Caught”, Department of Computer Science, University of Massachusetts, Amherst, MA 01003 {hertz,steveb,moss} @cs.umass.edu, 14 pages.
Cunei Antonio
Wolczko Mario
Hanish Marc S.
Mizrahi Diane D.
Sun Microsystems Inc.
Thelen Reid & Priest LLP
LandOfFree
Fast lifetime analysis of objects in a garbage-collected system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast lifetime analysis of objects in a garbage-collected system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast lifetime analysis of objects in a garbage-collected system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3263360