Data placement optimization using data context collected during garbage collection

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, and wherein the generation of the data context information is performed during a garbage collection operation of the data processing system;
• 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, based on the correlation of the cache miss information with the data context information of the object, 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 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, and 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.

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, and wherein the generation of the data context information is performed during a garbage collection operation of the computing device;
• 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, based on the correlation of the cache miss information with the data context information of the object, 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,
• 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, 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 it the object monitor field, and 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 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 abject 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, and wherein the generation of the data context information is performed during a garbage collection operation of the computing device;
• 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, based on the correlation of the cache miss information with the data context information of the object, 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, 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, and 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.

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, and wherein the generation of the data context information is performed during a garbage collection operation of the computing device;
• 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, based on the correlation of the cache miss information with the data context information of the object, 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,
• 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, 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, and 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.