Manipulating large arrays very fast

E

E. Naubauer

Hello everybody

I want to manipulate an image which is stored as an int array.
The array is as big as the image , 704 * 576 elements.

What I need to do is to read the data from the input array,
do some integer arithmetic and write it to an output array
from the same size.

it looks somewhat like this:

int input[];
int output[];



......


int temp;

for(int i = 0;i < array.length;i++)
{
temp = input;

<do some integer arithmetic with temp and write it to output>

output = temp;
}



However, this small loop causes running times from about ~80 ms.
Since I need to do more operations to the image before drawing and
the images need to be processed in real-time (10 frames per second)
this is a little slow for my purposes.

For testing I removed the last line and the processing time went down.
Then I used the new for-loop from Java 1.5 spec.

for(int i : array)
{
temp = i;

<do some integer arithmetic with temp and write it to output>
}

and again I got a speed boost.

I think this is due to optimized array access in the native
implementation (less bounds checking etc. ).


Does anyone have an idea of methods or new language constructs for
accessing array elements very fast?

Thanks in advance
 
O

Oliver Wong

E. Naubauer said:
Hello everybody

I want to manipulate an image which is stored as an int array.
The array is as big as the image , 704 * 576 elements.

What I need to do is to read the data from the input array,
do some integer arithmetic and write it to an output array
from the same size.

it looks somewhat like this:

int input[];
int output[];



.....


int temp;

for(int i = 0;i < array.length;i++)
{
temp = input;

<do some integer arithmetic with temp and write it to output>

output = temp;
}



However, this small loop causes running times from about ~80 ms.
Since I need to do more operations to the image before drawing and
the images need to be processed in real-time (10 frames per second)
this is a little slow for my purposes.

For testing I removed the last line and the processing time went down.
Then I used the new for-loop from Java 1.5 spec.

for(int i : array)
{
temp = i;

<do some integer arithmetic with temp and write it to output>
}

and again I got a speed boost.

I think this is due to optimized array access in the native
implementation (less bounds checking etc. ).


Does anyone have an idea of methods or new language constructs for
accessing array elements very fast?


Correct me if I've misunderstood, but... it looks like in your new code,
you don't actually write the data back to output. So essentially your
code is doing nothing, and maybe the compiler is realizing this, and
eliminating your for-loop altogether.

I'm assuming that the pseudocode that says "<do some integer arithmetic
with temp and write it to output>" doesn't actually write to output, and
this is just a historial artifact from an earlier draft of the post you
wrote, otherwise in the first version of your code, you're writing to temp
twice.

- Oliver
 
E

E. Naubauer

Oliver said:
E. Naubauer said:
Hello everybody

I want to manipulate an image which is stored as an int array.
The array is as big as the image , 704 * 576 elements.

What I need to do is to read the data from the input array,
do some integer arithmetic and write it to an output array
from the same size.

it looks somewhat like this:

int input[];
int output[];



.....


int temp;

for(int i = 0;i < array.length;i++)
{
temp = input;

<do some integer arithmetic with temp and write it to output>

output = temp;
}



However, this small loop causes running times from about ~80 ms.
Since I need to do more operations to the image before drawing and
the images need to be processed in real-time (10 frames per second)
this is a little slow for my purposes.

For testing I removed the last line and the processing time went down.
Then I used the new for-loop from Java 1.5 spec.

for(int i : array)
{
temp = i;

<do some integer arithmetic with temp and write it to output>
}

and again I got a speed boost.

I think this is due to optimized array access in the native
implementation (less bounds checking etc. ).


Does anyone have an idea of methods or new language constructs for
accessing array elements very fast?


Correct me if I've misunderstood, but... it looks like in your new code,
you don't actually write the data back to output. So essentially your
code is doing nothing, and maybe the compiler is realizing this, and
eliminating your for-loop altogether.

I'm assuming that the pseudocode that says "<do some integer arithmetic
with temp and write it to output>" doesn't actually write to output, and
this is just a historial artifact from an earlier draft of the post you
wrote, otherwise in the first version of your code, you're writing to temp
twice.

- Oliver


You're right, I shoud have explained it differently.
Point is that this thing here

for(int i : input)
{
temp = i;

<do some integer arithmetic with temp>
}

runs faster for me than this here

for(int i = 0;i < input.length;i++)
{
temp = intput;

<do some integer arithmetic with temp>
}

with 1.5 VM on a Mac Os X 10.4.4 Powerbook.
 
O

Oliver Wong

E. Naubauer said:
Point is that this thing here

for(int i : input)
{
temp = i;

<do some integer arithmetic with temp>
}

runs faster for me than this here

for(int i = 0;i < input.length;i++)
{
temp = intput;

<do some integer arithmetic with temp>
}

with 1.5 VM on a Mac Os X 10.4.4 Powerbook.


This looks like it would be compiler/runtime/virtual machine specific
(i.e. there is nothing in the JLS that prevents the latter from generating
faster run-time behaviour than the former for a different, but fully
compliant, Java compiler/runtime/VM).

Therefore, I'd be surprise if you get a lot of educated advice, unless
it comes from someone who is familiar with your specific
compiler/runtime/VM.

If you've really exhausted all other avenues of optimization, then you
may be hitting the limits of Java (or computer science itself, depending on
what kind of algorithms you're trying to run). The problems with the kinds
of optimizations you're mentioning here is that they are brittle. In the
next version of your VM (1.5.1?), perhaps they will have made some tweaks
reversing which one is faster and which one is slower.

Assuming you really have tried everything else at the Java-source code
level, have you considered tweaking the bytecode manually?

- Oliver
 
R

Roedy Green

Interesting, but do aot compilers tend to remove language specific
issues like array bounds check etc.?

They are clever. They figure out when the bounds checks are not
necessary or promote them out of loops. I'm not sure if you can still
do this, but at one time here was an option to have jet turn off
bounds checking altogether.

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

Optimising compilers do quite will with array processing. They can
avoid redoing the address calculations for each access. They
potentially can avoid the array store type check.

In Java, array indexing access does not require a multiply, just a
shift because anything you can put in an array is always a power of
two bytes long. Bit arrays are the possible exception if you pack 8
bits per byte.

In other languages you have arrays of structures that can be any size,
and hence access requires a multiply. There clever optimisers convert
multiplys to additions.
 
R

Roedy Green

So essentially your
code is doing nothing, and maybe the compiler is realizing this, and
eliminating your for-loop altogether.

This is why benchmarks made up of fake calculations are so
meaningless. The sorts of optimisation the compiler can do are not
that frequent in the real world.

A story. Back in my youth there was an Algol program to compute the
Nth prime of a certain class. For some reason the program took days
to compile. However when it executed it took no time at all. It had
at compile time unraveled the entire code so that the final program
was essentially

print("20988936657440586486151264256610222593863921");
 
E

E. Naubauer

Ok, you two made some interesting suggestions and
I'll try them out before grasping the JNI club,
especially the JET compiler Mr.Green suggested
(he seems to be quite busy in this ng, isn't he :) ).

Thanks for your kindness.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,439
Members
44,829
Latest member
PIXThurman

Latest Threads

Top