Profile-driven data layout optimization

• US 7,013,459 B2
• Filed: 11/12/2004
• Issued: 03/14/2006
• Est. Priority Date: 04/04/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Beckman, Brian C., Kuch, Gerald Dwayne, Zander, Jason L.
• Primary Examiner(s): Dam, Tuan
• Assistant Examiner(s): Nahar, Qamrun
• Application Number:
  US10/987,408
• Publication Number:
  US 20050172278A1
• Time in Patent Office: 487 Days
• Field of Search: 717/158, 717/151, 711/165
• US Class Current: 717/158
• CPC Class Codes: G06F 9/445 Program loading or initiating bootstrapping G06F9/4401; security arrangements for program loading or initiating G06F21/57
• CPC Class Codes: G06F 9/44557 Code layout in executable memory
• CPC Class Codes: G06F 9/4488 Object-oriented

Abstract

Data layout optimization arranges data members within memory to enhance software performance. Profiling data is consulted to determine how to group data members for an object class into groups. One technique groups the data members based on how frequently the data members are referenced in memory. Another technique groups the data members based on their affinities for one another in time as determined by observing when references to the data members take place. A variety of options when collecting the profiling data and grouping the data members is supported. The data member grouping is recorded in metadata associated with a definition of the object class. At runtime, a class loader places the data members of an object in memory according to the metadata. Data members of different groups can be placed in separately-loadable units of memory in the memory system. Subsequently, when the data members are referenced in memory, more frequently referenced data members, including those that tend to be referenced at times close to each other, reside at neighboring locations in the memory system.

Claims

1. One or more computer-readable media having computer-executable instructions for performing a method of arranging a plurality of data members of an object in a memory system, the method comprising:

identifying more frequently referenced data members out of the plurality of data members of the object by consulting profiling data for the object;

responsive to said identifying the more frequently referenced data members out of the plurality of data members of the object, grouping the more frequently referenced data members out of the plurality of data members of the object together into a group of more frequently referenced data members; and

responsive to said grouping the more frequently referenced data members into a group, assigning the data members from the group of more frequently referenced data members neighboring locations within the memory system.

2. The one or more computer-readable media of claim 1 wherein the memory system is a virtual memory system and the assigning assigns data members from the group of data members neighboring locations within the memory system by assigning data member from the group of data members a set of contiguous addresses in the virtual memory system.

3. The one or more computer-readable media of claim 1 wherein said identifying more frequently referenced data members out of the plurality of data members of the object by consulting profiling data for the object comprises:

ordering the data members according the number of memory references made during profiling of the object.

4. The one or more computer-readable media of claim 1 wherein said identifying more frequently referenced data members out of the plurality of data members of the object by consulting profiling data for the object comprises:

ordering the data members according to affinity between the data members.

5. The one or more computer-readable media of claim 1 wherein said grouping the more frequently referenced data members out of the plurality of data members of the object together into a group of more frequently referenced data members comprises:

computing an affinity matrix for the data members;

transforming the affinity matrix into a cost matrix representing a graph of the data members;

constructing a minimum-cost spanning tree for the graph; and

traversing the minimum-cost spanning tree to determine members of the group.

6. The one or more computer-readable media of claim 1, the method further comprising:

generating the profiling data by counting how many memory references were made to data members of the object during successive method calls.

7. The one or more computer-readable media of claim 1, the method further comprising:

generating the profiling data by recording how many memory references were made to data members of the object during successive time periods.

8. The one or more computer-readable media of claim 1, the method further comprising generating the profiling data in a database by a method comprising:

maintaining counters indicative of how many memory references were made to data members of the object during successive observations;

adding the counters to an overall counter; and

writing a record to the database whenever the overall counter is likely to overflow based on an extrapolated forecast.

9. The one or more computer-readable media of claim 1, the method further comprising:

decorating a class definition of the object with metadata indicating a plurality of non-intersecting groups into which the data members have been placed.

10. The one or more computer-readable media of claim 1 wherein the neighboring locations within the memory system are within a unit of the memory system separately loadable from other units of the memory system.

11. The one or more computer-readable media of claim 10 wherein the unit of the memory system is a page separately loadable into primary memory.

12. The one or more computer-readable media of claim 1, the method further comprising:

identifying less frequently referenced data members out of the plurality of data members of the object by consulting the profiling data for the object;

responsive to said identifying the less frequently referenced data members out of the plurality of data members of the object, grouping the less frequently referenced data members out of the plurality of data members of the object together into a group of less frequently referenced data members; and

responsive to said grouping the less frequently referenced data members into a group, assigning the data members from the group of less frequently referenced data members at least one location separately-loadable from the locations of the more frequently referenced data members within the memory system.

13. The one or more computer-readable media of claim 12 wherein

the memory system is a virtual memory system having a primary memory and a secondary memory;

the virtual memory system comprises memory units separately-loadable into the primary memory;

said assigning the data members from the group of more frequently referenced data members neighboring locations within the memory system comprises assigning the more frequently referenced data members locations within a first set of one or more memory units in the virtual memory system; and

said grouping the less frequently referenced data members out of the plurality of data members of the object together into a group of more frequently referenced data members comprises assigning the less frequently referenced data members locations within a second set of one or more memory units in the virtual memory system; and

the intersection of the first set of memory units and the second set of memory units is a null set.

14. The one or more computer-readable media of claim 13 wherein the memory units are memory pages.

15. The one or more computer-readable media of claim 13 wherein the memory units are of variable size.

16. One or more computer-readable media having computer-executable instructions for performing a method for optimizing the data layout of software comprising a set of object class definitions, the method comprising:

instrumenting the software to generate profile data indicating how frequently data members of the object class definitions are referenced in memory;

grouping the data members of the object class definitions into groups according to how frequently the data members of the object class definitions are referenced in memory, wherein the groups comprise a more frequently referenced group and a less frequently referenced group;

associating metadata indicative of the groups with the set of object class definitions; and

at runtime, consulting the metadata indicative of the groups to determine how to arrange the data members within memory, placing the data members in the more frequently referenced group in a first unit of memory and the data members in the less frequently referenced group in a second unit of memory separately loadable from the first unit of memory into primary memory.

17. The one or more computer-readable media of claim 16, the method further comprising:

declaratively specifying in the software that a specified object class definition is not to be optimized; and

during said grouping, inhibiting grouping of data members of the specified object class definition.

18. The one or more computer-readable media of claim 16, the method further comprising:

at runtime, loading data members in the first group into primary memory; and

inhibiting loading data members in the second group into primary memory.

19. One or more computer-readable media having computer-executable instructions for performing a method of monitoring affinity among a plurality of data members of an object class in a memory system, the method comprising:

constructing a table indicating how many times data members of the object were referenced during each of a plurality of time periods during profiling;

computing an affinity matrix for the object class with a dot product operation, wherein the affinity matrix indicates an affinity between a first data member of the object and a second data member of the object; and

displaying the affinity matrix as a graph for consideration by a user.

20. The one or more computer-readable media of claim 19, the method further comprising:

generating a database record by tracking how many time data members of the object are referenced during successive time periods by setting an expiring timer; and

writing the database record to a database of profiling data upon expiration of the timer.