Selecting Functions for Memoization Analysis

• US 20130074057A1
• Filed: 11/08/2012
• Published: 03/21/2013
• Est. Priority Date: 11/08/2012
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Concurix Corporation
• Inventors: Gounares, Alexander G., Li, Ying, Garrett, Charles D., Noakes, Michael D.
• Application Number:
  US13/671,828
• Publication Number:
  US 20130074057A1
• Time in Patent Office: Days
• US Class Current: 717/152
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code

Abstract

A function may be selected for memoization when the function indicates that memoization may result in a performance improvement. Impure functions may be identified and ranked based on operational data, which may include length of execution. A function may be selected from a ranked list and analyzed for memoization. The memoization analysis may include side effect analysis and consistency analysis. In some cases, the optimization process may perform optimization on one function at a time so as to not overburden a running system.

Claims

1. A method performed by at least one computer processor, said method comprising:

receiving an application, said application comprising a plurality of functions;

performing an initial analysis of said application, said initial analysis comprising;

executing said application and during said executing, collecting initial operational data comprising length of execution for each of said functions;

selecting a first function for detailed analysis at least in part based on said operational data;

performing a detailed analysis on said first function, said detailed analysis comprising;

receiving additional operational data comprising input parameters and return values;

evaluating said first function to determine said first function is memoizable; and

causing said first function to be memoized.

2. The method of claim 1, said initial operational data comprising call frequency.

3. The method of claim 2, said initial analysis further comprising:

creating an execution representation for said application, said execution representation comprising links between functions;

4. The method of claim 3, said selecting said first function further being determined in part based on said execution representation.

5. The method of claim 4, said initial analysis further comprising:

applying a score to each of said plurality of functions, said score being determined in part based on said operational data and said execution representation.

6. The method of claim 5, said score being determined in part by position of a function within said execution representation.

7. The method of claim 6, said detailed analysis comprising side effect analysis of said first function.

8. The method of claim 7, said side effect analysis being static side effect analysis.

9. The method of claim 7, said side effect analysis being dynamic side effect analysis.

10. The method of claim 1, said detailed analysis being performed on a remote processor.

11. The method of claim 10 further comprising:

storing said first function in a memoization database.

12. The method of claim 11, said initial analysis being performed by a first processor.

13. The method of claim 12, said first function being memoized by a third processor.

14. The method of claim 13, said first processor executing said application in an instrumented environment.

15. The method of claim 13, said first processor executing said application in a production environment.

16. A system comprising:

a processor;

an application executing on said processor;

a memoization analyzer that;

performs an initial analysis of said application, said initial analysis comprising;

executing said application and during said executing, collecting initial operational data comprising length of execution for each of said functions;

selecting a first function for detailed analysis at least in part based on said operational data;

performs a detailed analysis on said first function, said detailed analysis comprising;

receiving additional operational data comprising input parameters and return values;

evaluating said first function to determine said first function is memoizable; and

causing said first function to be memoized.

17. The system of claim 16 further comprising:

a configuration database comprising memoizable functions.

18. The system of claim 17 further comprising:

a configuration manager that communicates with an optimization server to update said configuration database.

19. The system of claim 18, said configuration manager that further transmits updates to said optimization server.

20. The system of claim 16 further comprising:

a purity analyzer that determines functional purity for said first function when said first function has been identified as impure based on static analysis.