Fast lifetime analysis of objects in a garbage-collected system

A method for measuring the lifetime of objects in a garbage-collected system, the objects organized in a graph structure, the method including:

• recording a timestamp for an object each time said reference count for said object is decremented;
• executing a garbage collection, said garbage collection indicating one or more objects which are cyclic garbage;
• reviewing in reverse chronological order said timestamps for each of said objects, and for each timestamp found:
• if said object is cyclic garbage:
• indicating that the object corresponding to said timestamp is dead;
• indicating that any object reachable from said object corresponding to said timestamp is dead;
• and
• removing any objects that have been indicated as dead from said objects which are cyclic garbage.

An apparatus for measuring the lifetime of objects in a garbage-collected system, the objects organized in a graph structure, the apparatus including:

• a memory;
• a reference count maintainer coupled to said memory;
• a reference count updater coupled to said reference count maintainer;
• a timestamp recorder coupled to said memory and to said reference count updater;
• a dead object indicator coupled to said reference count updater and to said memory;
• a garbage collector coupled to said memory;
• and
• a reverse chronological order timestamp reviewer coupled to said garbage collector and to said memory, said reverse chronological order timestamp reviewer having a dead timestamp object indicator, a dead reachable object indicator, and a dead object cyclic garbage remover coupled to said dead timestamp object indicator and said dead reachable object indicator.

An apparatus for measuring the lifetime of objects in a garbage-collected system, the objects organized in a graph structure, the apparatus including:

• a memory;
• a timestamp recorder coupled to said memory and to said reference count updater;
• a garbage collector coupled to said memory;
• and
• a reverse chronological order timestamp reviewer coupled to said garbage collector and to said memory, said reverse chronological order timestamp reviewer having a dead timestamp object indicator, a dead reachable object indicator, and a dead object cyclic garbage remover coupled to said dead timestamp object indicator and said dead reachable object indicator.

An apparatus for measuring the lifetime of objects in a garbage-collected system, the objects organized in a graph structure, the apparatus including:

• means for maintaining a reference count for each of the objects, said reference count indicating the number of incoming pointers to each object;
• means for updating said reference counts each time said graph structure is altered;
• means for recording a timestamp for an object each time said reference count for said object changes;
• means for indicating an object is dead when its reference count goes to zero;
• means for reviewing in reverse chronological order said timestamps for each of said objects which are cyclic garbage, and for each timestamp found:
• means for indicating that the object corresponding to said timestamp is dead;
• means for indicating that any object reachable from said object corresponding to said timestamp is dead;
• and
• means for removing any objects that have been indicated as dead from said objects which are cyclic garbage.

An apparatus for measuring the lifetime of objects in a garbage-collected system, the objects organized in a graph structure, the apparatus including:

• means for recording a timestamp for an object each time said reference count for said object is decremented;
• means for executing a garbage collection, said garbage collection indicating one or more objects which are cyclic garbage;
• means for reviewing in reverse chronological order said timestamps for each of said objects, and for each timestamp found:
• if said object is cyclic garbage:
• means for indicating that the object corresponding to said timestamp is dead;
• means for indicating that any object reachable from said object corresponding to said timestamp is dead;
• and
• means for removing any objects that have been indicated as dead from said objects which are cyclic garbage.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for measuring the lifetime of objects in a garbage-collected system, the objects organized in a graph structure, the method including:

• maintaining a reference count for each of the objects, said reference count indicating the number of incoming pointers to each object;
• updating said reference counts each time said graph structure is altered;
• recording a timestamp for an object each time said reference count for said object changes;
• indicating an object is dead when its reference count goes to zero;
• reviewing in reverse chronological order said timestamps for each of said objects which are cyclic garbage, and for each timestamp found:
• indicating that the object corresponding to said timestamp is dead;
• indicating that any object reachable from said object corresponding to said timestamp is dead;
• and
• removing any objects that have been indicated as dead from said objects which are cyclic garbage.

A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method for measuring the lifetime of objects in a garbage-collected system, the objects organized in a graph structure, the method including:

• recording a timestamp for an object each time said reference count for said object is decremented;
• executing a garbage collection, said garbage collection indicating one or more objects which are cyclic garbage;
• reviewing in reverse chronological order said timestamps for each of said objects, and for each timestamp found:
• if said object is cyclic garbage:
• indicating that the object corresponding to said timestamp is dead;
• indicating that any object reachable from said object corresponding to said timestamp is dead;
• and
• removing any objects that have been indicated as dead from said objects which are cyclic garbage.