«

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[i];

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

output[i] = 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

On Tue, 24 Jan 2006 21:10:24 +0100, "E. Naubauer"
<> wrote, quoted or indirectly quoted someone who
said :

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

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

http://mindprod.com/jgloss/optimising.html
--
Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

"E. Naubauer" <> wrote in message
news:43d689b2$...
> 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[i];
>
> <do some integer arithmetic with temp and write it to output>
>
> output[i] = 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[i]. 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

Roedy Green schrieb:
> On Tue, 24 Jan 2006 21:10:24 +0100, "E. Naubauer"
> <> wrote, quoted or indirectly quoted someone who
> said :
>
>>
>> Does anyone have an idea of methods or new language constructs for
>> accessing array elements very fast?
>
> see http://mindprod.com/jgloss/aot.html
>
> http://mindprod.com/jgloss/optimising.html

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

Oliver Wong schrieb:
> "E. Naubauer" <> wrote in message
> news:43d689b2$...
>> 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[i];
>>
>> <do some integer arithmetic with temp and write it to output>
>>
>> output[i] = 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[i]. 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[i];

<do some integer arithmetic with temp>
}

with 1.5 VM on a Mac Os X 10.4.4 Powerbook.

"E. Naubauer" <> wrote in message
news:43d6a34a$...
> 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[i];
>
> <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

On Tue, 24 Jan 2006 21:41:20 +0100, "E. Naubauer"
<> wrote, quoted or indirectly quoted someone who
said :

>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.

--
Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

On Tue, 24 Jan 2006 20:37:49 GMT, "Oliver Wong" <>
wrote, quoted or indirectly quoted someone who said :

>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("2098893665744058648615126425661022259386392 1");
--
Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

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.