Data Placement Optimization Using Data Context Collected During Garbage Collection

• US 20110252199A1
• Filed: 04/09/2010
• Published: 10/13/2011
• Est. Priority Date: 04/09/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation, ServiceNow Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Zhuang, Xiaotong, Serrano, Mauricio J.
• Granted Patent: US 8,621,150 B2
• Time in Patent Office: Days
• US Class Current: 711/118
• CPC Class Codes: G06F 11/3476 Data logging G06F11/14, G06F11/2205 take precedence
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 2201/885 Monitoring specific for caches

Abstract

Mechanisms are provided for data placement optimization during runtime of a computer program. The mechanisms detect cache misses in a cache of the data processing system and collect cache miss information for objects of the computer program. Data context information is generated for an object in an object access sequence of the computer program. The data context information identifies one or more additional objects accessed as part of the object access sequence in association with the object. The cache miss information is correlated with the data context information of the object. Data placement optimization is performed on the object, in the object access sequence, with which the cache miss information is associated. The data placement optimization places connected objects in the object access sequence in close proximity to each other in a memory structure of the data processing system.

Claims

1. A method, in a data processing system, for data placement optimization during runtime of a computer program, comprising:

detecting, by a processor of the data processing system, cache misses in a cache of the data processing system;

collecting, by the processor, cache miss information for objects of the computer program;

generating, by the processor, data context information for an object in an object access sequence of the computer program, wherein the data context information identifies one or more additional objects accessed as part of the object access sequence in association with the object;

correlating, by the processor, the cache miss information with the data context information of the object; and

performing, by the processor, data placement optimization on the object, in the object access sequence, with which the cache miss information is associated, wherein the data placement optimization places connected objects in the object access sequence in close proximity to each other in a memory structure of the data processing system.

2. The method of claim 1, wherein the generation of the data context information is performed during a garbage collection operation of the data processing system.

3. The method of claim 2, wherein the garbage collection operation is one of a mark-and-sweep garbage collection operation or a generational garbage collection operation.

4. The method of claim 2, wherein the data context information for the object is stored in one of an old object in a from-space of the garbage collection operation that corresponds to the object, or a new object in a to-space of the garbage collection operation that corresponds to the object.

5. The method of claim 4, wherein the data context information is stored in an object monitor field of the new object in response to the monitor field of the new object not indicating a lock of the new object, and wherein a least significant bit of the object monitor field is set to indicate that the data context information is stored in the object monitor field.

6. The method of claim 4, wherein the data context information is stored in a field of the old object in response to the monitor field of the new object indicating a lock of the new object, a pointer to the old object is stored in an object monitor field of the new object, and a least significant bit of the object monitor field of the new object is set to indicate that the data context information is stored in the old object pointed to by the pointer in the object monitor field.

7. The method of claim 1, wherein correlating the cache miss information with the data context information of the object comprises:

generating a hierarchical representation of the data context information; and

annotating one or more nodes of the hierarchical representation with cache miss information corresponding to the one or more nodes.

8. The method of claim 7, wherein annotating the one or more nodes of the hierarchical representation comprises storing a cache miss count indicating a number of cache misses occurring in an object corresponding to the node.

9. The method of claim 7, wherein the hierarchical representation is one of a data context graph, a data context tree, or a partial data context tree.

10. The method of claim 7, wherein performing data placement optimization comprises:

identifying a trigger node in the hierarchical representation; and

storing objects in a sub-portion of the hierarchical representation, corresponding to the trigger node, in close proximity to each other in the memory structure, wherein a trigger node is a node of the hierarchical representation having a node miss rate that meets a predetermined criteria, and wherein the node miss rate is a ratio of a number of cache misses caused by an object corresponding to a total number of cache misses.

11. The method of claim 10, wherein if the trigger node corresponds to an array object, storing objects in a sub-portion of the hierarchical representation further comprises:

generating a histogram of cache miss information for elements of the array object; and

performing the storing of objects in the sub-portion of the hierarchical representation in close proximity to each other for objects corresponding to elements of the array object that meet a predetermined criteria, based on the histogram.

12. A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:

detect cache misses in a cache of the computing device;

collect cache miss information for objects of the computer program;

generate data context information for an object in an object access sequence of the computer program, wherein the data context information identifies one or more additional objects accessed as part of the object access sequence in association with the object;

correlate the cache miss information with the data context information of the object; and

perform data placement optimization on the object, in the object access sequence, with which the cache miss information is associated, wherein the data placement optimization places connected objects in the object access sequence in close proximity to each other in a memory structure of the computing device.

13. The computer program product of claim 12, wherein the generation of the data context information is performed during a garbage collection operation of the computing device.

14. The computer program product of claim 13, wherein the garbage collection operation is one of a mark-and-sweep garbage collection operation or a generational garbage collection operation.

15. The computer program product of claim 13, wherein the data context information for the object is stored in one of an old object in a from-space of the garbage collection operation that corresponds to the object, or a new object in a to-space of the garbage collection operation that corresponds to the object.

16. The computer program product of claim 15, wherein the data context information is stored in an object monitor field of the new object in response to the monitor field of the new object not indicating a lock of the new object, and wherein a least significant bit of the object monitor field is set to indicate that the data context information is stored in the object monitor field.

17. The computer program product of claim 15, wherein the data context information is stored in a field of the old object in response to the monitor field of the new object indicating a lock of the new object, a pointer to the old object is stored in an object monitor field of the new object, and a least significant bit of the object monitor field of the new object is set to indicate that the data context information is stored in the old object pointed to by the pointer in the object monitor field.

18. The computer program product of claim 12, wherein the computer readable program causes the computing device to correlate the cache miss information with the data context information of the object by:

generating a hierarchical representation of the data context information; and

annotating one or more nodes of the hierarchical representation with cache miss information corresponding to the one or more nodes.

19. The computer program product of claim 18, wherein the computer readable program causes the computing device to annotate the one or more nodes of the hierarchical representation by storing a cache miss count indicating a number of cache misses occurring in an object corresponding to the node.

20. The computer program product of claim 18, wherein the hierarchical representation is one of a data context graph, a data context tree, or a partial data context tree.

21. The computer program product of claim 18, wherein the computer readable program causes the computing device to perform data placement optimization by:

identifying a trigger node in the hierarchical representation; and

storing objects in a sub-portion of the hierarchical representation, corresponding to the trigger node, in close proximity to each other in the memory structure, wherein a trigger node is a node of the hierarchical representation having a node miss rate that meets a predetermined criteria, and wherein the node miss rate is a ratio of a number of cache misses caused by an object corresponding to a total number of cache misses.

22. The computer program product of claim 21, wherein if the trigger node corresponds to an array object, storing objects in a sub-portion of the hierarchical representation further comprises:

generating a histogram of cache miss information for elements of the array object; and

performing the storing of objects in the sub-portion of the hierarchical representation in close proximity to each other for objects corresponding to elements of the array object that meet a predetermined criteria, based on the histogram.

23. An apparatus, comprising:

a processor; and

a memory coupled to the processor, wherein the memory comprises instructions which, when executed by the processor, cause the processor to;

detect cache misses in a cache of the computing device;

collect cache miss information for objects of the computer program;

generate data context information for an object in an object access sequence of the computer program, wherein the data context information identifies one or more additional objects accessed as part of the object access sequence in association with the object;

correlate the cache miss information with the data context information of the object; and

perform data placement optimization on the object, in the object access sequence, with which the cache miss information is associated, wherein the data placement optimization places connected objects in the object access sequence in close proximity to each other in a memory structure of the computing device.