Method and system for determining an optimal placement order for code portions within a module

• US 5,752,038 A
• Filed: 07/17/1997
• Issued: 05/12/1998
• Est. Priority Date: 03/16/1994
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Smith, Lee A., Blake, Russ, Baghai, M. Reza
• Primary Examiner(s): Voeltz, Emanuel Todd
• Assistant Examiner(s): CORCORAN, PETER JOSEPH
• Application Number:
  US08/903,323
• Time in Patent Office: 299 Days
• Field of Search: 395/705, 395/707, 395/709
• US Class Current: 717/158
• CPC Class Codes: G06F 11/3414 Workload generation, e.g. scripts, playback
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 2201/885 Monitoring specific for caches
• 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

Abstract

A method and system for determining an optimal placement order for code portions within a module to improve locality of reference and reduce the working set of the module are provided. The optimal placement order for code portions within a module reflects the concurrency of usage for code portions during execution of the module. All code portions which execute within a certain period of time are placed in close proximity to each other within the executable module. When determining the optimal placement order for each code portion, the present invention executes an instrumented version of the module to collect execution data for each code portion, analyzes the execution data to determine the optimal placement order for each code portion, and links the code portions according to the determined optimal placement order. The instrumented version of the module contains instructions that, when executed, cause execution data to be recorded. When the code portions are linked according to the determined optimal placement order, the working set for the module is reduced, thereby lessening page and cache misses and improving overall system performance. To collect execution data, a preferred embodiment of the present invention creates a bit vector for each code portion in the module. Each bit vector contains multiple bits such that each bit represents a unique time interval. Upon each invocation of a code portion within a time interval, the bit vector for the invoked code portion is located and the bit that represents the time interval is set to 1.

Claims

1. In a computer system, a method for ordering code portions that together non-redundantly comprise a single executable module, the method comprising the steps of:

executing the module on the computer system for a period of time;

defining within the period of time during which the module is executed a plurality of time intervals including a first and a second time interval;

during execution of the module, determining which of the code portions are invoked within the first interval and determining which of the code portions are indeed within the second time interval; and

ordering the code portions within the module so that code portions determined to be invoked within the first time interval are placed within the module in close proximity to each other relative to code portions not determined to be invoked within the first time interval and code portions determined to be invoked within the second time interval are placed in close proximity to each other relative to code portions not determined to be invoked during the second time interval.

2. The method according to claim 1 wherein the step of determining which of the code portions are invoked within a first and a second time interval includes the steps of:

creating a bit vector for each code portion, each bit vector containing a first bit corresponding to the first time interval and a second bit corresponding to the second time interval;

upon invocation of a code portion within the first time interval, setting the first bit in the bit vector for the invoked code portion; and

upon invocation of a code portion within the second time interval, setting the second bit in the bit vector for the invoked code portion.

3. The method according to claim 1 wherein the step of determining which of the code portions are invoked during a first and a second time interval includes the steps of:

inserting a call instruction to a library routine within the code portion so that when the code portion is invoked, the library routine is executed in addition to the code portion; and

upon initialization of the library routine, creating a bit vector for each code portion, each bit vector containing a plurality of bits, each of the plurality of bits corresponding to a time interval; and

upon invocation of the library routine by a code portion during a time interval, locating the bit vector for the code portion and setting the bit corresponding to the time interval.

4. In a computer system, a method for ordering code portions that together non-redundantly comprise a module, the method comprising the steps of:

creating a bit vector corresponding to each of the code portions, each bit vector including a plurality of bits, each bit corresponding to a common time interval in every bit vector;

executing the module on the computer system;

during execution of the module on the computer system, upon invocation of one of the code portions within one of the time intervals,

locating the bit vector corresponding to the invoked code portion,

locating the bit within the located bit vector corresponding to the time interval in which the code portion was invoked, and

setting the located bit;

subsequent to execution of the module on the computer system,

determining a placement order for each code portion based upon which bits are set within each bit vector, and

ordering the code portions within the module according to the determined placement order.

5. In a computer system, a method for ordering code portions that together non-redundantly comprise a single executable module to produce an optimized executable version of the module, the method comprising the steps of:

providing an instrumented executable version of the module, the instrumented executable version containing instructions within each code portion that, when executed, will cause execution information regarding the code portion to be recorded, the recorded execution information including when the code portion is invoked;

executing the instrumented executable version of the module to gather the execution information for each code portion;

analyzing the execution information to determine a desired placement order for each code portion, each code portion'"'"'s desired placement order reflecting a desired physical location for the code portion within the module relative to the physical locations of the other code portions, by determining that code portions which are invoked at proximate times have proximate placement orders;

providing an original compiled version; and

linking the original compiled version of the module according to the determined desired placement order for each code portion to produce an optimized executable version of the module.

6. In a computer system, a method for ordering code portions that together non-redundantly comprise a single executable module, the method comprising the steps of:

during compilation of the module, placing a call to a library routine within each code portion;

executing the module on the computer system for a period of time;

defining within the period of time during which the module is executed a plurality of time intervals;

during execution of the module on the computer system,

invoking code portions,

upon invocation of a code portion within a time interval, invoking the library routine,

upon a first invocation of the library routine, invoking an initialization function for the library routine;

upon invocation of the initialization function for the library routine,

creating a bit vector table, the bit vector table including one bit vector corresponding to each code portion, each bit vector including a plurality of bits, each bit of every bit vector corresponding to the same unique time interval during the execution of the module, and clearing each bit in the bit vector table;

upon every invocation of the library routine by a calling code portion during a time interval during the execution of the module,

locating a bit vector corresponding to the code portion within the bit vector table,

locating a bit within the located bit vector corresponding to the time interval, and

setting the located bit;

ceasing execution of the module on the computer system;

subsequent to execution of the module on the computer system,

sorting the bit vectors in the bit vector table,

for each bit vector,

determining whether any bit vectors are equivalent to the bit vector, and

if any bit vectors are identical to the bit vector, replacing the bit vector with a surrogate bit vector and removing the identical bit vectors from the bit vector table;

determining a placement order for each code portion based upon affinity; and

ordering the code portions within the module according to the determined placement order.

7. In a computer system, a method of determining placement order of code portions that together non-redundantly comprise a single executable module in an executable, the method comprising the steps of:

providing a bit vector for each code portion wherein each bit vector includes a plurality of bits and each bit of every bit vector corresponds to the same time interval during the execution of the module;

executing the module on the computer system such that each time one of the code portion executes during one of the time intervals, setting the corresponding bit in the bit vector of the code;

examining the bit vectors to determine a placement position for a first of the code portions in the executable;

calculating property values of the bit vectors for other code portions relative to the bit vector of the first code portion; and

using the calculated property values to determine which of the other code portions is placed next in the placement order of the executable after the first code portion.

8. The method of claim 7 wherein the step of calculating property values of the bit vectors for other code portions relative to the bit vector of the first code portion comprises the step for each of the other code portions, of calculating a logical AND between the bit vector of the first code portion and the bit vector of the other code portion to determine affinity between the code portions.

9. The method of claim 7 wherein the step of calculating property values of the bit vectors for other code portions comprises the step of counting a number of bits that are set in each of the bit vectors for the other code portions.

10. The method of claim 7 wherein the step of calculating property values of the bit vectors for other code portions comprises the step of calculating which bits in the bit vectors for the other code portions are set.

11. The method of claim 7 wherein the step of calculating property values of the bit vectors for other code portions comprises the step of determining a first bit in each of the bit vectors for the other code portions that is set.

12. The method of claim 7 further comprising the step of combining the calculated property values for each bit vector of the other code portions into a single value to simplify the step of using the calculated property values to determine which of the other code portions is placed next in the placement orders of the executable.

13. In a computer system, a method of determining placement order of code portions that together non-redundantly comprise a single executable module, said placement order comprising ordered portions, said method comprising the steps of:

providing a bit vector for each code portion, wherein each bit in every bit vector is associated with a time period during execution of the module and each bit is settable to indicate that the code portion was executed during the associated time period;

executing the module,

each time a code portion is executed during the execution of the module, setting the bit of the bit vector for the code portion that is associated with the current time period;

calculating a weight matrix having entries from the bit vectors, each entry specifying a weight of a first bit vector for a first of the code portions with a weight for a second bit vector of a second of the code portions; and

using the weights in the weight matrix to determine the placement order of the code portions in the executable.

14. The method of claim 13 wherein the step of calculating the weight matrix comprises the step for each entry of calculating a weight that quantifies merit in placing the first code portion in a next position in the placement order relative to other of the code portions given that a position in the placement order the second code portion has already been determined.

15. The method of claim 14 wherein the weight is calculated to quantify merit in placing the first code portion in the next position in the placement order relative to a last placed code portion.

16. The method of claim 14 wherein the step for each entry of calculating the weight further comprises the step of calculating the weight for each entry as a combination of component values, each component value associated with a property of the bit vectors of the code portions.

17. The method of claim 16 wherein the component values are disjoint such that each component value is not influenced by other component values.

18. The method of claim 17 wherein the component values are calculated to contribute to the weight in different degrees such that a component value of lesser degree cannot contribute to the weight more than a component value of greater degree.

19. The method of claim 14 wherein the step of using the weights in the weight matrix to determine the placement order of the code portions in the executable comprises the step of using only a predetermined portion of the weight matrix in determining placement order of each code portion to limit searching of the weight matrix to the predetermined portion.

20. A computer-readable medium for causing a computer system to order code portions that together non-redundantly comprise a single executable module by performing the steps of:

executing the module on the computer system for a period of time;

defining within the period of time during which the module is executed a plurality of time intervals including a first and a second time interval;

during execution of the module on the computer system, determining which of the code portions are invoked within the first interval and determining which of the code portions are indeed within the second time interval; and

ordering the code portions within the module so that code portions determined to be invoked within the first time interval are placed within the module in close proximity to each other relative to code portions not determined to be invoked within the first time interval and code portions determined to be invoked within the second time interval are placed in close proximity to each other relative to code portions not determined to be invoked during the second time interval.

21. The computer-readable medium according to claim 20 wherein the step of determining which of the code portions are invoked within a first and a second time interval includes the steps of:

creating a bit vector for each code portion, each bit vector containing a first bit corresponding to the first time interval and a second bit corresponding to the second time interval;

upon invocation of a code portion within the first time interval, setting the first bit in the bit vector for the invoked code portion; and

upon invocation of a code portion within the second time interval, setting the second bit in the bit vector for the invoked code portion.

22. A computer-readable medium whose contents cause a computer system to order code portions that together non-redundantly comprise a single executable module to produce an optimized executable version of the module by performing the steps of:

providing an instrumented executable version of the module, the instrumented executable version containing instructions within each code portion that, when executed, will cause execution information regarding the code portion to be recorded, the recorded execution information including when the code portion is invoked;

executing the instrumented executable version of the module to gather the execution information for each code portion;

analyzing the execution information to determine a desired placement order for each code portion, each code portion'"'"'s desired placement order reflecting a desired physical location for the code portion within the module relative to the physical locations of the other code portions, by determining that code portions which are invoked at proximate times have proximate placement orders;

providing an original compiled version; and

linking the original compiled version of the module according to the determined desired placement order for each code portion to produce an optimized executable version of the module.

23. A computer-readable medium whose contents cause a computer system to determine placement order of code portions that together non-redundantly comprise a single executable module, said placement order comprising ordered portions, by performing the steps of:

providing a bit vector for each code portion, wherein each bit in every bit vector is associated with a time period during execution of the module and each bit is settable to indicate that the code portion was executed during the associated time period;

executing the module;

each time a code portion is executed during the execution of the module, setting the bit of the bit vector for the code portion that is associated with the current time period;

calculating a weight matrix having entries from the bit vectors, each entry specifying a weight of a first bit vector for a first of the code portions with a weight for a second bit vector of a second of the code portions; and

using the weights in the weight matrix to determine the placement order of the code portions in the executable.