Fast lifetime analysis of objects in a garbage collected system
View Patent ↗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.
1. 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 one or more of the objects, said reference count indicating the number of incoming pointers to each object;
recording a timestamp for an object when said reference count for said object changes;
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; and
indicating that any object reachable from said object corresponding to said timestamp is dead.
2. The method of claim 1 , further including executing a garbage collection, said garbage collection indicating one or more objects which are cyclic garbage.
3. The method of claim 2 , wherein said executing includes detecting objects which are cyclic garbage by invoking a tracing collector.
4. The method of claim 3 , wherein said tracing collector is a mark-sweep collector.
5. The method of claim 1 , wherein said timestamp is a counter which is incremented on a pointer store.
6. The method of claim 1 , wherein the lifetime of an object is the period between the time it is created and the time it dies.
7. The method of claim 6 , wherein the time an object dies can be traced to the timestamp of when it was indicated the object was dead.
8. The method of claim 1 , wherein each time a change is made to the graph structure, a record is generated, one field in said record being said timestamp.
9. The method of claim 1 , further including repeating said reviewing each time a garbage collection is executed.
10. 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 when 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; and
indicating that any object reachable from said object corresponding to said timestamp is dead.
11. The method of claim 10 , wherein said timestamp is a counter which is incremented on every pointer deletion.
12. The method of claim 10 , wherein the lifetime of an object is the period between the time it is created and the time it dies.
13. The method of claim 12 , wherein the time an object dies can be traced to the timestamp of when it was indicated the object was dead.
14. The method of claim 10 , wherein each time a change is made to the graph structure, a record is generated, one field in said record being said timestamp.
15. The method of claim 10 , further including repeating said reviewing each time a garbage collection is executed.
16. The method of claim 10 , wherein said executing includes detecting objects which are cyclic garbage by invoking a tracing collector.
17. The method of claim 16 , wherein said tracing collector is a mark-sweep collector.
18. 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 one or more of the objects, said reference count indicating the number of incoming pointers to each object;
means for recording a timestamp for an object when said reference count for said object changes;
means for 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; and
indicating that any object reachable from said object corresponding to said timestamp is dead.
19. The apparatus of claim 18 , further including means for executing a garbage collection, said garbage collection indicating one or more objects which are cyclic garbage.
20. The apparatus of claim 19 , wherein said executing includes detecting objects which are cyclic garbage by invoking a tracing collector.
21. The apparatus of claim 20 , wherein said tracing collector is a mark-sweep collector.
22. The apparatus of claim 18 , wherein said timestamp is a counter which is incremented on a pointer store.
23. The apparatus of claim 18 , wherein the lifetime of an object is the period between the time it is created and the time it dies.
24. The apparatus of claim 23 , wherein the time an object dies can be traced to the timestamp of when it was indicated the object was dead.
25. The apparatus of claim 18 , wherein each time a change is made to the graph structure, a record is generated, one field in said record being said timestamp.
26. The apparatus of claim 18 , further including means for repeating said reviewing each time a garbage collection is executed.
27. 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 when 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:
indicating that the object corresponding to said timestamp is dead; and
indicating that any object reachable from said object corresponding to said timestamp is dead.
28. The apparatus of claim 27 , wherein said timestamp is a counter which is incremented on every pointer deletion.
29. The apparatus of claim 27 , wherein the lifetime of an object is the period between the time it is created and the time it dies.
30. The apparatus of claim 29 , wherein the time an object dies can be traced to the timestamp of when it was indicated the object was dead.
31. The apparatus of claim 27 , wherein each time a change is made to the graph structure, a record is generated, one field in said record being said timestamp.
32. The apparatus of claim 27 , further including means for repeating said reviewing each time a garbage collection is executed.
33. The apparatus of claim 27 , wherein said means for executing includes means for detecting objects which are cyclic garbage by invoking a tracing collector.
34. The apparatus of claim 33 , wherein said tracing collector is a mark-sweep collector.
35. 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 one or more of the objects, said reference count indicating the number of incoming pointers to each object;
recording a timestamp for an object when said reference count for said object changes;
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; and
indicating that any object reachable from said object corresponding to said timestamp is dead.
36. 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 when said reference count for said object is decremented;
executing a garbage collection, said garbage collection indicating one or more objects which are cyclic
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; and
indicating that any object reachable from said object corresponding to said timestamp is dead.