# US 8,752,021 B2 · Input vector analysis for memoization estimation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,752,021 B2
- Document ID: US8752021B2
- Status: Granted
- Kind: B2
- Application number: 13/671,822
- Filed: 2012-11-08
- Published: 2013-03-21
- Granted: 2014-06-10
- Earliest claimed: 2012-11-08
- Assignees: Concurix Corporation
- Applicants: Concurix Corporation
- Inventors: Ying Li; Charles D. Garrett; Michael D. Noakes; Alexander G. Gounares
- Web page: https://patentgrep.com/patent/US8752021B2

## CPC

- G06F 16/35: Clustering; Classification
- G06F 11/3409: {for performance assessment}
- G06F 11/3452: {Performance evaluation by statistical analysis}
- G06F 11/3466: {Performance evaluation by tracing or monitoring}
- G06F 11/36: Prevention of errors by analysis, debugging or testing of software
- G06F 11/3608: {using formal methods, e.g. model checking, abstract interpretation (theorem proving G06N5/013)}
- G06F 2201/82: Solving problems relating to consistency
- G06F 2201/865: Monitoring of software
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

The method of claim 1 further comprising:
transmitting said new input vector to an optimization server.

### Claim 5 (depends on 4)

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.

### Claim 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.

### Claim 7 (depends on 6)

The method of claim 6 further comprising:
storing said confidence boundaries.

### Claim 8 (depends on 6)

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.

### Claim 9 (depends on 8)

The method of claim 8, said operational data comprising:
input vectors for said first function; and
results for said first function.

### Claim 10 (depends on 9)

The method of claim 9, said operational data further comprising:
resource consumption for said first function.

### Claim 11 (depends on 6)

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

### Claim 12 (depends on 11)

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

### Claim 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.