Concurix Corporation

Microsoft Technology Licensing, LLC

Michael D Noakes

Ying Li

Charles D Garrett

Alexander G Gounares

Alexadner G Gounares

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.

Purity analysis using white list/black list analysis

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.

Determination of function purity for memoization

A function may be memoized when a side effect is a read only side effect. Provided that the read only side effect does not mutate a memory object, the side effect may be considered as an input to a function for purity and memoization analysis. When a read only side effect may be encountered during memoization analysis, the read only side effect may be treated as an input to a function for memoization analysis. In some cases, such side effects may enable an impure function to behave as a pure function for the purposes of memoization.

Memoizing with read only side effects

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.

Input vector analysis for memoization estimation

Memoization may be deployed using a configuration file or database that identifies functions to memorize, and in some cases, includes input and result values for those functions. As an application is executed, functions defined in the configuration file may be captured and memoized. During the first execution of the function, the return value may be captured and stored in the configuration file. For subsequent executions of the function, the return value may be stored in the configuration file. In some cases, the configuration file may be distributed with the return values to client computers. The configuration file may be created by one device and deployed to other devices in some deployments.

Memoization configuration file consumed at runtime

A set of optimizations may be defined in a configuration database. The configuration database may be defined with a set of boundaries that may define conditions under which the optimizations may be valid. When the conditions are not met, a new configuration database may be requested from an optimization server. The system may be used to distribute and manage optimizations for an application, which may be deployed in interpreted or runtime scenarios or in pre-execution or compiled scenarios.

Optimized settings in a configuration database with boundaries

Memoization may be deployed using a configuration file or database that identifies functions to memorize, and in some cases, includes input and result values for those functions. At compile time, functions defined in the configuration file may be captured and memoized. During compilation or other pre-execution analysis, the executable code may be modified or otherwise decorated to include memoization code. The memoization code may store results from a function during the first execution, then merely look up the results when the function may be called again. The memoized value may be stored in the configuration file or in another data store. In some embodiments, the modified executable code may operate in conjunction with an execution environment, where the execution environment may optionally perform the memoization.

Memoization configuration file consumed at compile time

A configurable memory allocation and management system may generate a configuration file with memory settings that may be deployed at runtime. An execution environment may capture a memory allocation boundary, look up the boundary in a configuration file, and apply the settings when the settings are available. When the settings are not available, a default set of settings may be used. The execution environment may deploy the optimized settings without modifying the executing code.

Optimized memory configuration deployed on executing code

A configurable memory allocation and management system may generate a configuration file with memory settings that may be deployed prior to runtime. A compiler or other pre-execution system may detect a memory allocation boundary and decorate the code. During execution, the decorated code may be used to look up memory allocation and management settings from a database or to deploy optimized settings that may be embedded in the decorations.

Optimized memory configuration deployed prior to execution

A computer software execution system may have a configurable memory allocation and management system. A configuration file or other definition may be created by analyzing a running application and determining an optimized set of settings for the application on the fly. The settings may include memory allocated to individual processes, memory allocation and deallocation schemes, garbage collection policies, and other settings. The optimization analysis may be performed offline from the execution system. The execution environment may capture processes during creation, then allocate memory and configure memory management settings for each individual process.

Growing community of inventors

Burien, WA, United States of America

Michael D Noakes