Fast array access

[Chris]

I'm writing code that performs mathematical calculations on large arrays.
The code is slower than C, because Java performs array bounds checking on
every access. The performance difference is substantial on large arrays.

Does anyone know of a way around this problem? What I'm thinking is that
there might be a JVM or some native libraries out there that can provide
"unsafe" arrays.

 

[David Hilsee]

I'm writing code that performs mathematical calculations on large arrays.
The code is slower than C, because Java performs array bounds checking on
every access. The performance difference is substantial on large arrays.

Does anyone know of a way around this problem? What I'm thinking is that
there might be a JVM or some native libraries out there that can provide
"unsafe" arrays.

I know of no libraries, native or otherwise, that provide "unsafe" arrays.
An "unsafe" array is dangerous and using one could cause the JVM to fail.
Writing an "unsafe" array class whose C implementation is exposed using a
JNI interface would be pointless because accessing the JNI code would have
more overhead than the check that you are trying to avoid. If you wish to
gain performance that is comparable to a C program and there are certain
portions of the code that are too slow in Java, then you may want to
consider migrating a reasonable portion of that code to a native JNI
implementation. When I say a "reasonable portion," I mean a section of code
that does a fair amount of work. That will make the overhead of invoking
the native code less noticeable.

 

[Liz]

I know of no libraries, native or otherwise, that provide "unsafe" arrays.
An "unsafe" array is dangerous and using one could cause the JVM to fail.
Writing an "unsafe" array class whose C implementation is exposed using a
JNI interface would be pointless because accessing the JNI code would have
more overhead than the check that you are trying to avoid. If you wish to
gain performance that is comparable to a C program and there are certain
portions of the code that are too slow in Java, then you may want to
consider migrating a reasonable portion of that code to a native JNI
implementation. When I say a "reasonable portion," I mean a section of code
that does a fair amount of work. That will make the overhead of invoking
the native code less noticeable.

Theoretically, if the JVM can tell that the array index cannot get
out of range it can skip the check, e.g.

for(i=0; i<array.length; i++) {
// do it
}

Maybe someone can check if it does.

 

[David Hilsee]

Theoretically, if the JVM can tell that the array index cannot get
out of range it can skip the check, e.g.

for(i=0; i<array.length; i++) {
// do it
}

Maybe someone can check if it does.

Thanks for bringing this up. This is a theoretical optimization that is
brought up alot when bounds checking is being discussed. I have never
attempted to verify that this optimization is used in practice. I assumed
that the OP knew about it, so he should take note if he didn't. I also
assumed that the JVM was not performing this optimization because he said
that the array bounds checking was causing it to be slower than C. I don't
know if he ran some tests and determined that the array bounds checks were
the problem or merely assumed that the checks were causing the problem.
Many people like to play up Java's bounds checking as a performance hit, so
I could see how one could leap to conclusions about its effect on the
performance of their application.

 

[Roedy Green]

I'm writing code that performs mathematical calculations on large arrays.
The code is slower than C, because Java performs array bounds checking on
every access. The performance difference is substantial on large arrays.

Try natively compiling it with an optimising compiler such as jet.

see http://mindprod.com/jgloss/nativecompiler.html

 

[Liz]

Thanks for bringing this up. This is a theoretical optimization that is
brought up alot when bounds checking is being discussed. I have never
attempted to verify that this optimization is used in practice. I assumed
that the OP knew about it, so he should take note if he didn't. I also
assumed that the JVM was not performing this optimization because he said
that the array bounds checking was causing it to be slower than C. I don't
know if he ran some tests and determined that the array bounds checks were
the problem or merely assumed that the checks were causing the problem.
Many people like to play up Java's bounds checking as a performance hit, so
I could see how one could leap to conclusions about its effect on the
performance of their application.

Here is my test of the above. I compiled a simple java file then
disassembled
it to get java source (to see that my compile was doing the right thing) and
to get the bytecodes. NOTE: there is only one compare in the byte codes
(line 8)
and that is necessary to see when the loop is to terminate. Therefore
in this case there is NO BOUNDS CHECKING done.

class test4 {
public static void main(String args[]) {
int array[] = new int[100];
for(int i = 0; i < array.length; i++)
array = 1;

System.exit(0);
}
}
// Source File Name: test4.java
class test4 {

public static void main(String args[])
{
// 0 0:bipush 100
// 1 2:newarray int[]
// 2 4:astore_1
// 3 5:iconst_0
// 4 6:istore_2
// 5 7:iload_2
// 6 8:aload_1
// 7 9:arraylength
// 8 10:icmpge 23
// 9 13:aload_1
// 10 14:iload_2
// 11 15:iconst_1
// 12 16:iastore
// 13 17:iinc 2 1
// 14 20:goto 7
// 15 23:iconst_0
// 16 24:invokestatic #2 <Method void System.exit(int)>
// 17 27:return
}
}

 

[Liz]

Thanks for bringing this up. This is a theoretical optimization that is
brought up alot when bounds checking is being discussed. I have never
attempted to verify that this optimization is used in practice. I assumed
that the OP knew about it, so he should take note if he didn't. I also
assumed that the JVM was not performing this optimization because he said
that the array bounds checking was causing it to be slower than C. I don't
know if he ran some tests and determined that the array bounds checks were
the problem or merely assumed that the checks were causing the problem.
Many people like to play up Java's bounds checking as a performance hit, so
I could see how one could leap to conclusions about its effect on the
performance of their application.

Here is my test of the above. I compiled a simple java file then
disassembled
it to get java source (to see that my compile was doing the right thing) and
to get the bytecodes. NOTE: there is only one compare in the byte codes
(line 8)
and that is necessary to see when the loop is to terminate. Therefore
in this case there is NO BOUNDS CHECKING done.

class test4 {
public static void main(String args[]) {
int array[] = new int[100];
for(int i = 0; i < array.length; i++)
array = 1;

System.exit(0);
}
}
// Source File Name: test4.java
class test4 {

public static void main(String args[])
{
// 0 0:bipush 100
// 1 2:newarray int[]
// 2 4:astore_1
// 3 5:iconst_0
// 4 6:istore_2
// 5 7:iload_2
// 6 8:aload_1
// 7 9:arraylength
// 8 10:icmpge 23
// 9 13:aload_1
// 10 14:iload_2
// 11 15:iconst_1
// 12 16:iastore
// 13 17:iinc 2 1
// 14 20:goto 7
// 15 23:iconst_0
// 16 24:invokestatic #2 <Method void System.exit(int)>
// 17 27:return
}
}

I forgot to mention that I used the Sun 1.4.2 java compiler with -g option.

java -g test4.java

 

[Roedy Green]

// 12 16:iastore

this instruction has a built in null pointer check and subscript range
check. The HotSpot or JIT or static compile may convert it to native
code that bypasses the check.

 

[Liz]

this instruction has a built in null pointer check and subscript range
check. The HotSpot or JIT or static compile may convert it to native
code that bypasses the check.

*sneaky* but probably more efficient

 

[Roedy Green]

*sneaky* but probably more efficient

It keeps the size of the class files down. It also allows for using
any hardware assist. If you check with ordinary instructions, you
can't tell them apart from ordinary arithmetic.

For example, the Pentium has a BOUND instruction that checks if an
index in within a given range, unfortunately giving no speed
advantage, especially when the lower bound is 0.

Imagine Java implemented on the old Intel 432. Its hardware would
automatically detect subscripts out of bounds. You would turn the
hardware interrupt into an ArrayIndexOutOfBounds exception.

 

[Thomas Weidenfeller]

I'm writing code that performs mathematical calculations on large arrays.
The code is slower than C,

Ok, of course this is possible.

because Java performs array bounds checking on
every access.

Did you measure if this is the cause? If not, get some profiler and
measure. Assumptions/guesses about potential bottlenecks are usually
just wrong, and there might be something completely different eating up
your performance.

If the array access is really the problem, you are almost out of luck.
Arrays are "low-level" data structures in Java. If they are not fast
enough, then you have to go to native code.

Does anyone know of a way around this problem? What I'm thinking is that
there might be a JVM or some native libraries out there that can provide
"unsafe" arrays.

You would have to move not only the array access, but also the
calculation to some JNI code. Otherwise the repeated JNI invocations
just to access an array element would eat up a lot of performance.

/Thomas

 

[Tor Iver Wilhelmsen]

I'm writing code that performs mathematical calculations on large
arrays. The code is slower than C, because Java performs array
bounds checking on every access. The performance difference is
substantial on large arrays.

Don't use arrays, but use the buffer classes in java.nio. Compute
offset using e.g. row*columns+column.

Also, do you every variable that can be is final, so that it might
optimize better?

 

[Filip Larsen]

Chris wrote

I'm writing code that performs mathematical calculations on large arrays.
The code is slower than C, because Java performs array bounds checking on
every access. The performance difference is substantial on large arrays.

Does anyone know of a way around this problem? What I'm thinking is that
there might be a JVM or some native libraries out there that can provide
"unsafe" arrays.

Let me add to the other fine answers in this thread, that if you do
choose to use a native library and JNI you should probably consider
doing many calculations in each native call rather than just accessing
one array element. Depending on your deployment requirements you may
also benefit from still having a pure java implementation of the
calculations and only switch to the native library when it is there
(this of course requires you to keep two set of source code in sync so
it might not be worth it in your case).

And let me also chime in with the choir saying: make sure you have
identified real performance problems by *measuring* them.


Regards,

 

[Tarlika Elisabeth Schmitz]

Hello Chris,

I'm writing code that performs mathematical calculations on large arrays.
The code is slower than C, because Java performs array bounds checking on
every access. The performance difference is substantial on large arrays.

Does anyone know of a way around this problem? What I'm thinking is that
there might be a JVM or some native libraries out there that can provide
"unsafe" arrays.

I don't know of fast arrays, but it might be worth checking out the
following library:

J.A.D.E. Java Addition to Default Environment, which offers, amongst
other things Miscellaneous utilities classes (public domain) such as
FastMap, FastSet, FastString and TypeFormat.
www.dautelle.com/jade/

--


Regards/Gruß,

Tarlika Elisabeth Schmitz

 

[Chris Uppal]

I'm writing code that performs mathematical calculations on large arrays.
The code is slower than C, because Java performs array bounds checking on
every access. The performance difference is substantial on large arrays.

BTW, you haven't told us what the elements of your arrays are, doubles ?
floats ? ints ? longs ? ...

Or even, and God help you if they are ;-) Doubles...

Also you haven't said whether you are using linear or mult-dimensional arrays
(and if multi-dimensional, then how you have them laid out in "memory").

The point is that while array bounds checking /may/ be having an effect (as
others have said, it's difficult to tell without measuring it -- itself a
tricky thing to do), the performance profile of operations on primitive types
is not typically the same in Java as it would be on an ostensibly similar type
in, say, C.

-- chris

 

[Eric Sosman]

*sneaky* but probably more efficient

It keeps the size of the class files down. It also allows for using
any hardware assist. [...]

Also, it relieves the bytecode verifier of the need
to ensure that the range-checking comparisons are actually
present and valid. Remember: The JVM must be able to
absorb bytecode streams not generated by javac, and do
so safely.

 

[Doug Pardee]

Theoretically, if the JVM can tell that the array index cannot get
out of range it can skip the check, e.g.

for(i=0; i<array.length; i++) {
// do it
}

Maybe someone can check if it does.

The JVM bytecodes for array access do not have an option to turn off
range checking, so I don't see how this could be done.

Personally, I'd be very surprised if the few extra machine cycles
needed to check the array bounds are an issue. Here are some other
possibilities, depending on the type of the array:

For arrays of non-primitive objects: the aastore instruction has to
validate that the type of the object being stored is
assignment-compatible with the type of the array (ArrayStoreException
checking).

For double[]: value-set conversion may be needed. In an Intel
architecture, double-precision floating-point computations are
performed in 80-bit precision, which will have to be converted to
64-bit IEEE format to be stored in a double or an element of double[].
Similarly, loading a double or an element of a double[] may require
converting to the 80-bit value set. (This discussion ignores
"strictfp", which can be very hard on performance in an Intel
architecture.)

For byte[] or boolean[] (theoretical issue): IF the JVM implements
boolean[] as a packed bit-array, the baload and bastore instructions
have to examine the type of the array to determine how to load/store
the data, and access to elements of a boolean[] require masking and
shifting. I say this is "theoretical" because this is NOT an issue
with Sun JVMs; they store booleans and bytes exactly the same.

Again, I seriously doubt that the index range-checking is responsible
for the performance issues. Once the performance problem has been
isolated to specific code sections, an investigation of the bytecodes
being generated for those sections will probably reveal what's going
on.

 

[Liz]

Chris wrote


Let me add to the other fine answers in this thread, that if you do
choose to use a native library and JNI you should probably consider
doing many calculations in each native call rather than just accessing
one array element. Depending on your deployment requirements you may
also benefit from still having a pure java implementation of the
calculations and only switch to the native library when it is there
(this of course requires you to keep two set of source code in sync so
it might not be worth it in your case).

But the c code already exists (or how would it be known that java is
slower) and since it does only math it is pretty portable. After all
a = b[5] + c;
shouldn't have to change for different OS.