Martin Hofmann
Institut für Informatik
Ludwig-Maximilians-Universität München
Germany
Amortized resource analysis
Abstract
Resource analysis aims at automatically determining and upper bound on the resource usage of a program as a function of its input size. Resources in this context can be runtime, heap- and stack size, number of occurrences of certain events, etc.
The amortized approach to resource analysis works by associating "credits" with elements of data structures and to "pay" for each consumption of resource from the credits currently available. In this way composite programs and programs with intermediate data structures can be analysed more conveniently than would otherwise be the case.
Amortization was introduced by Tarjan in the 70s in the context of manual complexity analyis of algorithms. More recently, it has been used for type-based automatic resource analysis.
The course describes the key concepts with simple examples and then moves on to survey some recent papers, notably the inference of multivariate polynomial resource bounds for functional programs and a type-based resource analysis of Java-like object-oriented programs.
Course materials
- M. Hofmann. Amortized resource analysis. Slides. [pdf]
- M. Hofmann, S. Jost. Static prediction of heap space usage for first-order functional programs. In Proc. of 30th Ann. ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, POPL '03 (New Orleans, LA, Jan. 2003), pp. 185-197. ACM Press, 2003. [doi link]
- M. Hofmann, D. Rodriguez. Efficient type-checking for amortised heap-space analysis. In E. Grädel, R. Kahle, eds., Proc. of 23rd Int. Wksh. on Computer Science Logic, CSL 2009 (Coimbra, Sept. 2009), v. 5771 of Lect. Notes in Comput. Sci., pp. 317-331. Springer, 2009. [doi link]
- J. Hoffmann, K. Aehlig, M. Hofmann. Multivariate amortized resource analysis. In Proc. of 38th Ann. ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, POPL '11 (Austin, TX, Jan. 2011), pp. 357-370. ACM Press, 2011. [doi link]
Last changed
March 7, 2011 13:27 EET
by
local organizers, ewscs11(at)cs.ioc.ee
EWSCS'11 page:
//cs.ioc.ee/ewscs/2011/