Input vector analysis for memoization estimation

• US 8,752,021 B2
• Filed: 11/08/2012
• Issued: 06/10/2014
• Est. Priority Date: 11/08/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Concurix Corporation
• Inventors: Li, Ying, Garrett, Charles D., Noakes, Michael D., Gounares, Alexander G.
• Primary Examiner(s): Chen, Xi D
• Application Number:
  US13/671,822
• Publication Number:
  US 20130073837A1
• Time in Patent Office: 579 Days
• Field of Search: None
• US Class Current: 717/127
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 11/36 Preventing errors by testing or debugging software
• CPC Class Codes: G06F 11/3608 using formal methods, e.g. model checking, abstract interpretation theorem proving G06N5/013
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 2201/865 Monitoring of software

Abstract

A function'"'"'s purity may be estimated by comparing a new input vector to previously analyzed input vectors. When a new input vector is within a confidence boundary, the new input vector may be treated as a known vector, even when that vector has not been evaluated. The input vector may reflect the input parameters passed to a function, and the function may be analyzed to determine whether to memoize with the input vector. The function may be a function that behaves as a pure function in some circumstances and with some input vectors, but not with others. By memoizing the function when possible, the function may be executed much faster, thereby improving performance.

Claims

1. A computer-implemented method comprising:

selecting a first impure function;

determining an input space for said first impure function, said input space comprising a range of input values for input parameters for said first impure function;

tracing said first impure function during execution and capturing operational data comprising input values and returned results;

determining a first subset of said input space where said first impure function behaves as a pure function;

receiving a new input vector, said new input vector comprising at least one input value not comprised in said operational data;

determining that said new input vector is within said first subset of said input space; and

memoizing said first impure function for said new input vector;

determining a second subset of said input space where said first impure function behaves as an impure function;

receiving a second new input vector, said second input vector comprising input values not found in said operational data;

determining that said second new input vector is within said second subset of said input space; and

not memoizing said first impure function for said second new input vector.

2. The method of claim 1, said input parameters comprising discrete input parameters.

3. The method of claim 1, said input parameters comprising continuous input parameters.

4. The method of claim 1 further comprising:

transmitting said new input vector to an optimization server.

5. The method of claim 4 further comprising:

tracing said first impure function with said new input vector to collect said operational data for a plurality of executions of said first impure function with said new input vector; and

determining that said first impure function with said new input vector is memoizable.

6. A computer-implemented method comprising:

receiving a first function;

performing a static code analysis on said first function and determining that said first function is impure due to a side effect;

exercising said first function with a plurality of input vectors, each of said input vectors comprising a set of input parameters;

classifying each of said input vectors as either memoizable or not memoizable;

mapping said input vectors in a vector space;

generating confidence boundaries defining memoizable and not memoizable input vectors, said confidence boundaries defining a subspace within said vector space;

receiving a new input vector;

determining that said new input vector is within a memoizable subspace; and

causing said first function to be memoized with said new input vector;

receiving a second new input vector;

determining that said second new input vector is within a non-memoizable subspace; and

causing said first function not to be memoized with said second new input vector.

7. The method of claim 6 further comprising:

storing said confidence boundaries.

8. The method of claim 6, said classifying each of said input vectors comprising:

collecting operational data regarding said first function to determine an input vector is memoizable.

9. The method of claim 8, said operational data comprising:

input vectors for said first function; and

results for said first function.

10. The method of claim 9, said operational data further comprising:

resource consumption for said first function.

11. The method of claim 6, at least one of said input parameters being a continuous variable.

12. The method of claim 11, at least one of said input parameters being a discrete variable.

13. A system comprising:

a processor;

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

selects a first impure function;

determines an input space for said first impure function, said input space comprising a range of input values for input parameters for said first impure function;

traces said first impure function during execution and capturing operational data comprising input values and returned results;

determines a first subset of said input space where said first impure function behaves as a pure function;

receives a new input vector, said new input vector comprising at least one input value not comprised in said operational data;

determines that said new input vector is within said first subset of said input space; and

memoizes said first impure function for said new input vector;

determines a second subset of said input space where said first impure function behaves as an impure function;

receives a second new input vector, said second input vector comprising input values not found in said operational data;

determines that said second new input vector is within said second subset of said input space; and

not memoizes said first impure function for said second new input vector.