skip to main content
10.1145/1251535.1251548acmconferencesArticle/Chapter ViewAbstractPublication PagespasteConference Proceedingsconference-collections
Article

Dynamic purity analysis for java programs

Published: 13 June 2007 Publication History

Abstract

The pure methods in a program are those that exhibit functional or side effect free behaviour, a useful property in many contexts. However, existing purity investigations present primarily staticresults. We perform a detailed examination of dynamic method purityin Java programs using a JVM-based analysis. We evaluate multiple purity definitions that range from strong to weak, consider purity forms specific to dynamic execution, and accomodate constraintsimposed by an example consumer application, memoization. We show that while dynamic method purity is actually fairly consistent between programs, examining pure invocation counts and the percentage of the byte code instruction stream contained within some pure method reveals great variation. We also show that while weakening purity definitions exposes considerable dynamic purity, consumer requirements can limitthe actual utility of this information.

References

[1]
U. A. Acar, G. E. Blelloch, and R. Harper. Selective memoization. In POPL'03: Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 14--25, Jan. 2003.
[2]
S. Artzi, A. Kiezun, D. Glasser, and M. D. Ernst. Combined static and dynamic mutability analysis. Technical Report MIT-CSAIL-TR-2007-020, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, Mar. 2007.
[3]
S. Balakrishnan and G. S. Sohi. Program demultiplexing: Data-flow based speculative parallelization of methods in sequential programs. In ISCA'06: Proceedings of the 33rd International Symposium on Computer Architecture, pages 302--313, June 2006.
[4]
J. P. Banning. An efficient way to find the side effects of procedure calls and the aliases of variables. In POPL'79: Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pages 29--41, Jan. 1979.
[5]
E. Bruneton, R. Lenglet, and T. Coupaye. ASM: A code manipulation tool to implement adaptable systems. In JC'02: Proceedings of the ACM SIGOPS France Journées Composants 2002: Systèmes à Composants Adaptables et Extensibles, Nov. 2002. http://asm.objectweb.org/.
[6]
L. Burdy, Y. Cheon, D. Cok, M. Ernst, J. Kiniry, G. T. Leavens, K. R. M. Leino, and E. Poll. An overview of JML tools and applications. STTT: International Journal on Software Tools for Technology Transfer, 7(3):212--232, June 2005.
[7]
M. Burke. An interval-based approach to exhaustive and incremental interprocedural data-flow analysis. TOPLAS: ACM Transactions on Programming Languages and Systems, 12(3):341--395, July 1990.
[8]
N. Cataño and M. Huisman. Chase: A static checker for JML's assignable clause. In VMCAI'03: Proceedings of the 4th International Conference on Verification, Model Checking, and Abstract Interpretation, volume 2575 of LNCS: Lecture Notes in Computer Science, pages 26--40, Jan. 2003.
[9]
L. R. Clausen. A Java bytecode optimizer using side-effect analysis. Concurrency: Practice and Experience, 9(11):1031--1045, Dec. 1997.
[10]
K. D. Cooper and K. Kennedy. Interprocedural side-effect analysis in linear time. In PLDI'88: Proceedings of the ACM SIGPLAN 1988 Conference on Programming Language Design and Implementation, pages 57--66, June 1988.
[11]
V. Dallmeier, C. Lindig, and A. Zeller. Dynamic purity analysis for Java programs, Feb. 2007. http://www.st.cs.uni-sb.de/ models/jdynpur/.
[12]
J. Dean, D. Grove, and C. Chambers. Optimization of object-oriented programs using static class hierarchy analysis. In ECOOP'95: Proceedings of the 9th European Conference on Object-Oriented Programming, volume 952 of LNCS: Lecture Notes in Computer Science, pages 77--101, Aug. 1995.
[13]
B. Demsky and M. Rinard. Role-based exploration of object-oriented programs. In ICSE'02: Proceedings of the 24th International Conference on Software Engineering, pages 313--324, May 2002.
[14]
B. Dufour, K. Driesen, L. Hendren, and C. Verbrugge. Dynamic metrics for Java. In OOPSLA'03: Proceedings of the 18th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 149--168, Oct. 2003.
[15]
G. N. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM Journal on Computing, 26(2):484--538, Apr. 1997.
[16]
E. M. Gagnon. A Portable Research Framework for the Execution of Java Bytecode. PhD thesis, School of Computer Science, McGill University, Montréal, Québec, Canada, Dec. 2002.
[17]
A. Heydon, R. Levin, and Y. Yu. Caching function calls using precise dependencies. In PLDI'00: Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, pages 311--320, June 2000.
[18]
P. Jouvelot and D. Gifford. Algebraic reconstruction of types and effects. In POPL'91: Proceedings of the 18th ACM SIGPLANSIGACT Symposium on Principles of Programming Languages, pages 303--310, Jan. 1991.
[19]
A. Le, O. Lhoták, and L. Hendren. Using inter-procedural side-effect information in JIT optimizations. In CC'05: Proceedings of the 14th International Conference on Compiler Construction, volume 3443 of LNCS: Lecture Notes in Computer Science, pages 287--304, Apr. 2005.
[20]
G. T. Leavens, A. L. Baker, and C. Ruby. Preliminary design of JML: A behavioral interface specification language for Java. SIGSOFT Software Engineering Notes, 31(3):1--38, May 2006.
[21]
O. Lhoták and L. J. Hendren. Context-sensitive points-to analysis: Is it worth it? In CC'06: Proceedings of the 15th International Conference on Compiler Construction, volume 3923 of LNCS: Lecture Notes in Computer Science, pages 47--64, Mar. 2006.
[22]
Y. A. Liu and T. Teitelbaum. Systematic derivation of incremental programs. Science of Computer Programming, 24(1):1--39, Feb. 1995.
[23]
A. Milanova, A. Rountev, and B. G. Ryder. Parameterized object sensitivity for points-to analysis for Java. ACM Transactions on Software Engineering and Methodology, 14(1):1--41, Jan. 2005.
[24]
K. Mulmuley. Randomized multidimensional search trees (extended abstract): Dynamic sampling. In SCG'91: Proceedings of the 7th Annual Symposium on Computational Geometry, pages 121--131, June 1991.
[25]
C. J. F. Pickett and C. Verbrugge. Return value prediction in a Java virtual machine. In VPW2: Proceedings of the 2nd Value-Prediction and Value-Based Optimization Workshop, pages 40--47, Oct. 2004.
[26]
C. J. F. Pickett and C. Verbrugge. Software thread level speculation for the Java language and virtual machine environment. In LCPC'05: Proceedings of the 18th International Workshop on Languages and Compilers for Parallel Computing, volume 4339 of LNCS: Lecture Notes in Computer Science, pages 304--318, Oct. 2005.
[27]
W. Pugh and T. Teitelbaum. Incremental computation via function caching. In POPL'89: Proceedings of the 16th ACM SIGPLANSIGACT Symposium on Principles of Programming Languages, pages 315--328, Jan. 1989.
[28]
F. Qian, L. J. Hendren, and C. Verbrugge. A comprehensive approach to array bounds check elimination for Java. In CC'02: Proceedings of the 11th International Conference on Compiler Construction, volume 2304 of LNCS: Lecture Notes in Computer Science, pages 325--342, Apr. 2002.
[29]
C. Razafimahefa. A study of side-effect analyses for Java. Master's thesis, School of Computer Science, McGill University, Montréal, Québec, Canada, Dec. 1999.
[30]
A. Rountev. Precise identification of side-effect-free methods in Java. In ICSM'04: Proceedings of the 20th IEEE International Conference on Software Maintenance, pages 82--91, Sept. 2004.
[31]
A. Sǎlcianu and M. Rinard. Purity and side effect analysis for Java programs. In VMCAI'05: Proceedings of the 6th International Conference on Verification, Model Checking, and Abstract Interpretation, volume 3385 of LNCS: Lecture Notes in Computer Science, pages 199--215, Jan. 2005. http://jppa.sourceforge.net.
[32]
D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. In STOC'81: Proceedings of the 13th Annual ACM Symposium on Theory of Computing, pages 114--122, May 1981.
[33]
Standard Performance Evaluation Corporation. SPEC JVM Client98 benchmark suite, June 1998. http://www.spec.org/jvm98/.
[34]
B. Steensgaard. Points-to analysis in almost linear time. In POPL'96: Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 32--41, Jan. 1996.
[35]
R. Vallée-Rai. Soot: A Java bytecode optimization framework. Master's thesis, School of Computer Science, McGill University, Montréal, Québec, Canada, July 2000. http://www.sable.mcgill.ca/soot/.
[36]
J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In OOPSLA'99: Proceedings of the 14th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 187--206, Nov. 1999.

Cited By

View all
  • (2021)A methodology and framework for software memoization of functionsProceedings of the 18th ACM International Conference on Computing Frontiers10.1145/3457388.3458668(93-101)Online publication date: 11-May-2021
  • (2021)Toward Speeding up Mutation Analysis by Memoizing Expensive Methods2021 IEEE/ACM 43rd International Conference on Software Engineering: New Ideas and Emerging Results (ICSE-NIER)10.1109/ICSE-NIER52604.2021.00023(71-75)Online publication date: May-2021
  • (2018)A unified lattice model and framework for purity analysesProceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering10.1145/3238147.3238226(340-350)Online publication date: 3-Sep-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PASTE '07: Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering
June 2007
96 pages
ISBN:9781595935953
DOI:10.1145/1251535
  • General Chairs:
  • Manuvir Das,
  • Dan Grossman
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Java
  2. dynamic analysis
  3. escape analysis
  4. memoization
  5. purity
  6. side effects
  7. software metrics

Qualifiers

  • Article

Conference

PASTE07

Acceptance Rates

Overall Acceptance Rate 57 of 159 submissions, 36%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)1
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)A methodology and framework for software memoization of functionsProceedings of the 18th ACM International Conference on Computing Frontiers10.1145/3457388.3458668(93-101)Online publication date: 11-May-2021
  • (2021)Toward Speeding up Mutation Analysis by Memoizing Expensive Methods2021 IEEE/ACM 43rd International Conference on Software Engineering: New Ideas and Emerging Results (ICSE-NIER)10.1109/ICSE-NIER52604.2021.00023(71-75)Online publication date: May-2021
  • (2018)A unified lattice model and framework for purity analysesProceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering10.1145/3238147.3238226(340-350)Online publication date: 3-Sep-2018
  • (2018)Mining Semantic Loop IdiomsIEEE Transactions on Software Engineering10.1109/TSE.2018.283204844:7(651-668)Online publication date: 1-Jul-2018
  • (2016)On the prevalence of function side effects in general purpose open source software systems2016 IEEE 14th International Conference on Software Engineering Research, Management and Applications (SERA)10.1109/SERA.2016.7516139(141-148)Online publication date: Jun-2016
  • (2016)On the Prevalence of Function Side Effects in General Purpose Open Source Software SystemsComputer and Information Science10.1007/978-3-319-40171-3_11(149-166)Online publication date: 17-Jun-2016
  • (2015)Tracking down performance variation against source code evolutionACM SIGPLAN Notices10.1145/2936313.281671851:2(129-139)Online publication date: 21-Oct-2015
  • (2015)Performance problems you can fix: a dynamic analysis of memoization opportunitiesACM SIGPLAN Notices10.1145/2858965.281429050:10(607-622)Online publication date: 23-Oct-2015
  • (2015)Tracking down performance variation against source code evolutionProceedings of the 11th Symposium on Dynamic Languages10.1145/2816707.2816718(129-139)Online publication date: 21-Oct-2015
  • (2015)Performance problems you can fix: a dynamic analysis of memoization opportunitiesProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814290(607-622)Online publication date: 23-Oct-2015
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media