Practical extraction techniques for Java

ABSTRACT

Reducing application size is important for software that is distributed via the internet, in order to keep download times manageable, and in the domain of embedded systems, where applications are often stored in (Read-Only or Flash) memory. This paper explores extraction techniques such as the removal of unreachable methods and redundant fields, inlining of method calls, and transformation of the class hierarchy for reducing application size. We implemented a number of extraction techniques in Jax, an application extractor for Java, and evaluated their effectiveness on a set of large Java applications. We found that, on average, the class file archives for these benchmarks were reduced to 37.5% of their original size. Modeling dynamic language features such as reflection, and extracting software distributions other than complete applications requires additional user input. We present a uniform approach for supplying this input that relies on MEL, a modular specification language. We also discuss a number of issues and challenges associated with the extraction of embedded systems applications.

REFERENCES

• 1: Ole Agesen, Concrete type inference: delivering object-oriented applications, Stanford University, Stanford, CA, 1996
• 2: Ole Agesen , David Ungar, Sifting out the gold: delivering compact applications from an exploratory object-oriented programming environment, Proceedings of the ninth annual conference on Object-oriented programming systems, language, and applications, p.355-370, October 23-28, 1994, Portland, Oregon, United States
• 3: Gerald Aigner , Urs Hölzle, Eliminating Virtual Function Calls in C++ Programs, Proceedings of the 10th European Conference on Object-Oriented Programming, p.142-166, July 08-12, 1996
• 4: Ken Arnold , James Gosling , David Holmes, The Java Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 5: David Francis Bacon , Susan L. Graham, Fast and effective optimization of statically typed object-oriented languages, 1997
• 6: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• 7: Quetzalcoatl Bradley , R. Nigel Horspool , Jan Vitek, JAZZ: an efficient compressed format for Java archive files, Proceedings of the 1998 conference of the Centre for Advanced Studies on Collaborative research, p.7, November 30-December 03, 1998, Toronto, Ontario, Canada
• 8: Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304113]
• 9: Brad Calder , Dirk Grunwald, Reducing indirect function call overhead in C++ programs, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.397-408, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177973]
• 10: Dustin R. Callaway, Inside Servlets: Server-Side Programming for the Java Platform with Other, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 11: Yih-Farn Chen , Emden R. Gansner , Eleftherios Koutsofios, A C++ Data Model Supporting Reachability Analysis and Dead Code Detection, IEEE Transactions on Software Engineering, v.24 n.9, p.682-694, September 1998 [doi>10.1109/32.713323]
• 12: Lars Ræder Clausen , Ulrik Pagh Schultz , Charles Consel , Gilles Muller, Java bytecode compression for low-end embedded systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.471-489, May 2000 [doi>10.1145/353926.353933]
• 13: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.139-149, May 01-04, 1999, Atlanta, Georgia, United States
• 14: De Sutter, B. 2002. Compactie van programma's na het linken. Ph.D. thesis, Gent University. In Dutch.
• 15: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Sifting out the mud: low level C++ code reuse, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 16: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere , Saumya Debray, Combining Global Code and Data Compaction, Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems, p.29-38, August 2001, Snow Bird, Utah, United States
• 17: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 18: Saumya K. Debray , William Evans , Robert Muth , Bjorn De Sutter, Compiler techniques for code compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.378-415, March 2000 [doi>10.1145/349214.349233]
• 19: Digitalk Inc. 1993. Smalltalk/V for win32 Programming. Digitalk Inc. Chapter 17: Object Libraries and Library Builder.
• 20: Eisma, A. 2001. Feedback directed ahead-of-time compilation for embedded Java applications. In Java Optimization Strategies for Embedded Systems, U. Assmann, Ed. Genova, Italy, 105--112. Workshop held at ETAPS'01.
• 21: Jens Ernst , William Evans , Christopher W. Fraser , Todd A. Proebsting , Steven Lucco, Code compression, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.358-365, June 16-18, 1997, Las Vegas, Nevada, United States
• 22: Fowler, M. 1999. Refactoring. Addison-Wesley.
• 23: Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.117-121, June 17-22, 1984, Montreal, Canada
• 24: David Grove , Greg DeFouw , Jeffrey Dean , Craig Chambers, Call graph construction in object-oriented languages, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.108-124, October 05-09, 1997, Atlanta, Georgia, United States
• 25: R. Nigel Horspool , Jason Corless, Tailored compression of Java class files, Software—Practice & Experience, v.28 n.12, p.1253-1268, Oct. 1998 [doi>10.1002/(SICI)1097-024X(1998100)28:12<1253::AID-SPE200>3.0.CO;2-8]
• 26: IBM Corporation 1995. IBM Smalltalk User's Guide, Version 3.0 ed. IBM Corporation. Chapter 36: Introduction to Packaging, Chapter 37: Simple Packaging, Chapter 38: Advanced Packaging.
• 27: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java Language Specification, Second Edition: The Java Series, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 28: Michael Franz , Thomas Kistler, Slim binaries, Communications of the ACM, v.40 n.12, p.87-94, Dec. 1997 [doi>10.1145/265563.265576]
• 29: Thomas Kistler , Michael Franz, A Tree-Based Alternative to Java Byte-Codes, International Journal of Parallel Programming, v.27 n.1, p.21-33, Feb. 1999 [doi>10.1023/A:1018740018601]
• 30: Chandra Krintz , Brad Calder , Han Bok Lee , Benjamin G. Zorn, Overlapping execution with transfer using non-strict execution for mobile programs, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.159-169, October 02-07, 1998, San Jose, California, United States
• 31: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 32: Hemant D. Pande , Barbara G. Ryder, Data-Flow-Based Virtual Function Resolution, Proceedings of the Third International Symposium on Static Analysis, p.238-254, September 24-26, 1996
• 33: ParcPlace Systems 1992. ParcPlace Smalltalk, ObjectWorks Release 4.1 ed. ParcPlace Systems. Section 16: Deploying an Application, Section 28: Binary Object Streaming Service.
• 34: Patrice Pominville , Feng Qian , Raja Vallée-Rai , Laurie J. Hendren , Clark Verbrugge, A Framework for Optimizing Java Using Attributes, Proceedings of the 10th International Conference on Compiler Construction, p.334-354, April 02-06, 2001
• 35: William Pugh, Compressing Java class files, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.247-258, May 01-04, 1999, Atlanta, Georgia, United States
• 36: Derek Rayside , Kostas Kontogiannis, Extracting Java Library Subsets for Deployment on Embedded Systems, Proceedings of the Third European Conference on Software Maintenance and Reengineering, p.102, March 03-05, 1999
• 37: Derek Rayside , Evan Mamas , Erik Hons, Compact Java binaries for embedded systems, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.9, November 08-11, 1999, Mississauga, Ontario, Canada
• 38: Gregg Rothermel , Mary Jean Harrold, A safe, efficient regression test selection technique, ACM Transactions on Software Engineering and Methodology (TOSEM), v.6 n.2, p.173-210, April 1997 [doi>10.1145/248233.248262]
• 39: Barbara G. Ryder , Frank Tip, Change impact analysis for object-oriented programs, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.46-53, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379661]
• 40: Robert W. Scheifler, An analysis of inline substitution for a structured programming language, Communications of the ACM, v.20 n.9, p.647-654, Sept. 1977 [doi>10.1145/359810.359830]
• 41: Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France [doi>10.1145/263699.263703]
• 42: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 43: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 44: Sun Microsystems 1997. JavaBeans, Version 1.01 ed. Sun Microsystems, 2550 Garcia Avenue, Mountain View, CA 94043.
• 45: Sun Microsystems 1999. Java 2 {S}oftware Development Kit, Version 1.2.2 ed. Sun Microsystems, 2550 Garcia Avenue, Mountain View, CA 94043. Available at http://java.sun.com/docs/books/ tutorial/ext/security/sealing.html.
• 46: Vijay Sundaresan , Laurie Hendren , Chrislain Razafimahefa , Raja Vallée-Rai , Patrick Lam , Etienne Gagnon , Charles Godin, Practical virtual method call resolution for Java, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.264-280, October 2000, Minneapolis, Minnesota, United States
• 47: Peter F. Sweeney , Frank Tip, A study of dead data members in C++ applications, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.324-332, June 17-19, 1998, Montreal, Quebec, Canada
• 48: Peter F. Sweeney , Frank Tip, Extracting library-based object-oriented applications, Proceedings of the 8th ACM SIGSOFT international symposium on Foundations of software engineering: twenty-first century applications, p.98-107, November 06-10, 2000, San Diego, California, United States
• 49: Thies, M. 1999a. A closer look at inter-library dependencies in Java-software. In Java-Informations-Tage 1999 (JIT'99). Informatik Aktuell. Springer Verlag.
• 50: Thies, M. 1999b. Static compositional analysis of libraries in support of dynamic optimization. Technischer Bericht tr-ri-99-210, University of Paderborn. Aug.
• 51: Frank Tip , Jong-Deok Choi , John Field , G. Ramalingam, Slicing class hierarchies in C++, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.179-197, October 06-10, 1996, San Jose, California, United States
• 52: Frank Tip , Chris Laffra , Peter F. Sweeney , David Streeter, Practical experience with an application extractor for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.292-305, November 01-05, 1999, Denver, Colorado, United States
• 53: Frank Tip , Jens Palsberg, Scalable propagation-based call graph construction algorithms, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.281-293, October 2000, Minneapolis, Minnesota, United States
• 54: Frank Tip , Peter F. Sweeney, Class hierarchy specialization, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.271-285, October 05-09, 1997, Atlanta, Georgia, United States
• 55: Frank Tip , Peter F. Sweeney, Class hierarchy specialization, Acta Informatica, v.36 n.12, p.927-982, Jan. 2000 [doi>10.1007/PL00013298]
• 56: Ayal Zaks , Vitaly Feldman , Nava Aizikowitz, Sealed calls in Java packages, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-92, October 2000, Minneapolis, Minnesota, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Java
      D.3.4 Processors
          Subjects: Compilers; Optimization

General Terms:
Algorithms, Experimentation, Languages, Measurement, Performance

Keywords:
Application extraction, call graph construction, class hierarchy transformation, packaging, whole-program analysis