An improved replacement strategy for function caching

ABSTRACT

Function caching is the technique of remembering previous function calls and avoiding the cost of recomputing them. Function caching provides a simple way of implementing dynamic programming algorithms and can provide a facility for incremental computation. Previous discussions of function caching have generally relied on the user to purge items from the function cache or have proposed a strategy such as least-recently-used without any analysis of the appropriateness of that strategy. We describe a formal model that allows us to describe the potential of a function cache and use that model to develop a practical cache replacement strategy that performs substantially better than currently used strategies. Benchmarks show that in use in an incremental theorem prover, our caching strategy produces almost a factor of four improvement in running time over a system running without function caching and almost a factor of two improvement in running time over a system using a standard cache replacement strategy.

REFERENCES

• All78: John Allen, Anatomy of LISP, McGraw-Hill, Inc., New York, NY, 1978
• Coh79: Norman H. Cohen, Characterization and elimination of redundancy in recursive programs, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.143-157, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567766]
• FWW76: Daniel P. Friedman , David S. Wise , Mitchell Wand, Recursive programming through table look-up, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.85-89, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806326]
• Hil76: J. Hilden, Elimination of recursive calls using a small table of 'randomly' selected function values, BIT, Vo116 no. 1, pp60-73 (1976)
• Hug85: John Hughes, Lazy memo-functions, Proc. of a conference on Functional programming languages and computer architecture, p.129-146, January 1985, Nancy, France
• KS86: Robert M. Keller , M. R. Sleep, Applicative caching, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.88-108, Jan. 1986 [doi>10.1145/5001.5004]
• Mic68: Donald Michie, "Memo" Functions and .Machine Learning, Nature, No. 218, pp19-22 (April 1968)
• MC85: Jack Mostow and Donald Cohen, Automating Program Speedup by Deciding What to Cache, Proc. of the Ninth International Joint Conference on Artificial Intelligence, 18-23 August, 1985, Vol. 1, pp 165-172.
• Pug88: William Worthington Pugh, Jr., Incremental computation and the incremental evaluation of functional programs, 1988
• RT84: Thomas Reps , Tim Teitelbaum, The synthesizer generator, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.42-48, April 1984
• Rob87: A. D. Robison, The Illinois functional programming interpreter, Papers of the Symposium on Interpreters and interpretive techniques, p.64-73, June 24-26, 1987, St. Paul, Minnesota, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Algorithms, Design, Languages, Performance