Determination of function purity for memoization

• US 8,839,204 B2
• Filed: 11/08/2012
• Issued: 09/16/2014
• Est. Priority Date: 11/08/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Concurix Corporation
• Inventors: Gounares, Alexander G., Li, Ying, Garrett, Charles D., Noakes, Michael D.
• Primary Examiner(s): Dao, Thuy
• Assistant Examiner(s): ST LEGER, GEOFFREY R
• Application Number:
  US13/671,819
• Publication Number:
  US 20130067445A1
• Time in Patent Office: 677 Days
• Field of Search: None
• US Class Current: 717/128
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code

Abstract

The purity of a function may be determined after examining the performance history of a function and analyzing the conditions under which the function behaves as pure. In some cases, a function may be classified as pure when any side effects are de minimis or are otherwise considered trivial. A control flow graph may also be traversed to identify conditions in which a side effect may occur as well as to classify the side effects as trivial or non-trivial. The function purity may be used to identify functions for memoization. In some embodiments, the purity analysis may be performed by a remote server and communicated to a client device, where the client device may memoize the function.

Claims

1. A method performed by a computer processor, said method comprising:

performing a static code analysis of executable code and determining that a first function has side effects;

executing said executable code and tracing the operation of said first function to gather operational data for said first function, said operational data comprising;

input parameter values passed to said first function; and

result values returned from said first function;

analyzing said operational data to determine that said first function is memoizable based on a consistency analysis of said input parameter values and said result values returned from said first function within a statistical confidence limit, the statistical confidence limit reflecting an acceptable variance limit or error that may be tolerated; and

causing said first function to be memoized;

said operational data being gathered from a plurality of execution runs of said executable code;

said plurality of execution runs being performed on a plurality of devices.

2. The method of claim 1, said first function being memoizable under a first set of conditions.

3. The method of claim 2, said first function not being memoizable under a second set of conditions.

4. The method of claim 2, said first set of conditions comprising a subset of said input parameter values.

5. The method of claim 2, said first set of conditions comprising an external condition not included in said input parameter values.

6. The method of claim 5, said external condition comprising a parameter value for a memory object, said memory object not being one of said input parameter values.

7. A method performed by a computer processor, said method comprising:

receiving operational data for a first function, said first function being determined to have side effects from static code analysis, said side effects being classified during said static code analysis;

said operational data comprising;

input parameter values passed to said first function; and

result values returned from said first function;

analyzing said operational data to determine that said first function is memoizable based on a consistency analysis of said input parameter values and said result values returned from said first function within a statistical confidence limit, the statistical confidence limit reflecting an acceptable variance limit or error that may be tolerated; and

storing said first function as a memoizable function in a configuration database;

said operational data being gathered from a plurality of executions of said first function;

said plurality of executions being received from a plurality of devices on which said first function has been executed and said operational data has been gathered.

8. The method of claim 7 further comprising:

receiving an application comprising said first function; and

performing a static code analysis on said application to determine said first function has side effects.

9. The method of claim 8 further comprising:

performing said static code analysis to identify a plurality of functions having side effects; and

determining a processing cost for each of said plurality of functions.

10. The method of claim 9, said first function having a higher processing cost than a second function, said second function having side effects.

11. The method of claim 10, said processing cost being estimated from static code analysis.

12. The method of claim 11, said processing cost being estimated from a control flow graph.

13. A system comprising:

a processor;

a network interface;

a purity analyzer operable on said processor, said purity analyzer that;

receives operational data for a first function, said first function being determined to have a first side effect and a classification for said first side effect, said first side effect being identified from static code analysis;

said operational data comprising input parameter values passed to said first function and result values returned from said first function;

analyzes said operational data to determine that said first function is memoizable based on a consistency analysis of said input parameter values and said result values returned from said first function within a statistical confidence limit, the statistical confidence limit reflecting an acceptable variance limit or error that may be tolerated; and

stores said first function as a memoizable function in a configuration database; and

a distribution mechanism that;

receives a request for said configuration database;

creates a configuration distributable; and

transmits said configuration distributable in response to said request.

14. The system of claim 13 further comprising:

a static analyzer that;

receives an application comprising said first function;

performs a static code analysis on said application to determine that said first function has said first side effect.