DATA STRUCTURE PATH PROFILING

• US 20080005208A1
• Filed: 06/20/2006
• Published: 01/03/2008
• Est. Priority Date: 06/20/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chilimbi, Trishul, Vaswani, Kapil
• Granted Patent: US 7,926,043 B2
• Time in Patent Office: Days
• US Class Current: 707/206
• 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 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,

assigning identifiers to data paths traversed through data objects, and

counting the number of times identified data paths are traversed.

2. The method of claim 1 wherein assigning identifiers to data objects comprises assigning prime numbers to data objects.

3. The method of claim 2 wherein 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.

4. The method of claim 1 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.

5. The method of claim 1 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.

6. The method of claim 1 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.

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

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

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

10. The method of claim 9 further comprising displaying at least a portion of the profile output.

11. The method of claim 9 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.

12. The method of claim 9 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.

13. 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 associated to data structure instances via pointers,

uniquely identified paths through data structures, the uniquely identified paths comprising a product of prime numbers assigned to the data objects on the path.

14. The computer system of claim 13 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.

15. The computer system of claim 13 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.

16. A computer readable 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,

assigning identifiers to data paths traversed through data objects, and

counting the number of times identified data paths are traversed.

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

18. The computer readable medium of claim 16 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.

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

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