United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
JDK-4987722 : Fast array access in constrained loops for numeric computing

Details
Type:
Enhancement
Submit Date:
2004-02-03
Status:
Closed
Updated Date:
2007-06-06
Project Name:
JDK
Resolved Date:
2007-06-06
Component:
hotspot
OS:
windows_xp
Sub-Component:
compiler
CPU:
x86
Priority:
P4
Resolution:
Cannot Reproduce
Affected Versions:
1.4.2
Fixed Versions:

Related Reports

Sub Tasks

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



Hardware and Software, Engineered to Work Together