AUTOMATIC CACHING OF PARTIAL RESULTS WHILE EDITING SOFTWARE

• US 20130086327A1
• Filed: 11/10/2011
• Published: 04/04/2013
• Est. Priority Date: 09/30/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Coulson, Michael, Hughes, Gregory
• Granted Patent: US 9,465,631 B2
• Time in Patent Office: Days
• US Class Current: 711/125
• 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:

receiving a software program that has been edited by an editing user;

automatically identifying one or more cache points between instructions of the received software program that indicate one or more locations where data has been gathered or computed and can be cached to avoid at least one subsequent gathering or computation of the same data;

instrumenting the received software program to add caching logic that checks for and stores cached data at identified cache points; and

storing the instrumented program code for execution upon invocation of the software program,

wherein the preceding steps are performed by at least one processor.

2. The method of claim 1 wherein receiving the software program comprises 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 cache points comprises, in association with a visual environment for building the software program by selecting visual program building blocks, identifying points following each block as a point to cache data created or output by the block.

4. The method of claim 1 wherein automatically identifying cache points comprises identifying points after which computation beyond a threshold resource usage has occurred.

5. The method of claim 1 wherein automatically identifying cache points comprises operating repeatedly on the same program as the user edits the program over time.

6. The method of claim 1 wherein automatically identifying cache points comprises selecting a cache key to distinguish each identified cache point.

7. The method of claim 1 wherein instrumenting comprises 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 comprises 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 comprises 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 comprises associates cached data at each 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 comprises, 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 program code comprises storing the code by creating a binary module or other runtime module that represents the software program.

13. The method of claim 1 further comprising repeatedly receiving changes, instrumenting, storing, and executing the software program during an editing session as the user improves the software program.

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

a processor and memory configured to execute software instructions embodied within the following components;

a program editing component that provides an interface that receives software program actions from a software developer;

a cache point identifying component that identifies one or more points among the received software program actions at which to cache programmatic results related to each point;

a program instrumenting component that instruments the received software program actions to place additional caching actions at the identified cache points;

a cached results store that stores data that is cached for subsequent use by the instrumented software program actions;

a program executing component that provides an execution environment for carrying out the software program actions;

a cache cost component that determines a cost of accessing cached data versus recomputing the data expected to be in the cache; and

a recompute decision component that receives cost information determined by the cache cost component and selects either the cache or recomputation as the source of data for a particular program action.

15. The system of claim 14 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.

16. The system of claim 14 wherein the cache point identifying component identifies 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.

17. The system of claim 14 wherein the program instrumenting component creates 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.

18. The system of claim 14 wherein the cached results store stores data across execution sessions of the software program.

19. The system of claim 14 wherein the cached results store stores data on a computer system remote from the computer system executing the software program.

20. A computer-readable storage medium comprising instructions for controlling a computer system to execute a software program previously instrumented to automatically cache intermediate data, wherein the instructions, upon execution, cause a processor to perform actions comprising:

receiving a request to execute a software program previously instrumented to automatically cache data at identified points within the program;

identifying a cache instruction that is an instrumented point in the program code where the system may either use previously cached results to skip a block of code, or may execute the block of code to produce a result that can then be cached and used to bypass subsequent execution of the block of code;

performing a cost analysis that weighs a cost associated with accessing cached data against a cost associated with computing the data without using the cache;

upon selecting the cache for retrieving data, retrieving cached data associated with the identified cache instruction based on a cache key that identifies a point within the software program that produces particular results stored in the cache; and

advancing the next instruction to be executed of the software program beyond any instructions that can be skipped due to use of the cached data.