More Web Proxy on the site http://driver.im/

research-article

Incremental resource usage analysis

Authors:

Jesús Correas,

Germán Puebla,

Guillermo Román-DíezAuthors Info & Claims

PEPM '12: Proceedings of the ACM SIGPLAN 2012 workshop on Partial evaluation and program manipulation

Pages 25 - 34

https://doi.org/10.1145/2103746.2103754

Published: 23 January 2012 Publication History

Abstract

The aim of incremental global analysis is, given a program, its analysis results and a series of changes to the program, to obtain the new analysis results as efficiently as possible and, ideally, without having to (re-)analyze fragments of code which are not affected by the changes. incremental analysis can significantly reduce both the time and the memory requirements of analysis. This paper presents an incremental resource usage analysis for a sequential Java-like language. Our main contributions are (1) a multi-domain incremental fixed-point algorithm which can be used by all global pre-analyses required to infer the cost (including class, sharing, cyclicity, constancy, and size analyses), and which takes care of propagating dependencies among such domains, and (2) a novel form of cost summaries which allows us to incrementally reconstruct only those components of cost functions affected by the change. Experimental results in the COSTA system show that the proposed incremental analysis performs very efficiently in practice.

References

[1]

E. Albert, P. Arenas, S. Genaim, and G. Puebla. Closed-Form Upper Bounds in Static Cost Analysis. Journal of Automated Reasoning, 46(2):161--203, February 2011.

Digital Library

[2]

E. Albert, P. Arenas, S. Genaim, G. Puebla, and D. Ramírez. From Object Fields to Local Variables: a Practical Approach to Field-Sensitive Analysis. In Proc. of SAS'10, volume 6337 of LNCS, pages 100--116. Springer, 2010.

Digital Library

[3]

E. Albert, P. Arenas, S. Genaim, G. Puebla, and D. Zanardini. Cost Analysis of Object-Oriented Bytecode Programs. Theoretical Computer Science, 413(1):142--159, 2012.

Digital Library

[4]

E. Albert, P. Arenas, S. Genaim, and D. Zanardini. Task-Level Analysis for a Language with Async-Finish parallelism. In Proc. of LCTES'11, pages 21--30. ACM Press, 2011.

Digital Library

[5]

E. Albert, S. Genaim, and M. Gómez-Zamalloa. Parametric Inference of Memory Requirements for Garbage Collected Languages. In Proc. of ISMM'10, pages 121--130. ACM Press, 2010.

Digital Library

[6]

P. Cousot and R. Cousot. Abstract Interpretation: a Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Proc. of POPL'77, pages 238--252. ACM Press, 1977.

Digital Library

[7]

P. Cousot and R. Cousot. Modular Static Program Analysis, invited paper. In Compiler Construction, 2002.

Digital Library

[8]

I. Dillig, T. Dillig, and A. Aiken. Sound, complete and scalable path-sensitive analysis. In PLDI, pages 270--280. ACM, 2008.

Digital Library

[9]

C. A. Lakos G. Lewis. Towards incremental analysis. In Workshop on Formal Methods for Dependable Systems (FMDS), 1998.

[10]

S. Genaim and F. Spoto. Constancy Analysis. In Marieke Huisman, editor, 10th Workshop on Formal Techniques for Java-like Programs, July 2008.

[11]

S. Gulwani, K. K. Mehra, and T. M. Chilimbi. Speed: Precise and Efficient Static Estimation of Program Computational Complexity. In Proc. of POPL'09, pages 127--139. ACM, 2009.

Digital Library

[12]

G. Hedin. An object-oriented notation for attribute grammars. In Proc. of ECOOP'89, pages 329--345, 1989.

[13]

M. Hermenegildo, G. Puebla, K. Marriott, and P. Stuckey. Incremental Analysis of Constraint Logic Programs. ACM TOPLAS, 22(2):187--223, March 2000.

Digital Library

[14]

M. Hofmann J. Hoffmann, K. Aehlig. Multivariate Amortized Resource Analysis. In Proc. of POPL'11, pages 357--370. ACM, 2011.

Digital Library

[15]

M. Kero, P. Pietrzak, and Nordlander J. Live Heap Space Bounds for Real-Time Systems. In Proc. of APLAS'10, volume 6461 of LNCS, pages 287--303. Springer, 2010.

Digital Library

[16]

Francesco Logozzo. Practical verification for the working programmer with codecontracts and abstract interpretation - (invited talk). In Proc. of VMCAI'11, volume 6538 of LNCS, pages 19--22. Springer, 2011.

Digital Library

[17]

A. Miné. Field-Sensitive Value Analysis of Embedded C Programs with Union Types and Pointer Arithmetics. In Proc. of LCTES'06, pages 54--63. ACM, 2006.

Digital Library

[18]

Apache Commons Project. http://commons.apache.org/.

[19]

T. W. Reps, S. Horwitz, and S. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proc. POPL'95, pages 49--61, 1995.

Digital Library

[20]

S. Rossignoli and F. Spoto. Detecting Non-Cyclicity by Abstract Compilation into Boolean Functions. In Proc. of VMCAI'06, volume 3855 of LNCS, pages 95--110. Springer, 2006.

Digital Library

[21]

S. Secci and F. Spoto. Pair-Sharing Analysis of Object-Oriented Programs. In Proc. of SAS'05, volume 3672 of LNCS, pages 320--335. Springer, 2005.

Digital Library

[22]

F. Spoto, F. Mesnard, and É. Payet. A Termination Analyzer for Java Bytecode based on Path-Length. ACM Transactions on Programming Languages and Systems, 32(3), 2010.

Digital Library

[23]

Fausto Spoto and Thomas P. Jensen. Class analyses as abstract interpretations of trace semantics. ACM Trans. Program. Lang. Syst., 25(5):578--630, 2003.

Digital Library

[24]

JOlden Suite. http://www-ali.cs.umass.edu/DaCapo/benchmarks.html.

[25]

T. A. Wagner and S. L. Graham. Incremental analysis of real programming languages. In Proc. of PLDI'97, pages 31--43, 1997.

Digital Library

[26]

B. Wegbreit. Mechanical Program Analysis. Comm. of the ACM, 18(9), 1975.

Digital Library

Cited By

Harianto KWang FAbouzeid M(2024)Enhancing Incremental Dataflow Analysis in an IDE2024 IEEE 24th International Conference on Software Quality, Reliability, and Security Companion (QRS-C)10.1109/QRS-C63300.2024.00055(383-390)Online publication date: 1-Jul-2024
https://doi.org/10.1109/QRS-C63300.2024.00055
Morton JMaier PTrinder P(2016)JIT-Based Cost Analysis for Dynamic Program TransformationsElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2016.12.012330:C(5-25)Online publication date: 10-Dec-2016
https://dl.acm.org/doi/10.1016/j.entcs.2016.12.012
Braberman VGarbervetsky DHym SYovine S(2014)Summary-based inference of quantitative bounds of live heap objectsScience of Computer Programming10.1016/j.scico.2013.11.03692(56-84)Online publication date: Oct-2014
https://doi.org/10.1016/j.scico.2013.11.036
Show More Cited By

Index Terms

Incremental resource usage analysis
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
2. Theory of computation

Recommendations

Incremental analysis of constraint logic programs

Global analyzers traditionally read and analyze the entire program at once, in a nonincremental way. However, there are many situations which are not well suited to this simple model and which instead require reanalysis of certain parts of a program ...
A multi-domain incremental analysis engine and its application to incremental resource analysis

The aim of incremental analysis is, given a program, its analysis results, and a series of changes to the program, to obtain the new analysis results as efficiently as possible and, ideally, without having to (re-)analyze fragments of code which are not ...
Scalable and incremental software bug detection
ESEC/FSE 2013: Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering

An important, but often neglected, goal of static analysis for detecting bugs is the ability to show defects to the programmer quickly. Unfortunately, existing static analysis tools scale very poorly, or are shallow and cannot find complex ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM '12: Proceedings of the ACM SIGPLAN 2012 workshop on Partial evaluation and program manipulation

January 2012

172 pages

ISBN:9781450311182

DOI:10.1145/2103746

Program Chairs:
Oleg Kiselyov
Monterey, CA., USA
,
Simon Thompson
University of Kent, UK

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 January 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL '12

Sponsor:

SIGPLAN

POPL '12: The 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 23 - 24, 2012

Pennsylvania, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
142
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Harianto KWang FAbouzeid M(2024)Enhancing Incremental Dataflow Analysis in an IDE2024 IEEE 24th International Conference on Software Quality, Reliability, and Security Companion (QRS-C)10.1109/QRS-C63300.2024.00055(383-390)Online publication date: 1-Jul-2024
https://doi.org/10.1109/QRS-C63300.2024.00055
Morton JMaier PTrinder P(2016)JIT-Based Cost Analysis for Dynamic Program TransformationsElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2016.12.012330:C(5-25)Online publication date: 10-Dec-2016
https://dl.acm.org/doi/10.1016/j.entcs.2016.12.012
Braberman VGarbervetsky DHym SYovine S(2014)Summary-based inference of quantitative bounds of live heap objectsScience of Computer Programming10.1016/j.scico.2013.11.03692(56-84)Online publication date: Oct-2014
https://doi.org/10.1016/j.scico.2013.11.036
Wong PAlbert EMuschevici RProença JSchäfer JSchlatte R(2012)The ABS tool suiteInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-012-0250-114:5(567-588)Online publication date: 1-Oct-2012
https://dl.acm.org/doi/10.1007/s10009-012-0250-1
Albert EAlonso-Blas DArenas PCorreas JFlores-Montoya AGenaim SGómez-Zamalloa MMasud APuebla GRojas JRomán-Díez GZanardini D(2012)Automatic Inference of Bounds on Resource ConsumptionRevised Lectures of the 11th International Symposium on Formal Methods for Components and Objects - Volume 786610.1007/978-3-642-40615-7_4(119-144)Online publication date: 24-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-40615-7_4
Albert EArenas PGenaim SGómez-Zamalloa MPuebla G(2012)Automatic inference of resource consumption boundsProceedings of the 18th international conference on Logic for Programming, Artificial Intelligence, and Reasoning10.1007/978-3-642-28717-6_1(1-11)Online publication date: 11-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28717-6_1

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents