AUTOMATIC AND TRANSPARENT MEMOIZATION

• US 20090049421A1
• Filed: 08/15/2007
• Published: 02/19/2009
• Est. Priority Date: 08/15/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Beckman, Brian C., Meijer, Henricus Johannes Maria, van Gogh, Jeffrey
• Granted Patent: US 8,108,848 B2
• Time in Patent Office: Days
• US Class Current: 717/100
• CPC Class Codes: G06F 9/4484 Executing subprograms
• CPC Class Codes: G06F 9/4486 Formation of subprogram jump address

Abstract

Functions are memoized automatically and transparently. Memoized code can be injected automatically within a program to facilitate efficient and/or expeditious execution thereof, among other things. The memoized code can intercept calls to an original function and return values in accordance with the code. Accordingly, callers of the function need not do anything special and can invoke the function without knowledge of it being memoized.

Claims

1. A memoization system, comprising:

an analysis component that analyzes program code; and

a memo component that automatically and transparently memoizes a function in response to the analysis via code injection and function override.

2. The system of claim 1, further comprising a component that removes cached values employed by a memorized function in accordance with a policy.

3. The system of claim 1, further comprising a component that pre-fetches and loads one or more values in a storage construct employed by a memorized function.

4. The system of claim 1, further comprising a component that removes function memoization.

5. The system of claim 1, the memorized function includes a component for identifying whether values should be re-computed or retrieved from cache, when available.

6. The system of claim 1, further comprising an export component that persists memoization storage construct data to a computer readable medium.

7. The system of claim 1, further comprising an import component the loads data from a computer readable medium into a memoization storage construct.

8. The system of claim 1, the memo component transforms the function into an idempotent function.

9. The system of claim 1, the analysis component identifies if memoization is to be turned on or off as a function of online and/or offline network connectivity.

10. The system of claim 1, further comprising a component that adds logging and/or security functionality.

11. The system of claim 1, the analysis and memo component form part of a compiler.

12. A method of computer program interpretation, comprising:

receiving a first function; and

overriding a previously specified second function at runtime with the first function, which memoizes the second function.

13. The method of claim 12, further comprising recording values of previous calls in an instance method field.

14. The method of claim 12, further comprising computing a unique key to facilitate location of a previously generated value stored in a storage construct as a function of one or more arguments associated with a call to the first function.

15. The method of claim 14, further comprising employing one of a specified, default or inferred key generation function.

16. The method of claim 14, further comprising returning a previously generated value located in the construct.

17. The method of claim 12, further comprising employing backpatching to detect or create cycles.

18. A computer readable medium having a computer code stored thereon comprising:

a first function; and

a second dynamically injected function that follows, overrides and memoizes the first function.

19. The computer readable medium of claim 18, the second function includes a hash function for storage and lookup of memoized values.

20. The computer readable medium of claim 19, the first and second functions are denoted in a scripting language.