JDK-4987722 : Fast array access in constrained loops for numeric computing
  • Type: Enhancement
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: 1.4.2
  • Priority: P4
  • Status: Closed
  • Resolution: Cannot Reproduce
  • OS: windows_xp
  • CPU: x86
  • Submitted: 2004-02-03
  • Updated: 2007-06-06
  • Resolved: 2007-06-06
Description

Name: jl125535			Date: 02/03/2004


A DESCRIPTION OF THE REQUEST :
Heavy-duty numeric computing tasks involving linear algebra matrix operations often take more than 10 times longer in Java than C.  Presumably, it is because of the extra time for array index checking.  Often the important array accesses occur inside of tight loops where the index is bound by the loop constraints to be valid.  So how about have the JVM make this check when entering the loop instead of on each access?  Consider the inner loop of a matrix multiply (full function attached):

     for (int k = 0; k < n; k++) {
             val += m1i[k] * m2j[k];
     }

At run-time, if the JVM detects that n <= m1i.length and n <= m2j.length (and that n and the array lengths are constant), then it can execute a fast version of the loop without array index checking (or null pointer checking, for that matter), possibly even noticing the sequential access and using pointer arithmetic.

This is a JVM optimization and doesn't require or suggest any change to the language or the instruction set, since doing so would allow mischievous code.

JUSTIFICATION :
Drastic improvement is needed to make Java competitive for numeric computing.  Array indexing is a likely opportunity for safe optimization.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Matrix multiplications within 2x of C/C++.
ACTUAL -
Matrix multiplications about 15x of C/C++.

---------- BEGIN SOURCE ----------
    public static void multiplySquare(int n,
                             double[][] m1, double[][] m2, double[][] m3) {
        transposeSquare(m2);
        for (int i = 0; i < n; i++) {
            double m1i[] = m1[i];
            double m3i[] = m3[i];
            for (int j = 0; j < n; j++) {
                double m2j[] = m2[j];
                double val = 0;
                for (int k = 0; k < n; k++) {
                    val += m1i[k] * m2j[k];
                }
                m3i[j] = val;
            }
        }
        transposeSquare(m2);
    }
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Use C/C++.
(Incident Review ID: 232272) 
======================================================================

Comments
EVALUATION > java -version java version "1.7.0-ea" > CC -V CC: Sun C++ 5.8 2005/10/13
2007-06-07

EVALUATION SPARC CC: 11 secs Java: 14 secs x86 CC: 18 secs Java: 6.4 secs SunOS minnesota 5.9 Generic_122300-02 sun4u sparc SUNW,Sun-Blade-2500 Cpus: 2 at 1280 MHz Memory size: 2048 Megabytes > CC -xO4 MultiplySquare.cpp > a.out 11.0: 2D array using array[row][row] > java -server -XX:+PrintCompilation MultiplySquare 1% MultiplySquare$ArrayOfArrays::calc @ 46 (94 bytes) 1 MultiplySquare$ArrayOfArrays::calc (94 bytes) 14.2: 2D array using array[row][row] SunOS foundation 5.10 Generic_125101-05 i86pc i386 i86pc Cpus: 4 at 2393 MHz Memory size: 7744 Megabytes > CC -xO4 MultiplySquare.cpp > a.out 18.0: 2D array using array[row][row] > java -server -XX:+PrintCompilation MultiplySquare 1% MultiplySquare$ArrayOfArrays::calc @ 46 (94 bytes) 1 MultiplySquare$ArrayOfArrays::calc (94 bytes) 6.4: 2D array using array[row][row]
2007-06-06