An experimental analysis of self-adjusting computation

ABSTRACT

Dependence graphs and memoization can be used to efficiently update the output of a program as the input changes dynamically. Recent work has studied techniques for combining these approaches to effectively dynamize a wide range of applications. Toward this end various theoretical results were given. In this paper we describe the implementation of a library based on these ideas, and present experimental results on the efficiency of this library on a variety of applications. The results of the experiments indicate that the approach is effective in practice, often requiring orders of magnitude less time than recomputing the output from scratch. We believe this is the first experimental evidence that incremental computation of any type is effective in practice for a reasonably broad set of applications.

REFERENCES

• 1: Martín Abadi , Butler Lampson , Jean-Jacques Lévy, Analysis and caching of dependencies, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.83-91, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 2: Umut A. Acar , Guy Blelloch , Robert Harper, Self-adjusting computation, Carnegie Mellon University, Pittsburgh, PA, 2005
• 3: U. A. Acar, G. E. Blelloch, M. Blume, R. Harper, and K. Tangwongsan. A library for self-adjusting computation. In ACM SIGPLAN Workshop on ML, 2005.
• 4: Umut A. Acar , Guy E. Blelloch , Robert Harper, Adaptive functional programming, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.247-259, January 16-18, 2002, Portland, Oregon
• 5: Umut A. Acar , Guy E. Blelloch , Robert Harper, Selective memoization, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.14-25, January 15-17, 2003, New Orleans, Louisiana, USA
• 6: Umut A. Acar , Guy E. Blelloch , Robert Harper , Jorge L. Vittes , Shan Leung Maverick Woo, Dynamizing static algorithms, with applications to dynamic trees and history independence, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 7: U. A. Acar, G. E. Blelloch, K. Tangwongsan, and J. Vittes. Kinetic algorithms via self-adjusting computation. Technical Report CMU-CS-06-115, Department of Computer Science, Carnegie Mellon University, March 2006.
• 8: U. A. Acar, G. E. Blelloch, and J. L. Vittes. An experimental analysis of change propagation in dynamic trees. In Workshop on Algorithm Engineering and Experimentation, 2005.
• 9: C. Bradford Barber , David P. Dobkin , Hannu Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.469-483, Dec. 1996 [doi>10.1145/235815.235821]
• 10: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 11: Michael A. Bender , Richard Cole , Erik D. Demaine , Martin Farach-Colton , Jack Zito, Two Simplified Algorithms for Maintaining Order in a List, Proceedings of the 10th Annual European Symposium on Algorithms, p.152-164, September 17-21, 2002
• 12: Gerth Stølting Brodal , Riko Jacob, Dynamic Planar Convex Hull, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.617-626, November 16-19, 2002
• 13: Magnus Carlsson, Monads for incremental computing, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.26-35, October 04-06, 2002, Pittsburgh, PA, USA
• 14: T. M. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete and Computational Geometry, 16:361--368, 1996.
• 15: Timothy M. Chan, Dynamic planar convex hull operations in near-logarithmic amortized time, Journal of the ACM (JACM), v.48 n.1, p.1-12, Jan. 2001 [doi>10.1145/363647.363652]
• 16: Y.-J. Chiang and R. Tamassia. Dynamic algorithms in computational geometry. Proceedings of the IEEE, 80(9):1412--1434, 1992.
• 17: Alan Demers , Thomas Reps , Tim Teitelbaum, Incremental evaluation for attribute grammars with application to syntax-directed editors, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-116, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567544]
• 18: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 19: D. Eppstein, Z. Galil, and G. F. Italiano. Dynamic graph algorithms. In M. J. Atallah, editor, Algorithms and Theory of Computation Handbook, chapter 8. CRC Press, 1999.
• 20: R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132--133, 1972.
• 21: Allan Heydon , Roy Levin , Yuan Yu, Caching function calls using precise dependencies, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.311-320, June 18-21, 2000, Vancouver, British Columbia, Canada
• 22: David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
• 23: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 24: Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Discovering auxiliary information for incremental computation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-170, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237769]
• 25: Yanhong A. Liu , Scott D. Stoller , Tim Teitelbaum, Static caching for incremental computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.546-585, May 1998 [doi>10.1145/291889.291895]
• 26: J. McCarthy. A Basis for a Mathematical Theory of Computation. In P. Braffort and D. Hirschberg, editors, Computer Programming and Formal Systems, pages 33- 70. North-Holland, Amsterdam, 1963.
• 27: D. Michie. Memo functions and machine learning. Nature, 218:19--22, 1968.
• 28: M. H. Overmans and J. van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23:166--204, 1981.
• 29: W. Pugh. Incremental computation via function caching. PhD thesis, Department of Computer Science, Cornell University, August 1988.
• 30: W. Pugh , T. Teitelbaum, Incremental computation via function caching, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.315-328, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75305]
• 31: G. Ramalingam , Thomas Reps, A categorized bibliography on incremental computation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.502-510, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158710]
• 32: Raimund Seidel, Linear programming and convex hulls made easy, Proceedings of the sixth annual symposium on Computational geometry, p.211-215, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98570]
• 33: Michael Ian Shamos, Computational geometry., 1978
• 34: R. Wenger. Randomized quickhull. Algorithmica, 17(3):322--329, 1997.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.0 General

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Algorithms, Languages, Performance

Keywords:
computational geometry, dynamic algorithms, dynamic dependence graphs, memorization, performance, self-adjusting computation