Automatic caching of partial results while editing software

• US 9,465,631 B2
• Filed: 11/10/2011
• Issued: 10/11/2016
• Est. Priority Date: 09/30/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Coulson, Michael, Hughes, Gregory
• Primary Examiner(s): VU, TUAN A
• Application Number:
  US13/293,145
• Publication Number:
  US 20130086327A1
• Time in Patent Office: 1,797 Days
• Field of Search: 717/119, 717/114, 711113-114, 711/119, 711/129, 707/201, 707/781
• US Class Current: 1/1
• CPC Class Codes: G06F 11/362 Software debugging
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation

Abstract

An automatic caching system is described herein that automatically determines user-relevant points at which to incrementally cache expensive to obtain data, resulting in faster computation of dependent results. The system can intelligently choose between caching data locally and pushing computation to a remote location collocated with the data, resulting in faster computation of results. The automatic caching system uses stable keys to uniquely refer to programmatic identifiers. The system annotates programs before execution with additional code that utilizes the keys to associate and cache intermediate programmatic results. The system can maintain the cache in a separate process or even on a separate machine to allow cached results to outlive program execution and allow subsequent execution to utilize previously computed results. Cost estimations are performed in order to choose whether utilizing cached values or remote execution would result in a faster computation of a result.

Claims

1. A computer-implemented method to instrument a software program with automatic caching of results, the method comprising:

at a cache point identifying component executed by a processor, receiving a software program including a chain of actions that have been written by an editing user;

automatically identifying and inserting a cache point between actions in the chain of actions in the software program,

the cache point indicating a location where data that has been gathered or computed can be cached to avoid subsequent gathering or computation of the same data, where the cache point has not been previously identified as a potential cache point and the cache point is configured to persist across a series of execution phases;

at a program instrumenting component executed by the processor, instrumenting the software program to add caching logic that checks for and stores cached data at the location indicated by the cache point;

storing the instrumented software program with the caching logic at the cache point in memory associated with the processor;

at a program executing component executed by the processor, during a first execution phase, executing the instrumented software program in the virtual machine,

wherein the execution of the instrumented software program includes;

compiling the instrumented software program; and

running a plurality of actions in the chain of actions, wherein a particular action in the plurality of actions includes caching data based on the caching logic in a cache results store;

receiving an edit of the instrumented software program, the edit generated responsive to user input; and

executing the edited software program during a second execution phase;

wherein the execution of the edited software program includes;

recompiling the edited software program;

rerunning a portion of the plurality of actions in the edited software program;

determining that the cached data corresponding to the particular action is to be retrieved from the cache results store rather than recomputed;

in response to determining that the cached data is to be retrieved, skipping the particular action corresponding to the cached data in the plurality of actions and retrieving the cached data while rerunning the remainder of the plurality of actions.

2. The method of claim 1 wherein receiving the software program includes receiving the program through a development tool during an editing session or build process of the tool.

3. The method of claim 1 wherein automatically identifying and inserting the cache point includes, in association with a visual environment for building the software program by selecting a visual program building block, identifying a point following the block as a point to cache data created or output by the block.

4. The method of claim 1 wherein automatically identifying and inserting the cache point includes identifying a point after which computation beyond a threshold resource usage has occurred.

5. The method of claim 1 wherein automatically identifying and inserting the cache point are implemented repeatedly on the software program as the user edits the program over time.

6. The method of claim 1 wherein automatically identifying and inserting the cache point includes selecting a cache key to distinguish the identified cache point.

7. The method of claim 1 wherein instrumenting the software program includes adding logic before a block of code executes that determines whether a cached version of the data generated by the block is available so that the block can be bypassed by using the cached data.

8. The method of claim 1 wherein instrumenting the software program includes adding logic at the end of a block of code that stores output of the block of code to the cache for use during subsequent potential runs of the block of code.

9. The method of claim 1 wherein instrumenting the software program includes accessing an intermediate language version of the program which can be instrumented by adding additional intermediate language instructions before the program is compiled.

10. The method of claim 1 wherein instrumenting the software program includes associating cached data at the location with a cache key that acts as an identifier for distinguishing cached data associated with one point in the program from cached data associated with other points from the same or other programs.

11. The method of claim 1 wherein instrumenting the software program includes, after receiving changed program code, identifying data dependencies and invalidating cached data rendered invalid based on the received changes.

12. The method of claim 1 wherein storing the instrumented software program includes storing the instrumented software program by creating a binary module or other runtime module that represents the software program.

13. A computer system for automatic caching of partial results while editing software, the system comprising:

a processor and associated memory;

a cache point identifying component executed by the processor to;

receive a software program including a chain of actions that have been written by an editing user;

automatically identify and insert a cache point between actions in the chain of actions in the software program, the cache point indicating a location where data that has been gathered or computed can be cached to avoid subsequent gathering or computation of the same data where the cache point has not been previously identified as a potential cache point and the cache point is configured to persist across a series of execution phases;

a program instrumenting component executed by the processor to;

instrument the software program to add caching logic that checks for and stores cached data at the location indicated by the cache point;

store the instrumented software program with the caching logic at the cache point in the memory;

a program executing component executed by the processor to;

during a first execution phase, execute the instrumented software program in the virtual machine,

wherein the execution of the instrumented software program includes;

compiling the instrumented software program; and

running a plurality of actions in the chain of actions, wherein a particular action in the plurality of actions includes caching data based on the caching logic in a cache results store;

receive an edit of the instrumented software program, the edit generated responsive to user input; and

execute the edited software program during a second execution phase;

wherein the execution of the edited software program includes;

recompiling the edited software program;

rerunning a portion of the plurality of actions in the edited software program;

determining that the cached data corresponding to the particular action is to be retrieved from the cache results store rather than recomputed;

in response to determining that the cached data is to be retrieved, skipping the particular action corresponding to the cached data in the plurality of actions and retrieving the cached data while rerunning the remainder of the plurality of actions.

14. The system of claim 13 wherein the program editing component includes a visual programming environment in which a program author selects one or more program resources and connects the resources together to build a software program.

15. The system of claim 13 wherein the cache point identifying component is configured to identify each junction between blocks in a programming environment that allows users to assemble programs using visual building blocks that represent retrieving or analyzing data as being a suitable point for caching any output result provided by the prior block and consumed by the subsequent block.

16. The system of claim 13 wherein the program instrumenting component is configured to create cache actions that specify a cache key with which to associate the cached data so that future requests for the same data can refer to the data stored in the cache.

17. The system of claim 13 wherein the cached results store is configured to store data across execution sessions of the software program.

18. The system of claim 13 wherein the cached results store is configured to store the cached data on a computer system remote from the computer system executing the software program.