Data structure path profiling
First Claim
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, andcounting a number of times identified data paths are traversed.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
Specification