Manipulating large arrays very fast

Discussion in 'Java' started by E. Naubauer, Jan 24, 2006.

  1. E. Naubauer

    E. Naubauer Guest

    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
    E. Naubauer, Jan 24, 2006
    #1
    1. Advertising

  2. E. Naubauer

    Roedy Green Guest

    Roedy Green, Jan 24, 2006
    #2
    1. Advertising

  3. E. Naubauer

    Oliver Wong Guest

    "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;
    >
    > <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
    Oliver Wong, Jan 24, 2006
    #3
  4. E. Naubauer

    E. Naubauer Guest

    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.?
    E. Naubauer, Jan 24, 2006
    #4
  5. E. Naubauer

    E. Naubauer Guest

    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;
    >>
    >> <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.
    E. Naubauer, Jan 24, 2006
    #5
  6. E. Naubauer

    Oliver Wong Guest

    "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;
    >
    > <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
    Oliver Wong, Jan 24, 2006
    #6
  7. E. Naubauer

    Roedy Green Guest

    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.
    Roedy Green, Jan 25, 2006
    #7
  8. E. Naubauer

    Roedy Green Guest

    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("20988936657440586486151264256610222593863921");
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
    Roedy Green, Jan 25, 2006
    #8
  9. E. Naubauer

    E. Naubauer Guest

    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.
    E. Naubauer, Jan 25, 2006
    #9
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Raymond Arthur St. Marie II of III

    very Very VERY dumb Question About The new Set( ) 's

    Raymond Arthur St. Marie II of III, Jul 23, 2003, in forum: Python
    Replies:
    4
    Views:
    472
    Raymond Hettinger
    Jul 27, 2003
  2. shanx__=|;-

    very very very long integer

    shanx__=|;-, Oct 16, 2004, in forum: C Programming
    Replies:
    19
    Views:
    1,616
    Merrill & Michele
    Oct 19, 2004
  3. Abhishek Jha

    very very very long integer

    Abhishek Jha, Oct 16, 2004, in forum: C Programming
    Replies:
    4
    Views:
    418
    jacob navia
    Oct 17, 2004
  4. Peter

    Very very very basic question

    Peter, Feb 8, 2005, in forum: C Programming
    Replies:
    14
    Views:
    513
    Dave Thompson
    Feb 14, 2005
  5. olivier.melcher

    Help running a very very very simple code

    olivier.melcher, May 12, 2008, in forum: Java
    Replies:
    8
    Views:
    2,287
Loading...

Share This Page