Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / January 2006

Tip: Looking for answers? Try searching our database.

Manipulating large arrays very fast

Thread view: 
E. Naubauer - 24 Jan 2006 20:10 GMT
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
Roedy Green - 24 Jan 2006 20:18 GMT
On Tue, 24 Jan 2006 21:10:24 +0100, "E. Naubauer"
<chrono@mail.isis.de> 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
Signature

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

E. Naubauer - 24 Jan 2006 20:41 GMT
Roedy Green schrieb:
> On Tue, 24 Jan 2006 21:10:24 +0100, "E. Naubauer"
> <chrono@mail.isis.de> wrote, quoted or indirectly quoted someone who
[quoted text clipped - 6 lines]
>
> http://mindprod.com/jgloss/optimising.html

Interesting, but do aot compilers tend to remove language specific
issues like array bounds check etc.?
Roedy Green - 25 Jan 2006 02:07 GMT
On Tue, 24 Jan 2006 21:41:20 +0100, "E. Naubauer"
<chrono@mail.isis.de> 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.

Signature

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

Oliver Wong - 24 Jan 2006 20:37 GMT
> Hello everybody
>
[quoted text clipped - 45 lines]
> 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
E. Naubauer - 24 Jan 2006 21:59 GMT
Oliver Wong schrieb:
>> Hello everybody
>>
[quoted text clipped - 58 lines]
>
>     - 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.
Oliver Wong - 24 Jan 2006 22:20 GMT
> Point is that this thing here
>
[quoted text clipped - 15 lines]
>
> 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
Roedy Green - 25 Jan 2006 02:12 GMT
>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");
Signature

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

E. Naubauer - 25 Jan 2006 04:46 GMT
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.


Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2009 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.