Umut A. Acar
Guy E. Blelloch
Matthias Blume
Robert Harper
Skip Abstract Section
Abstract
Recent work on adaptive functional programming (AFP) developed techniques for writing programs that can respond to modifications to their data by performing change propagation. To achieve this, executions of programs are represented with dynamic dependence graphs (DDGs) that record data dependences and control dependences in a way that a change-propagation algorithm can update the computation as if the program were from scratch, by re-executing only the parts of the computation affected by the changes. Since change-propagation only re-executes parts of the computation, it can respond to certain incremental modifications asymptotically faster than recomputing from scratch, potentially offering significant speedups. Such asymptotic speedups, however, are rare: for many computations and modifications, change propagation is no faster than recomputing from scratch.
In this article, we realize a duality between dynamic dependence graphs and memoization, and combine them to give a change-propagation algorithm that can dramatically increase computation reuse. The key idea is to use DDGs to identify and re-execute the parts of the computation that are affected by modifications, while using memoization to identify the parts of the computation that remain unaffected by the changes. We refer to this approach as self-adjusting computation. Since DDGs are imperative, but (traditional) memoization requires purely functional computation, reusing computation correctly via memoization becomes a challenge. We overcome this challenge with a technique for remembering and reusing not just the results of function calls (as in conventional memoization), but their executions represented with DDGs. We show that the proposed approach is realistic by describing a library for self-adjusting computation, presenting efficient algorithms for realizing the library, and describing and evaluating an implementation. Our experimental evaluation with a variety of applications, ranging from simple list primitives to more sophisticated computational geometry algorithms, shows that the approach is effective in practice: compared to recomputing from-scratch; self-adjusting programs respond to small modifications to their data orders of magnitude faster.
- Abadi, M., Lampson, B. W., and Lévy, J.-J. 1996. Analysis and caching of dependencies. In Proceedings of the International Conference on Functional Programming. 83--91. Google Scholar
Digital Library
- Acar, U. A. 2005. Self-adjusting computation. Ph.D. dissertation, Department of Computer Science, Carnegie Mellon University. Google ScholarDigital Library
- Acar, U. A. 2009. Self-adjusting computation (an overview). In Proceedings of ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation. ACM, New York. Google ScholarDigital Library
- Acar, U. A., Ahmed, A., and Blume, M. 2008a. Imperative self-adjusting computation. In Proceedings of the 25th Annual ACM Symposium on Principles of Programming Languages. ACM, New York. Google ScholarDigital Library
- Acar, U. A., Blelloch, G. E., Tangwongsan, K., and Türkoğlu, D. 2008b. Robust kinetic convex hulls in 3D. In Proceedings of the 16th Annual European Symposium on Algorithms. Google ScholarDigital Library
- Acar, U. A., Blume, M., and Donham, J. 2007a. A consistent semantics of self-adjusting computation. In Proceedings of the 16th Annual European Symposium on Programming (ESOP). Google ScholarDigital Library
- Acar, U. A., Ihler, A., Mettu, R., and Sümer, O. 2007b. Adaptive Bayesian Inference. In Neural Information Processing Systems (NIPS).Google Scholar
- Acar, U. A., Blelloch, G. E., Blume, M., Harper, R., and Tangwongsan, K. 2006a. A library for self-adjusting computation. Electron. Notes Theor. Comput. Sci. 148, 2. Google ScholarDigital Library
- Acar, U. A., Blelloch, G. E., Blume, M., and Tangwongsan, K. 2006b. An experimental analysis of self-adjusting computation. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York. Google ScholarDigital Library
- Acar, U. A., Blelloch, G. E., and Harper, R. 2006c. Adaptive functional programming. ACM Trans. Program. Lang. Syst. 28, 6, 990--1034. Google ScholarDigital Library
- Acar, U. A., Blelloch, G. E., Harper, R., Vittes, J. L., and Woo, M. 2004. Dynamizing static algorithms with applications to dynamic trees and history independence. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. ACM, New York. Google ScholarDigital Library
- Acar, U. A., Blelloch, G. E., and Harper, R. 2003. Selective memoization. In Proceedings of the 30th Annual ACM Symposium on Principles of Programming Languages. ACM, New York. Google ScholarDigital Library
- Acar, U. A., Blelloch, G. E., and Harper, R. 2002. Adaptive functional programming. In Proceedings of the 29th Annual ACM Symposium on Principles of Programming Languages. 247--259. Google ScholarDigital Library
- Agarwal, P. K., Guibas, L. J., Edelsbrunner, H., Erickson, J., Isard, M., Har-Peled, S., Hershberger, J., Jensen, C., Kavraki, L., Koehl, P., Lin, M., Manocha, D., Metaxas, D., Mirtich, B., Mount, D., Muthukrishnan, S., Pai, D., Sacks, E., Snoeyink, J., Suri, S., and Wolefson, O. 2002. Algorithmic issues in modeling motion. ACM Comput. Surv. 34, 4, 550--572. Google ScholarDigital Library
- Alexandron, G., Kaplan, H., and Sharir, M. 2005. Kinetic and dynamic data structures for convex hulls and upper envelopes. In Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, vol. 3608, Springer, Berlin, 269--281. Google ScholarDigital Library
- Alstrup, S., Holm, J., de Lichtenberg, K., and Thorup, M. 1997. Minimizing diameters of dynamic trees. In Automata, Languages and Programming, 270--280. Google ScholarDigital Library
- Alstrup, S., Holm, J., de Lichtenberg, K., and Thorup, M. 2003. Maintaining information in fully-dynamic trees with top trees. The Computing Research Repository (CoRR){cs.DS/0310065}. Google ScholarDigital Library
- Barber, C. B., Dobkin, D. P., and Huhdanpaa, H. 1996. The Quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 4, 469--483. Google ScholarDigital Library
- Basch, J., Guibas, L. J., and Hershberger, J. 1999. Data structures for mobile data. J. Algorithms 31, 1, 1--28. Google ScholarDigital Library
- Bellman, R. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.Google Scholar
- Bender, M. A., Cole, R., Demaine, E. D., Farach-Colton, M., and Zito, J. 2002. Two simplified algorithms for maintaining order in a list. In Proceedings of the 10th European Symposium on Algorithms (ESA 2002). Lecture Notes in Computer Science, vol. 2461, 219--223. Google ScholarDigital Library
- Bentley, J. L. and Saxe, J. B. 1980. Decomposable searching problems I: Static-to-dynamic transformation. J. Algorithms 1, 4, 301--358.Google ScholarCross Ref
- Bhattacharya, B. K. and Sen, S. 1997. On a simple, practical, optimal, output-sensitive randomized planar convex hull algorithm. J. Algorithms 25, 1, 177--193. Google ScholarDigital Library
- Boissonnat, J.-D. and Yvinec, M. 1998. Algorithmic Geometry. Cambridge Press. Google ScholarDigital Library
- Brodal, G. S. and Jacob, R. 2002. Dynamic planar convex hull. In Proceedings of the 43 rd Annual IEEE Symposium on Foundations of Computer Science. 617--626. Google ScholarDigital Library
- Carlsson, M. 2002. Monads for incremental computing. In Proceedings of the 7th ACM SIGPLAN International Conference on Functional Programming. ACM, New York, 26--35. Google ScholarDigital Library
- Chan, T. M. 1996. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete Computat. Geometry 16, 361--368.Google ScholarDigital Library
- Chan, T. M. 1999. Dynamic planar convex hull operations in near-logarithmic amortized time. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 92--99. Google ScholarDigital Library
- Chiang, Y.-J. and Tamassia, R. 1992. Dynamic algorithms in computational geometry. Proc. IEEE 80, 9, 1412--1434.Google ScholarCross Ref
- Cohen, R. F. and Tamassia, R. 1991. Dynamic expression trees and their applications. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 52--61. Google ScholarDigital Library
- Demers, A., Reps, T., and Teitelbaum, T. 1981. Incremental evaluation of attribute grammars with application to syntax-directed editors. In Proceedings of the 8th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, 105--116. Google ScholarDigital Library
- Dietz, P. F. and Sleator, D. D. 1987. Two algorithms for maintaining order in a list. In Proceedings of the 19th ACM Symposium on Theory of Computing. ACM, New York, 365--372. Google ScholarDigital Library
- Doyle, J. 1987. A truth maintenance system. In Readings in Nonmonotonic Reasoning, Morgan Kaufmann, Palo Alto, CA, 259--279. Google ScholarDigital Library
- Eppstein, D., Galil, Z., and Italiano, G. F. 1999. Dynamic graph algorithms. In Algorithms and Theory of Computation Handbook, CRC Press, Ch. 8.Google Scholar
- Eppstein, D., Galil, Z., Italiano, G. F., and Nissenzweig, A. 1997. Sparsification—A technique for speeding up dynamic graph algorithms. J. ACM 44, 5, 669--696. Google ScholarDigital Library
- Field, J. 1991. Incremental reduction in the lambda calculus and related reduction systems. Ph.D. dissertation, Department of Computer Science, Cornell University. Google ScholarDigital Library
- Field, J. and Teitelbaum, T. 1990. Incremental reduction in the lambda calculus. In Proceedings of the ACM Conference on LISP and Functional Programming. ACM, New York, 307--322. Google ScholarDigital Library
- Frederickson, G. N. 1985. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14, 781--798.Google ScholarDigital Library
- Frederickson, G. N. 1997. A data structure for dynamically maintaining rooted trees. J. Algorithms 24, 1, 37--65. Google ScholarDigital Library
- Graham, R. L. 1972. An efficient algorithm for determining the convex hull of a finete planar set. Inform. Process. Lett. 1, 132--133.Google ScholarCross Ref
- Guibas, L. 2004. Modeling motion. In Handbook of Discrete and Computational Geometry, 2nd ed., J. Goodman and J. O'Rourke, Eds. Chapman and Hall/CRC, 1117--1134.Google Scholar
- Guibas, L. and Russel, D. 2004. An empirical comparison of techniques for updating Delaunay triangulations. In Proceedings of the 20th Annual Symposium on Computational Geometry (SCG'04). ACM Press, New York, 170--179. Google ScholarDigital Library
- Guibas, L. J. 1998. Kinetic data structures: A state of the art report. In Proceedings of the Third Workshop on the Algorithmic Foundations of Robotics (WAFR'98). 191--209. Google ScholarDigital Library
- Hammer, M. A. and Acar, U. A. 2008. Memory management for self-adjusting computation. In Proceedings of the 7th International Symposium on Memory Management (ISMM'08). 51--60. Google ScholarDigital Library
- Hammer, M. A., Acar, U. A., and Chen, Y. 2009. CEAL: A C-based language for self-adjusting computation. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York. Google ScholarDigital Library
- Henzinger, M. R. and King, V. 1997. Maintaining minimum spanning trees in dynamic graphs. In Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP'97). Springer, Berlin, 594--604. Google ScholarDigital Library
- Henzinger, M. R. and King, V. 1999. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46, 4, 502--516. Google ScholarDigital Library
- Heydon, A., Levin, R., and Yu, Y. 2000. Caching function calls using precise dependencies. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 311--320. Google ScholarDigital Library
- Holm, J., de Lichtenberg, K., and Thorup, M. 2001. Polylogarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48, 4, 723--760. Google ScholarDigital Library
- Hoover, R. 1987. Incremental graph evaluation. Ph.D. dissertation, Department of Computer Science, Cornell University. Google ScholarDigital Library
- Jones, R. E. 1996. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, New York. (With a chapter on distributed garbage collection by R. Lins.) Google ScholarDigital Library
- Kirkpatrick, D. G. and Seidel, R. 1986. The ultimate planar convex hull algorithm. SIAM J. Comput. 15, 1, 287--299. Google ScholarDigital Library
- Knuth, D. E. 1998. The Art of Computer Programming: Sorting and Searching, vol. 3, 2nd ed. Addison-Wesley, Ch. 6, 481--489. Google ScholarDigital Library
- Ley-Wild, R., Acar, U. A., and Fluet, M. 2009. A cost semantics for self-adjusting computation. In Proceedings of the 26th Annual ACM Symposium on Principles of Programming Languages. ACM, New York. Google ScholarDigital Library
- Ley-Wild, R., Fluet, M., and Acar, U. A. 2008. Compiling self-adjusting programs with continuations. In Proceedings of the International Conference on Functional Programming. Google ScholarDigital Library
- Liu, Y. A., Stoller, S., and Teitelbaum, T. 1998. Static caching for incremental computation. ACM Trans. Program. Lang. Syst. 20, 3, 546--585. Google ScholarDigital Library
- McAllester, D. 1990. Truth maintenance. In Proceedings of the 8th National Conference on Artificial Intelligence. 1109--1116.Google ScholarDigital Library
- McCarthy, J. 1963. A basis for a mathematical theory of computation. In Computer Programming and Formal Systems, P. Braffort and D. Hirschberg, Eds. North-Holland, Amsterdam, 33--70.Google Scholar
- Michie, D. 1968. “Memo” functions and machine learning. Nature 218, 19--22.Google ScholarCross Ref
- Mulmuley, K. 1994. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
- Overmars, M. H. and van Leeuwen, J. 1981. Maintenance of configurations in the plane. J. Comput. Syst. Sci. 23, 166--204.Google ScholarCross Ref
- Pugh, W. and Teitelbaum, T. 1989. Incremental computation via function caching. In Proceedings of the 16th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, 315--328. Google ScholarDigital Library
- Radzik, T. 1998. Implementation of dynamic trees with in-subtree operations. ACM J. Exper. Algor. 3, 9. Google ScholarDigital Library
- Ramalingam, G. and Reps, T. 1993. A categorized bibliography on incremental computation. In Proceedings of the 20th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, 502--510. Google ScholarDigital Library
- Reps, T. 1982. Optimal-time incremental semantic analysis for syntax-directed editors. In Proceedings of the 9th Annual Symposium on Principles of Programming Languages, 169--176. Google ScholarDigital Library
- Russel, D. 2007. Kinetic data structures in practice. Ph.D. dissertation, Department of Computer Science, Stanford University. Google ScholarDigital Library
- Russel, D., Karavelas, M. I., and Guibas, L. J. 2007. A package for exact kinetic data structures and sweepline algorithms. Comput. Geom. Theory Appl. 38, 1-2, 111--127. Google ScholarDigital Library
- Saxe, J. B. and Bentley, J. L. 1979. Transforming static data structures to dynamic structures (abridged version). In Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Science. 148--168. Google ScholarDigital Library
- Shamos, M. I. 1978. Computational geometry. Ph.D. dissertation, Department of Computer Science, Yale University. Google ScholarDigital Library
- Shankar, A. and Bodik, R. 2007. DITTO: Automatic incrementalization of data structure invariant checks (in Java). In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York. Google ScholarDigital Library
- Sleator, D. D. and Tarjan, R. E. 1983. A data structure for dynamic trees. J. Comput. Syst. Sci. 26, 3, 362--391. Google ScholarDigital Library
- Sleator, D. D. and Tarjan, R. E. 1985. Self-adjusting binary search trees. J. ACM 32, 3, 652--686. Google ScholarDigital Library
- Stallman, R. M. and Sussman, G. J. 1977. Forward reasoning and dependency-directed back-tracking in a system for computer-aided circuit analysis. Art. Intell. 9, 2, 135--196.Google ScholarCross Ref
- Sundaresh, R. S. and Hudak, P. 1991. Incremental compilation via partial evaluation. In Conference Record of the 18th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, 1--13.Google Scholar
- Tarjan, R. and Werneck, R. 2005a. Dynamic trees in practice. In Proceeding of the 6th Workshop on Experimental Algorithms (WEA'07). 80-93. Google ScholarDigital Library
- Tarjan, R. and Werneck, R. 2005b. Self-adjusting top trees. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. Google ScholarDigital Library
- Tarjan, R. E. 1997. Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Mathemat. Program. 78, 167--177. Google ScholarDigital Library
- Wegman, M. N. and Carter, L. 1979. New classes and applications of hash functions. In Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science. 175--182. Google ScholarDigital Library
- Wenger, R. 1997. Randomized quickhull. Algorithmica 17, 3, 322--329.Google ScholarCross Ref
- Yellin, D. M. and Strom, R. E. 1991. INC: A language for incremental computations. ACM Trans. Program. Lang. Syst. 13, 2, 211--236. Google ScholarDigital Library
Index Terms
- An experimental analysis of self-adjusting computation
Recommendations
Efficient Parallel Self-Adjusting Computation
SPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and ArchitecturesSelf-adjusting computation is an approach for automatically producing dynamic algorithms from static ones. It works by tracking control and data dependencies, and propagating changes through the dependencies when making an update. Extensively studied in ...
Imperative self-adjusting computation
POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languagesSelf-adjusting computation enables writing programs that can automatically and efficiently respond to changes to their data (e.g., inputs). The idea behind the approach is to store all data that can change over time in modifiable references and to let ...
An experimental analysis of self-adjusting computation
PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and ImplementationDependence 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 ...
Comments