Elimination of Java array bounds checks in the presence of indirection

ABSTRACT

The Java language specification states that every access to an array needs to be within the bounds of that array; i.e. between 0 and array length 1. Different techniques for different programming languages have been proposed to eliminate explicit bounds checks. Some of these techniques are implemented in off-the-shelf Java Virtual Machines (JVMs). The underlying principle of these techniques is that bounds checks can be removed when a JVM/compiler has enough information to guarantee that a sequence of accesses (e.g. inside a for-loop) is safe (within the bounds). Most of the techniques for the elimination of array bounds checks have been developed for programming languages that do not support multi-threading and/or enable dynamic class loading. These two characteristics make most of these tech niques unsuitable for Java. Techniques developed specifically for Java have not addressed the elimination of array bounds checks in the presence of indirection, that is, when the index is stored in another array (indirection array). With the objective of optimising applications with array indirection, this paper proposes and evaluates three implementation strategies, each implemented as a Java class. The classes provide the functionality of Java arrays of type int so that objects of the classes can be used instead of indirection arrays. Each strategy enables JVMs, when examining only one of these classes at a time, to obtain enough information to remove array bounds checks.

REFERENCES

• 1: Aneesh Aggarwal , Keith H. Randall, Related field analysis, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.214-220, June 2001, Snowbird, Utah, United States
• 2: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 3: Jonathan M. Asuru, Optimization of array subscript range checks, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.2, p.109-118, June 1992 [doi>10.1145/151333.151392]
• 4: Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
• 5: Rastislav Bodík , Rajiv Gupta , Vivek Sarkar, ABCD: eliminating array bounds checks on demand, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.321-333, June 18-21, 2000, Vancouver, British Columbia, Canada
• 6: Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.35-46, November 01-05, 1999, Denver, Colorado, United States
• 7: Ronald F. Boisvert , José Moreira , Michael Philippsen , Roldan Pozo, Java and Numerical Computing, IEEE MultiMedia, v.3 n.2, p.18-24, March 1996
• 8: Ronald F. Boisvert , Roldan Pozo , Karin Remington , Richard F. Barrett , Jack J. Dongarra, Matrix market: a web resource for test matrix collections, Proceedings of the IFIP TC2/WG2.5 working conference on Quality of numerical software: assessment and enhancement, p.125-137, January 1997, Oxford, United Kingdom
• 9: J. M. Bull , L. A. Smith , L. Pottage , R. Freeman, Benchmarking Java against C and Fortran for scientific applications, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.97-105, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376823]
• 10: Wei-Ngan Chin , Eak-Khoon Goh, A reexamination of “Optimization of array subscript range checks”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.217-227, March 1995 [doi>10.1145/201059.201063]
• 11: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 12: Michał Cierniak , Guei-Yuan Lueh , James M. Stichnoth, Practicing JUDO: Java under dynamic optimizations, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.13-26, June 18-21, 2000, Vancouver, British Columbia, Canada
• 13: Robert Fitzgerald , Todd B. Knoblock , Erik Ruf , Bjarne Steensgaard , David Tarditi, Marmot: an optimizing compiler for Java, Software—Practice & Experience, v.30 n.3, p.199-232, Mar.1.2000 [doi>10.1002/(SICI)1097-024X(200003)30:3<199::AID-SPE296>3.0.CO;2-2]
• 14: Sanjay Ghemawat , Keith H. Randall , Daniel J. Scales, Field analysis: getting useful and low-cost interprocedural information, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.334-344, June 18-21, 2000, Vancouver, British Columbia, Canada
• 15: G. H. Golub and C. F. van Loan. Matrix Computations. John Hopkins University Press, 3rd edition, 1996.
• 16: Rajiv Gupta, A fresh look at optimizing array bound checking, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.272-282, June 1990, White Plains, New York, United States
• 17: Rajiv Gupta, Optimizing array bound checks using flow analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.2 n.1-4, p.135-150, March–Dec. 1993 [doi>10.1145/176454.176507]
• 18: Java Grande Forum. Making Java Work for High-End Computing, November 1998. Available at http://www.javagrande.org/reports.htm.
• 19: Java Grande Forum. Interim Java Grande Forum Report, June 1999. Available at http://www.javagrande.org/reports.htm.
• 20: Robert L. Johnston, Numerical Methods: A Software Approach, John Wiley & Sons, Inc., New York, NY, 1982
• 21: Multiarray package. http://jcp.org/jsr/detail/083.jsp.
• 22: Iffat H. Kazi , Howard H. Chen , Berdenia Stanley , David J. Lilja, Techniques for obtaining high performance in Java programs, ACM Computing Surveys (CSUR), v.32 n.3, p.213-240, Sept. 2000 [doi>10.1145/367701.367714]
• 23: Priyadarshan Kolte , Michael Wolfe, Elimination of redundant array subscript range checks, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.270-278, June 18-21, 1995, La Jolla, California, United States
• 24: Mikel Luján , T. L. Freeman , John R. Gurd, OoLALA: an object oriented analysis and design of numerical linear algebra, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.229-252, October 2000, Minneapolis, Minnesota, United States
• 25: M. Luján, J. R. Gurd, and T. L. Freeman. OoLaLa: Transformations for implementations of matrix operations at high abstraction levels. In Proceedings of the 4th Workshop on Parallel Object-Oriented Scientific Computing -- POOSC'01, 2001.
• 26: Victoria Markstein , John Cocke , Peter Markstein, Optimization of range checking, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.114-119, June 23-25, 1982, Boston, Massachusetts, United States
• 27: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 28: S. P. Midkiff , J. E. Moreira , M. Snir, Optimizing array reference checking in Java programs, IBM Systems Journal, v.37 n.3, p.409-453, 1998
• 29: J. E. Moreira, S. P. Midki, and M. Gupta. A standard Java array package for technical computing. In Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, 1999.
• 30: José E. Moreira , Samuel P. Midkiff , Manish Gupta, From flop to megaflops: Java for technical computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.265-295, March 2000 [doi>10.1145/349214.349222]
• 31: J. E. Moreira , S. P. Midkiff , M. Gupta , P. V. Artigas , M. Snir , R. D. Lawrence, Java programming for high-performance numerical computing, IBM Systems Journal, v.39 n.1, p.21-56, January 2000
• 32: José E. Moreira , Samuel P. Midkiff , Manish Gupta , Pedro V. Artigas , Peng Wu , George Almasi, The NINJA project, Communications of the ACM, v.44 n.10, p.102-109, Oct. 2001 [doi>10.1145/383845.383867]
• 33: George C. Necula , Peter Lee, The design and implementation of a certifying compiler, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.333-344, June 17-19, 1998, Montreal, Quebec, Canada
• 34: M. Paleczny, C. Vick, and C. Click. The Java Hotspot server compiler. In Proceedings of the USENIX Symposium on Java Virtual Machine Research and Technology, 2001.
• 35: Radu Rugina , Martin Rinard, Symbolic bounds analysis of pointers, array indices, and accessed memory regions, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.182-195, June 18-21, 2000, Vancouver, British Columbia, Canada
• 36: Mauricio Serrano , Rajesh Bordawekar , Sam Midkiff , Manish Gupta, Quicksilver: a quasi-static compiler for Java, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.66-82, October 2000, Minneapolis, Minnesota, United States
• 37: T. Suganuma , T. Ogasawara , M. Takeuchi , T. Yasue , M. Kawahito , K. Ishizaki , H. Komatsu , T. Nakatani, Overview of the IBM Java just-in-time compiler, IBM Systems Journal, v.39 n.1, p.175-193, January 2000
• 38: Norihisa Suzuki , Kiyoshi Ishihata, Implementation of an array bound checker, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.132-143, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512963]
• 39: George K. Thiruvathukal, Java at Middle Age: Enabling Java for Computational Science, Computing in Science and Engineering, v.4 n.1, p.74-84, January 2002
• 40: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States
• 41: P. Wu, S. P. Midki, J. E. Moreira, and M. Gupta. Improving Java performance through semantic inlining. Technical Report 21313, IBM Research Division, 1998.
• 42: Hongwei Xi , Frank Pfenning, Eliminating array bound checking through dependent types, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.249-257, June 17-19, 1998, Montreal, Quebec, Canada
• 43: Zhichen Xu , Barton P. Miller , Thomas Reps, Safety checking of machine code, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.70-82, June 18-21, 2000, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
      D.3.4 Processors
          Subjects: Optimization; Compilers

General Terms:
Languages, Performance

Keywords:
Java, array bounds check, array indirection