Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

This article presents a symbolic static analysis for computing parametric upper bounds of the number of simultaneously live objects of sequential Java-like programs. Inferring the peak amount of irreclaimable objects is the cornerstone for analyzing potential heap-memory consumption of stand-alone applications or libraries. The analysis builds method-level summaries quantifying the peak number of live objects and the number of escaping objects. Summaries are built by resorting to summaries of their callees. The usability, scalability and precision of the technique is validated by successfully predicting the object heap usage of a medium-size, real-life application which is significantly larger than other previously reported case-studies. © 2013 Elsevier B.V.

Registro:

Documento: Artículo
Título:Summary-based inference of quantitative bounds of live heap objects
Autor:Braberman, V.; Garbervetsky, D.; Hym, S.; Yovine, S.
Filiación:Departamento de Computación, FCEyN, UBA, Argentina
CONICET, Argentina
LIFL, Université Lille 1, CNRS, France
Palabras clave:Heap memory requirements; Quantitative analysis; Resource consumption; Chemical analysis; Computer programming; Software engineering; Case-studies; Escaping objects; Java-like programs; Memory requirements; Quantitative bounds; Real-life applications; Resource consumption; Standalone applications; Static analysis
Año:2014
Volumen:92
Número:PART A
Página de inicio:56
Página de fin:84
DOI: http://dx.doi.org/10.1016/j.scico.2013.11.036
Título revista:Science of Computer Programming
Título revista abreviado:Sci Comput Program
ISSN:01676423
CODEN:SCPGD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01676423_v92_nPARTA_p56_Braberman

Referencias:

  • Albert, E., Arenas, P., Genaim, S., Puebla, G., Zanardini, D., Costa: Design and implementation of a cost and termination analyzer for Java bytecode (2007) FMCO, 5382, pp. 113-132. , Frank S. de Boer, Marcello M. Bonsangue, Susanne Graf, Willem P. de Roever, Lect. Notes Comput. Sci. Springer 978-3-540-92187-5
  • Albert, E., Genaim, S., Gómez-Zamalloa, M., Live Heap Space Analysis for Languages with Garbage Collection, pp. 129-138. , [31] ISBN 978-1-60558-347-1
  • Albert, E., Genaim, S., Gómez-Zamalloa, M., Parametric inference of memory requirements for garbage collected languages (2010) ISMM, pp. 121-130. , Jan Vitek, Doug Lea, ACM 978-1-4503-0054-4
  • Albert, E., Arenas, P., Genaim, S., Puebla, G., Closed-form upper bounds in static cost analysis (2011) J. Autom. Reason., 46 (2), pp. 161-203
  • Albert, E., Correas, J., Puebla, G., Román-Díez, G., Incremental resource usage analysis (2012) PEPM, pp. 25-34. , Oleg Kiselyov, Simon Thompson, ACM 978-1-4503-1118-2
  • Albert, E., Genaim, S., Gómez-Zamalloa, M., Heap space analysis for garbage collected languages (2013) Sci. Comput. Program., 78 (9), pp. 1427-1448
  • Barnett, M., Fändrich, M., Garbervetsky, D., Logozzo, F., Annotations for (more) precise points-to analysis (2007) Proceedings of the 2nd International Workshop on Aliasing, Confinement and Ownership in Object-Oriented Programming (IWACO'07), pp. 11-18
  • Beringer, L., Hofmann, M., Momigliano, A., Shkaravska, O., Automatic certification of heap consumption (2004) LPAR, 3452, pp. 347-362. , Franz Baader, Andrei Voronkov, Lect. Notes Comput. Sci. Springer 3-540-25236-3
  • Blanc, R., Henzinger, T.A., Hottelier, T., Kovács, L., Abc: Algebraic bound computation for loops (2010) LPAR (Dakar), 6355, pp. 103-118. , Edmund M. Clarke, Andrei Voronkov, Lect. Notes Comput. Sci. Springer 978-3-642-17510-7
  • Braberman, V.A., Garbervetsky, D., Yovine, S., A static analysis for synthesizing parametric specifications of dynamic memory consumption (2006) J. Object Technol., 5 (5), pp. 31-58
  • Braberman, V.A., Fernández, F.J., Garbervetsky, D., Yovine, S., Parametric Prediction of Heap Memory Requirements, pp. 141-150. , [30] ISBN 978-1-60558-134-7
  • Cachera, D., Jensen, T.P., Jobin, A., Kirchner, F., Inference of polynomial invariants for imperative programs: A farewell to Gröbner bases (2012) SAS, 7460, pp. 58-74. , Antoine Miné, David Schmidt, Lect. Notes Comput. Sci. Springer 978-3-642-33124-4
  • Cahoon, B., McKinley, K.S., Data flow analysis for software prefetching linked data structures in Java (2001) IEEE PACT, pp. 280-291. , IEEE Computer Society 0-7695-1363-8
  • Chin, W.-N., Nguyen, H.H., Popeea, C., Qin, S., Analysing Memory Resource Bounds for Low-level Programs, pp. 151-160. , [30] ISBN 978-1-60558-134-7
  • Clauss, P., Fernández, F.J., Garbervetsky, D., Verdoolaege, S., Symbolic polynomial maximization over convex sets and its application to memory requirement estimation (2009) IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 17 (8), pp. 983-996
  • Cook, B., Gupta, A., Magill, S., Rybalchenko, A., Simsa, J., Singh, S., Vafeiadis, V., Finding heap-bounds for hardware synthesis (2009) FMCAD, pp. 205-212. , IEEE 978-1-4244-4966-8
  • Courbot, A., Grimaud, G., Vandewalle, J.-J., Efficient off-board deployment and customization of virtual machine-based embedded systems (2010) ACM Trans. Embed. Comput. Syst., 9 (3)
  • Cytron, R., Ferrante, J., Rosen, B.K., Wegman, M.N., Zadeck, F.K., An efficient method of computing static single assignment form (1989) POPL, pp. 25-35. , ACM Press 0-89791-294-2
  • Ernst, M.D., Perkins, J.H., Guo, P.J., McCamant, S., Pacheco, C., Tschantz, M.S., Xiao, C., The Daikon system for dynamic detection of likely invariants (2007) Sci. Comput. Program., 69 (13), pp. 35-45
  • Garbervetsky, D., (2007) Parametric Specification of Dynamic Memory Utilization, , PhD thesis Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires
  • Garbervetsky, D., Yovine, S., Braberman, V.A., Rouaux, M., Taboada, A., Quantitative dynamic-memory analysis for Java (2011) Concurr. Comput., Pract. Exp., 23 (14), pp. 1665-1678
  • Gulwani, S., Zuleger, F., The reachability-bound problem (2010) PLDI, pp. 292-304. , Benjamin G. Zorn, Alexander Aiken, ACM 978-1-4503-0019-3
  • Gulwani, S., Jain, S., Koskinen, E., Control-flow refinement and progress invariants for bound analysis (2009) PLDI, pp. 375-385. , Michael Hind, Amer Diwan, ACM 978-1-60558-392-1
  • Havelund, K., Pressburger, T., Model checking Java programs using Java PathFinder (2000) Int. J. Softw. Tools Technol. Transf., 2 (4), pp. 366-381. , ISSN 1433-2779
  • Hoffmann, J., Aehlig, K., Hofmann, M., Multivariate amortized resource analysis (2011) POPL, pp. 357-370. , Thomas Ball, Mooly Sagiv, ACM 978-1-4503-0490-0
  • Hofmann, M., Jost, S., Static prediction of heap space usage for first-order functional programs (2003) POPL, pp. 185-197. , Alex Aiken, Greg Morrisett, ACM 1-58113-628-5
  • Hofmann, M., Jost, S., Type-based amortised heap-space analysis (2006) ESOP, 3924, pp. 22-37. , Peter Sestoft, Lect. Notes Comput. Sci. Springer 3-540-33095-X
  • Hofmann, M., Rodriguez, D., Efficient type-checking for amortised heap-space analysis (2009) CSL, 5771, pp. 317-331. , Erich Grädel, Reinhard Kahle, Lect. Notes Comput. Sci. Springer 978-3-642-04026-9
  • Hofmann, M., Rodriguez, D., Automatic type inference for amortised heap-space analysis (2013) ESOP, 7792, pp. 593-613. , Matthias Felleisen, Philippa Gardner, Lect. Notes Comput. Sci. Springer 978-3-642-37035-9
  • Jones, R.E., Blackburn, S.M., (2008) Proceedings of the 7th International Symposium on Memory Management, , ISMM 2008, Tucson, AZ, USA, June 7-8, 2008 ACM 978-1-60558-134-7
  • Kolodner, H., Steele, Jr.G.L., (2009) Proceedings of the 8th International Symposium on Memory Management, , ISMM 2009, Dublin, Ireland, June 19-20, 2009 ACM 978-1-60558-347-1
  • (2000) J2ME Building Blocks for Mobile Devices, , Sun Microsystems May
  • Nguyen, T., Kapur, D., Weimer, W., Forrest, S., Using dynamic analysis to discover polynomial and array invariants (2012) ICSE, pp. 683-693. , Martin Glinz, Gail C. Murphy, Mauro Pezzè, IEEE 978-1-4673-1067-3
  • Nimmer, J.W., Ernst, M.D., Static verification of dynamically detected program invariants: Integrating Daikon and ESC/Java (2001) Electron. Notes Theor. Comput. Sci., 55 (2), pp. 255-276
  • Salagnac, G., Rippert, C., Yovine, S., Semi-automatic region-based memory management for real-time Java embedded systems (2007) RTCSA, pp. 73-80. , IEEE Computer Society
  • Salcianu, A., Rinard, M.C., Pointer and escape analysis for multithreaded programs (2001) PPOPP, pp. 12-23. , Michael T. Heath, Andrew Lumsdaine, ACM 1-58113-346-4
  • Unnikrishnan, L., Stoller, S.D., Parametric Heap Usage Analysis for Functional Programs, pp. 139-148. , [31] ISBN 978-1-60558-347-1
  • Verdoolaege, S., Isl: An integer set library for the polyhedral model (2010) ICMS, 6327, pp. 299-302. , Komei Fukuda, Joris van der Hoeven, Michael Joswig, Nobuki Takayama, Lect. Notes Comput. Sci. Springer 978-3-642-15581-9
  • Vivien, F., Rinard, M.C., Incrementalized pointer and escape analysis (2001) PLDI, pp. 35-46. , Michael Burke, Mary Lou Soffa, ACM 1-58113-414-2
  • Wolfram, S., (2003) The Mathematica Book, , fifth edition Wolfram Media 1-57955-022-3

Citas:

---------- APA ----------
Braberman, V., Garbervetsky, D., Hym, S. & Yovine, S. (2014) . Summary-based inference of quantitative bounds of live heap objects. Science of Computer Programming, 92(PART A), 56-84.
http://dx.doi.org/10.1016/j.scico.2013.11.036
---------- CHICAGO ----------
Braberman, V., Garbervetsky, D., Hym, S., Yovine, S. "Summary-based inference of quantitative bounds of live heap objects" . Science of Computer Programming 92, no. PART A (2014) : 56-84.
http://dx.doi.org/10.1016/j.scico.2013.11.036
---------- MLA ----------
Braberman, V., Garbervetsky, D., Hym, S., Yovine, S. "Summary-based inference of quantitative bounds of live heap objects" . Science of Computer Programming, vol. 92, no. PART A, 2014, pp. 56-84.
http://dx.doi.org/10.1016/j.scico.2013.11.036
---------- VANCOUVER ----------
Braberman, V., Garbervetsky, D., Hym, S., Yovine, S. Summary-based inference of quantitative bounds of live heap objects. Sci Comput Program. 2014;92(PART A):56-84.
http://dx.doi.org/10.1016/j.scico.2013.11.036