Data structure path profiling

• US 7,926,043 B2
• Filed: 06/20/2006
• Issued: 04/12/2011
• Est. Priority Date: 06/20/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Vaswani, Kapil, Chilimbi, Trishul
• Primary Examiner(s): Dam; Tuan Q
• Assistant Examiner(s): Wei; Zheng
• Application Number:
  US11/425,354
• Publication Number:
  US 20080005208A1
• Time in Patent Office: 1,757 Days
• Field of Search: None
• US Class Current: 717/130
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 2201/865 Monitoring of software

Abstract

The described technology provides data structure path profiling. An instrumented version of a program is created that calls a profiler runtime when pointer based data structures are allocated or accessed via pointers. A model of the heap is created and nodes in the model data structures are assigned unique identifiers. Paths traversed through the model data structures are assigned unique identifiers. The paths are counted in order to identify paths through the data structure model that are traversed frequently. The model is useful for providing information about high frequency data paths to the program developer and for various optimization purposes, such as prefetching and or increasing data locality during garbage collection.

Claims

1. A method for profiling computer programs comprising:

receiving a program binary;

creating a modified version of the program binary comprising instrumenting memory allocator instructions and heap pointer instructions with runtime call instructions to a runtime profiler;

executing the modified version comprising executing the runtime call instructions; and

responsive to receiving the runtime call instructions at the runtime profiler, creating a heap model comprising,

assigning identifiers to data objects, wherein assigning identifiers to data objects comprises assigning prime numbers to data objects,

associating data objects with data structure instances,

assigning identifiers to data paths traversed through data objects, wherein assigning identifiers to data paths traversed through data objects comprises determining a product of prime numbers assigned to data objects on the data path, and

counting a number of times identified data paths are traversed.

2. The method of claim 1 wherein assigning identifiers to data paths comprises assigning the product of prime numbers as an identifier of the data path.

3. The method of claim 1 wherein creating a heap model further comprises determining that a pointer dereference from a first data object at one memory allocation site dereferences a second data object at another allocation site, and indicating in the heap model, that the first and second data objects are part of a same data structure instance.

4. The method of claim 1 wherein creating a heap model further comprises determining that a next data object in a path would create a cycle, and responsive to the determination creating a new data path starting with the next data object.

5. The method of claim 1 wherein the runtime profiler provides a profile output comprising plural data paths through plural data structures.

6. The method of claim 5 further comprising displaying at least a portion of the profile output.

7. The method of claim 5 further comprising:

from information in the profile output, identifying a frequently executed data path;

creating program logic that,

identifies leading data objects in the frequently executed data path, and prefetches the remaining data objects in the frequently executed data path;

instrumenting the program binary with the created program logic; and

executing the instrumented program binary comprising prefetching the remaining objects in the frequently executed data path.

8. The method of claim 5 further comprising:

from information in the profile output, identifying a frequently executed data path; and

executing program logic that rearranges a heap to increase spatial locality for data objects in the frequently executed data path.

9. The method of claim 1 wherein:

assigning identifiers to data objects comprises assigning identifiers to the data objects on the heap of the executing modified version of the program;

associating data objects with data structure instances comprises associating the data objects on the heap of the executing modified version of the program with data structure instances based on pointers that determine links between the data objects on the heap that comprise the data structure instances;

assigning identifiers to data paths traversed through data objects comprises assigning identifiers to data paths comprising acyclic sequences of references to the data objects on the heap associated to the data structure instances; and

counting the number of times identified data paths are traversed comprises counting the number of times the identified data paths through the data objects on the heap, which are associated with the data structure instances, are traversed during the execution of the executing modified version of the program.

10. A computer system providing data structure path profiling, the system comprising:

a central processing unit coupled to memory via a bus;

in memory, software comprising;

a program binary;

an instrumenting component for instrumenting the program binary to make calls to a profiler runtime component;

the profiler runtime component for building a heap model responsive to receiving calls from the instrumented program binary; and

the built heap model comprising;

data objects assigned prime numbers;

data objects at different memory allocation sites on the heap associated to data structure instances via pointers that determine links between the data objects, wherein the data structure instances comprise the data objects associated to the data structure instances;

uniquely identified paths through the data structure instances, wherein the uniquely identified paths comprise acyclic sequences of references to the data objects associated to the data structure instances, and further comprise unique identifiers comprising products of prime numbers assigned to the data objects on the uniquely identified paths.

11. The computer system of claim 10 wherein the in memory software further comprises a data dynamic prefetch component that identifies leading data objects in a uniquely identified data path, and prefetches the remaining data objects in the uniquely identified data path.

12. The computer system of claim 10 wherein the in memory software further comprises a heap component that rearranges a heap to increase spatial locality for data objects in the uniquely identified data path.

13. A computer readable storage medium comprising computer executable instructions for performing a method comprising:

receiving a program binary;

creating a modified version of the program binary comprising instrumenting memory allocator instructions and heap pointer instructions with call instructions to a runtime profiler;

executing the modified version comprising executing the runtime call instructions; and

responsive to receiving the runtime call instructions at the runtime profiler, creating a heap model comprising;

assigning identifiers to data objects;

associating data objects with data structure instances, wherein creating the heap model further comprises determining that a pointer dereference from a first data object at one memory allocation site dereferences a second data object at another allocation site, and indicating in the heap model, that a same data structure instance comprises the first and second data objects;

assigning identifiers to data paths traversed through data objects; and

counting the number of times identified data paths are traversed.

14. The computer readable storage medium of claim 13 wherein the computer executable instructions for assigning identifiers to data objects includes assigning prime numbers to data objects.

15. The computer readable storage medium of claim 13 wherein the computer executable instructions for assigning identifiers to data paths comprises determining a product of prime numbers assigned to data objects on the data path, and assigning the product of prime numbers as an identifier of the data path.

16. The computer readable storage medium of claim 13 wherein the computer executable instructions for assigning identifiers to data paths comprises hashing on heap addresses of data objects along a path.

17. The computer readable storage medium of claim 13 wherein the computer executable instructions for assigning identifiers to data paths comprises determining a sum of the data object'"'"'s identifiers along the path.

18. The computer readable storage medium of claim 13 wherein identifiers assigned to data objects comprise an identified object'"'"'s heap address, and identifiers of data paths comprise outputs of a cyclic redundancy check hash using the identifiers of data objects along a path as inputs to the cyclic redundancy check hash.

19. The computer readable storage medium of claim 13 wherein identifiers assigned to data objects comprise a hash output using a data object'"'"'s heap address as input to the hash, and identifiers of data paths comprise a sum of the data object identifiers along a path.

20. The computer readable storage medium of claim 13 wherein identifiers assigned to data objects comprise a hash output using a data object'"'"'s heap address as input to the hash, and identifiers of data paths comprise an exclusive OR of data object identifiers along a path.