Object-oriented compiler mechanism for automatically selecting among multiple implementations of objects

• US 6,360,360 B1
• Filed: 02/08/1996
• Issued: 03/19/2002
• Est. Priority Date: 02/08/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bates, Cary Lee, Schmidt, William Jon, Prosser, Edward Curtis
• Primary Examiner(s): COURTENAY III, ST JOHN
• Application Number:
  US08/598,360
• Time in Patent Office: 2,231 Days
• Field of Search: 395/704, 395/705, 717/5-10, 709/330, 707/102, 707/103
• US Class Current: 717/160
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

In an object-oriented or object-based computer system, a compiler mechanism allows a compiler to automatically select among multiple implementations of an object to optimize the performance of the compiled code. The selection may be made by assigning a weighted cost to each of the implementations, and selecting the implementation with the lowest weighted cost, where the weighted cost represents estimates of execution frequencies for each of the object'"'"'s functions. In the alternative, for implementations that have different interfaces, the selection may be made based on an evaluation of the functions used in the program compared to the functions provided by the different implementations, and selecting an implementation that contains all functions issued against the object with a minimum of functions that are not issued against the object.

Claims

1. A computer apparatus comprising:

a processing unit, the processing unit executing a first instruction stream;

a compiler, the compiler generating the first instruction stream from an object oriented instruction stream, the compiler including;

an implementation selector, the implementation selector automatically selecting according to at least one predetermined criterion which of a plurality of pre-existing implementations for at least one object oriented object in the object oriented instruction stream is used to generate the first instruction stream.

2. The computer apparatus of claim 1 wherein the predetermined criterion includes a weighted cost function corresponding to each of the plurality of implementations of the object, wherein the implementation selector selects the implementation for the object that has the lowest weighted cost.

3. The computer apparatus of claim 2 wherein the weighted cost function comprises a numerical relationship between a cost of each object oriented function for each of the plurality of implementations of the object and a corresponding function call profile for each of the plurality of implementations, wherein the function call profile includes an estimate of the frequency of execution for each object oriented function as the first instruction stream is executed on the processing unit.

4. The computer apparatus of claim 2 wherein the weighted cost function for each of the plurality of implementations is derived heuristically by the compiler according to the attributes of one of the first and object oriented instruction streams.

5. The computer apparatus of claim 2 wherein the weighted cost function for each of the plurality of implementations is derived by using dynamic profiling information acquired by running a portion of test code on the processing unit, the test code being designed to simulate the performance of the first instruction stream.

6. The computer apparatus of claim 1 wherein each object includes at least one object oriented function, and wherein the implementation selector selects which of the plurality of implementations is used to generate the first instruction stream according to which object oriented functions are issued against the object.

7. The computer apparatus of claim 6 wherein the implementation selector selects one of the plurality of implementations that contains all of the functions that are issued against the object.

8. The computer apparatus of claim 7 wherein the selected implementation further contains the fewest functions that are not issued against the object.

9. A computer apparatus, the computer apparatus generating a first instruction stream executable on a processing unit from an object oriented instruction stream, the computer apparatus comprising:

an implementation selector, the implementation selector automatically selecting at compile time according to at least one predetermined criterion which of a plurality of pre-existing implementations for at least one object oriented object in the object oriented instruction stream is used to generate the first instruction stream.

10. The computer apparatus of claim 9 wherein the predetermined criterion includes a weighted cost function corresponding to each of the plurality of implementations of the object, wherein the implementation selector selects the implementation for the object that has the lowest weighted cost.

11. The computer apparatus of claim 9 wherein each object includes at least one object oriented function, and wherein the implementation selector selects which of the plurality of implementations is used to generate the first instruction stream according to which object oriented functions are issued against the object.

12. A program product comprising:

a recordable media; and

a compiler recorded on the recordable media, the compiler being used to generate a first instruction stream from an object oriented instruction stream, the compiler including;

an implementation selector, the implementation selector automatically selecting according to at least one predetermined criterion which of a plurality of pre-existing implementations for at least one object oriented object in the object oriented instruction stream is used to generate the first instruction stream.

13. The program product of claim 12 wherein the predetermined criterion includes a weighted cost function corresponding to each of the plurality of implementations of the object, wherein the implementation selector selects the implementation for the object that has the lowest weighted cost.

14. The program product of claim 12 wherein each object includes at least one object oriented function, and wherein the implementation selector selects which of the plurality of implementations is used to generate the first instruction stream according to which object oriented functions are issued against the object.

15. A program product comprising:

a recordable media; and

a compiler recorded on the recordable media, the compiler being used to generate a first instruction steam for a processing unit from an object oriented instruction stream, the compiler including;

an implementation selector, the implementation selector automatically selecting according to at least one predetermined criterion which of a plurality of pre-existing implementations for at least one object oriented object in the object oriented instruction stream is used to generate the first instruction stream according to a weighted cost function corresponding to each of the plurality of implementations of the object, the weighted cost function for each of the plurality of implementations being determined from dynamic profiling information acquired by running a portion of test code on the processing unit, the test code being designed to simulate the performance of the first instruction stream, the weighted cost function representing an estimate of the frequency of execution for each object oriented function as the first instruction stream is executed on the processing unit, and wherein the implementation selector selects the implementation for the object that has the lowest weighted cost.

16. A compiler method for generating a first instruction stream from an object oriented instruction stream and for optimizing the performance of a processing unit that executes the first instruction stream, the method including the step of:

automatically selecting according to at least one predetermined criterion which of a plurality of pre-existing implementations for at least one object oriented object in the object oriented instruction stream is used to generate the first instruction stream.

17. The compiler method of claim 16 wherein the predetermined criterion is determined by performing the step of:

deriving a weighted cost function corresponding to each of the plurality of implementations of the object, wherein the implementation selector selects the implementation for the object that has the lowest weighted cost.

18. The compiler method of claim 17 wherein the weighted cost function for each of the plurality of implementations is derived heuristically by the compiler according to the attributes of one of the first and object oriented instruction streams.

19. The compiler method of claim 17 wherein the weighted cost function for each of the plurality of implementations is derived by using dynamic profiling information acquired by running a portion of test code on the processing unit, the test code being designed to simulate the performance of the first instruction stream.

20. The compiler method of claim 17 wherein the test code comprises an object code output from an initial compilation of the object oriented instruction stream, the object code output including instrumentation code to generate the dynamic profiling information.

21. The compiler method of claim 16 further including the steps of:

determining a cost function for each of the plurality of implementations;

determining a function call profile for each of the plurality of implementations, the function call profile including an estimate of the frequency of execution for each object oriented function as the first instruction stream is executed on the processing unit;

weighting the cost function with the function call profile for each implementation to arrive at a weighted cost function for each of the plurality of implementations; and

selecting the implementation for the object that has the lowest weighted cost.

22. The compiler method of claim 16, wherein each object includes at least one object oriented function, and wherein the step of automatically selecting which of the plurality of implementations is used to generate the first instruction stream includes the steps of:

determining which object oriented functions are issued against the object; and

selecting one of the implementations that contains all the object oriented functions that are issued against the object.

23. The compiler method of claim 22 wherein the selected implementation further contains the fewest object oriented functions that are not issued against the object.

24. A method for distributing a program product comprising the steps of:

initiating a connection between a first computer system and a second computer system;

transmitting the program product from the first computer system to the second computer system, the program product being a compiler, the compiler being used to generate a first instruction stream from an object oriented instruction stream, the compiler including an implementation selector for automatically selecting according to at least one predetermined criterion which of a plurality of pre-existing implementations for at least one object oriented object in the object oriented instruction stream is used to generate the first instruction stream.

25. A method for programming a computer comprising the steps of:

providing a compiler, the compiler generating a first instruction stream from an object oriented source code instruction stream;

providing a plurality of implementations for at least one object oriented object to the compiler;

writing the source code instruction stream in an object oriented language requiring compilation by the compiler;

compiling the object oriented source code instruction stream using the compiler, the compilation step including the step of;

automatically selecting which of the plurality of implementations for at least one object oriented object in the object oriented source code instruction stream is used to generate the first instruction stream according to an estimation of execution frequencies of object oriented functions associated with the object.

26. The method of claim 25 further comprising the steps of:

precompiling the source code instruction stream to produce a test code instruction stream;

executing the test code instruction stream on a computer system similar to that anticipated for executing the first instruction stream;

acquiring profiling information relating to the execution frequencies of each function of each object;

providing the profiling information to the compiler;

wherein the step of automatically selecting among the plurality of implementations includes the step of selecting one of the plurality of implementations based on the profiling information.

27. The method of claim 26 further comprising the step of inserting instrumentation code into the test code instruction stream to measure the performance of the test code instruction stream during the executing step, and wherein the step of acquiring profiling information includes the step of deriving the profiling information from the results provided by the instrumentation code.

28. The method of claim 26 wherein the step of acquiring profiling information includes the steps of:

collecting an address trace during the step of executing the test code instruction stream; and

deriving the profiling information from the results provided by the address trace.

29. The method of claim 25 wherein each object includes at least one object oriented function, and wherein the step of automatically selecting which of the plurality of implementations is used to generate the first instruction stream includes the steps of:

determining which object oriented functions are issued against the object; and

selecting one of the implementations that contains all the object oriented functions that are issued against the object.