Determination of function purity for memoization
View Patent ↗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.
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.