Purity analysis using white list/black list analysis

• US 9,594,754 B2
• Filed: 01/25/2016
• Issued: 03/14/2017
• Est. Priority Date: 11/08/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Gounares, Alexander G., Li, Ying, Garrett, Charles D., Noakes, Michael D.
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Perez-Arroyo, Raquel
• Application Number:
  US15/005,643
• Publication Number:
  US 20160140018A1
• Time in Patent Office: 414 Days
• Field of Search: 707/690
• US Class Current: 1/1
• 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 computer-implemented method of determining whether an impure function of a program is memoizable, the computer-implemented method comprising:

performing a static code analysis of the program which identifies for one or more functions of the program whether a function has a side effect, and if the function has a side effect, classifying the function as impure;

for each function classified as impure;

analyzing different sets of input parameters treated as input vectors,

clustering the input vectors to create areas of known input vectors for which memoization may be performed and areas of known input vectors for which memoization may not be performed, and

for a given input vector, classifying at least one or more of the impure functions as memoizable or not based at least in part on whether the given input vector is within one of said areas of known input vectors for which memoization may be performed; and

storing the one or more impure functions classified as memoizable in a memoization list to facilitate return of cached results for those functions stored on the memoization list so that the cached results are provided without having to re-execute the one or more functions.

2. The computer-implemented method of claim 1 further comprising:

for the given input vector, classifying whether the given input vector is within a known area of input vectors for which memoization may not be performed.

3. The computer-implemented method of claim 1, wherein:

at least one area of known input vectors for which memoization may be performed is defined by a first boundary;

at least one area of known input vectors for which memoization may not be performed is defined by a second boundary;

classifying at least one or more of the impure functions as memoizable or not further comprises determining whether the given input function is within either the first or second boundary.

4. The computer-implemented method of claim 1 further comprising:

for the given input vector, determining for one or more of the impure functions whether the given input vector is not within either one of said known areas of input vectors for which memoization may be performed or one of said known areas of input vectors for which memoization may not be performed; and

not adding to the memoization list one or more impure functions based on said determination.

5. The computer-implemented method of claim 4, wherein determining for one or more of the impure functions whether the given input vector is not within either one of said known areas of input vectors for which memoization may be performed or one of said known areas of input vectors for which memoization may not be performed comprises determining that the given input vector is not within either of the first or second boundaries.

6. The computer-implemented method of claim 1 wherein the areas of known input vectors for which memoization may be performed and areas of known input vectors for which memoization may not be performed are evaluated for consistency.

7. The computer-implemented method of claim 6 wherein the evaluation for consistency is performed using said different sets of input parameters for a given impure function, and wherein said consistency is determined with a statistical confidence.

8. A computing system comprising:

memory containing computer-executable instructions;

one or more processors which, when executing the computer-executable instructions, cause the computing system to determine whether an impure function of a program is memoizable, by causing the computing system to perform the following;

perform a static code analysis of the program which identifies for one or more functions of the program whether a function has a side effect, and if the function has a side effect, classifying the function as impure;

for each function classified as impure;

analyze different sets of input parameters treated as input vectors,

cluster the input vectors to create areas of known input vectors for which memoization may be performed and areas of known input vectors for which memoization may not be performed, and

for a given input vector, classify at least one or more of the impure functions as memoizable or not based at least in part on whether the given input vector is within one of said areas of known input vectors for which memoization may be performed; and

store the one or more impure functions classified as memoizable in a memoization list to facilitate return of cached results for those functions stored on the memoization list so that the cached results are provided without having to re-execute the one or more functions.

9. The computing system of claim 8 wherein the one or more processors cause the computing system to further perform the following:

for the given input vector, classify whether the given input vector is within a known area of input vectors for which memoization may not be performed.

10. The computing system of claim 8 wherein:

at least one area of known input vectors for which memoization may be performed is defined by a first boundary;

at least one area of known input vectors for which memoization may not be performed is defined by a second boundary;

and wherein the one or more processors causing the computing system to classify at least one or more of the impure functions as memoizable or not comprises causing the computing system to determine whether the given input function is within either the first or second boundary.

11. The computing system of claim 8 wherein the one or more processors cause the computing system to further perform the following:

for the given input vector, determine for one or more of the impure functions whether the given input vector is not within either one of said known areas of input vectors for which memoization may be performed or one of said known areas of input vectors for which memoization may not be performed; and

not add to the memoization list one or more impure functions based on said determination.

12. The computing system of claim 11 wherein causing the computing system to determine for one or more of the impure functions whether the given input vector is not within either one of said known areas of input vectors for which memoization may be performed or one of said known areas of input vectors for which memoization may not be performed comprises causing the computing system to determine that the given input vector is not within either of the first or second boundaries.

13. The computing system of claim 8 wherein the areas of known input vectors for which memoization may be performed and areas of known input vectors for which memoization may not be performed are evaluated for consistency.

14. The computing system of claim 8 wherein the evaluation for consistency is performed using said different sets of input parameters for a given impure function, and wherein said consistency is determined with a statistical confidence.

15. A computer program product comprising one or more computer storage device containing computer-executable instructions which, when performed by one or more processors, implemented a method of determining whether an impure function of a program is memoizable, and wherein the method comprises:

performing a static code analysis of the program which identifies for one or more functions of the program whether a function has a side effect, and if the function has a side effect, classifying the function as impure;

for each function classified as impure;

analyzing different sets of input parameters treated as input vectors,

clustering the input vectors to create areas of known input vectors for which memoization may be performed and areas of known input vectors for which memoization may not be performed, and

for a given input vector, classifying at least one or more of the impure functions as memoizable or not based at least in part on whether the given input vector is within one of said areas of known input vectors for which memoization may be performed; and

storing the one or more impure functions classified as memoizable in a memoization list to facilitate return of cached results for those functions stored on the memoization list so that the cached results are provided without having to re-execute the one or more functions.

16. The computer program product of claim 15 wherein the method further comprises:

for the given input vector, classifying whether the given input vector is within a known area of input vectors for which memoization may not be performed.

17. The computer program product of claim 15, wherein:

at least one area of known input vectors for which memoization may be performed is defined by a first boundary;

at least one area of known input vectors for which memoization may not be performed is defined by a second boundary;

and wherein the method further comprises classifying at least one or more of the impure functions as memoizable or not further comprises determining whether the given input function is within either the first or second boundary.

18. The computer program product of claim 15 wherein the method further comprises:

for the given input vector, determining for one or more of the impure functions whether the given input vector is not within either one of said known areas of input vectors for which memoization may be performed or one of said known areas of input vectors for which memoization may not be performed; and

not adding to the memoization list one or more impure functions based on said determination.

19. The computer program product of claim 18, wherein determining for one or more of the impure functions whether the given input vector is not within either one of said known areas of input vectors for which memoization may be performed or one of said known areas of input vectors for which memoization may not be performed comprises determining that the given input vector is not within either of the first or second boundaries.

20. The computer program product claim 15 wherein the areas of known input vectors for which memoization may be performed and areas of known input vectors for which memoization may not be performed are evaluated for consistency, and wherein said consistency is determined with a statistical confidence.