Fast lifetime analysis of objects in a garbage-collected system

• US 20030191783A1
• Filed: 04/03/2002
• Published: 10/09/2003
• Est. Priority Date: 04/03/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Cunei, Antonio, Wolczko, Mario
• Granted Patent: US 6,728,738 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

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.

Claims

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 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.

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 1, wherein each timestamp is a counter which is incremented on every pointer store.

4. 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.

5. The method of claim 4, wherein the time an object dies can be traced to the timestamp of when it was indicated the object was dead.

6. 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.

7. The method of claim 1, further including repeating said reviewing each time a garbage collection is executed.

8. The method of claim 2, wherein said executing includes detecting objects which are cyclic garbage by invoking a tracing collector.

9. The method of claim 8, wherein said tracing collector is a mark-sweep collector.

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 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.

11. The method of claim 10, wherein each 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:

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.

19. The apparatus of claim 18, wherein said memory includes a counter which is incremented on every pointer store.

20. The apparatus of claim 18, wherein said garbage collector includes a tracing collector.

21. The apparatus of claim 20, wherein said tracing collector is a mark-sweep collector.

22. 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.

23. The apparatus of claim 22, wherein said memory includes a counter which is decremented on every pointer deletion.

24. The apparatus of claim 22, wherein said garbage collector includes a tracing collector.

25. The apparatus of claim 24, wherein said tracing collector is a mark-sweep collector.

26. 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.

27. The apparatus of claim 26, further including means for executing a garbage collection, said garbage collection indicating one or more objects which are cyclic garbage.

28. The apparatus of claim 26, wherein each timestamp is a counter which is incremented on every pointer store.

29. The apparatus of claim 26, 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 26, 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 26, further including means for repeating said reviewing each time a garbage collection is executed.

33. The apparatus of claim 26, 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. 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.

36. The apparatus of claim 35, wherein each timestamp is a counter which is incremented on every pointer store.

37. The apparatus of claim 35, wherein the lifetime of an object is the period between the time it is created and the time it dies.

38. The apparatus of claim 37, wherein the time an object dies can be traced to the timestamp of when it was indicated the object was dead.

39. The apparatus of claim 35, wherein each time a change is made to the graph structure, a record is generated, one field in said record being said timestamp.

40. The apparatus of claim 35, further including means for repeating said reviewing each time a garbage collection is executed.

41. The apparatus of claim 35, wherein said means for executing includes means for detecting objects which are cyclic garbage by invoking a tracing collector.

42. The apparatus of claim 41, wherein said tracing collector is a mark-sweep collector.

43. 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.

44. 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.