Purity Analysis Using White List/Black List Analysis

• US 20130073523A1
• Filed: 11/08/2012
• Published: 03/21/2013
• 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.
• Granted Patent: US 9,262,416 B2
• Time in Patent Office: Days
• US Class Current: 707/690
• CPC Class Codes: G06F 11/3616 using software metrics
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code

Abstract

Memoizable functions may be identified by analyzing a function'"'"'s side effects. The side effects may be evaluated using a white list, black list, or other definition. The side effects may also be classified into conditions which may or may not permit memoization. Side effects that may have de minimus or trivial effects may be ignored in some cases where the accuracy of a function may not be significantly affected when the function may be memoized.

Claims

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

determining that a first function has a first side effect;

looking up said first side effect in a side effect database;

determining that said first side effect is de minimus from said side effect database; and

causing said first function to be memoized.

2. The method of claim 1 further comprising:

determining that said first function with said first side effect is memoizable under a first condition but not memoizable under a second condition; and

causing said first function to be memoized under said first condition and not memoized under said second condition.

3. The method of claim 2, said first condition comprising a first set of input values to said first function.

4. The method of claim 3, said second condition comprising a second set of input values to said first function.

5. The method of claim 4 further comprising:

determining that a second function has said first side effect;

determining that said first side effect is de minimus from said side effect database; and

causing said second function to be memoized.

6. The method of claim 4 further comprising:

evaluating said first function for consistency using said first set of input values to determine that said first function returns a first result given said first set of input values.

7. The method of claim 6, said consistency being determined with a statistical confidence.

8. The method of claim 7, said side effect database indicating that said first side effect causes a variance in said first function by less than a predefined amount.

9. The method of claim 7 further comprising:

looking up said first function in a configuration database;

retrieving an acceptable variance limit for said first function; and

determining that first function is memoizable based at least in part on said acceptable variance limit.

10. The method of claim 1 further comprising:

executing said first function under said first condition to return a first result; and

storing said first result.

11. The method of claim 10 further comprising:

determining that said first function is to be executed under said first condition;

determining that said first result is stored; and

retrieving said first result and returning said first result.

12. A system comprising:

a processor;

a purity analyzer executing on said processor that;

determines that a first function has a first side effect;

looks up said first side effect in a side effect database;

determines that said first side effect is de minimus from said side effect database; and

causes said first function to be memoized.

13. The system of claim 12, said purity analyzer that further:

determines that said first function with said first side effect is memoizable under a first condition but not memoizable under a second condition; and

causes said first function to be memoized under said first condition and not memoized under said second condition.

14. The system of claim 13, said first condition comprising a first set of input values to said first function.

15. The system of claim 14, said second condition comprising a second set of input values to said first function.

16. The system of claim 15, said purity analyzer that further:

determines that a second function has said first side effect;

determines that said first side effect is de minimus from said side effect database; and

causes said second function to be memoized.

17. The system of claim 16, said purity analyzer that further:

evaluates said first function for consistency using said first set of input values to determine that said first function returns a first result given said first set of input values.

18. The system of claim 17, said consistency being determined with a statistical confidence.

19. The system of claim 18, said side effect database indicating that said first side effect causes a variance in said first function by less than a predefined amount.

20. The system of claim 17, said purity analyzer that further:

looks up said first function in a configuration database;

retrieves an acceptable variance limit for said first function; and

determines that first function is memoizable based at least in part on said acceptable variance limit.