Array access optimization

Question

I have a 10x10 array in Java, some of the items in array which are not used, and I need to traverse through all elements as part of a method. What Would be better to do :

1. Go through all elements with 2 for loops and check for the nulltype to avoid errors, e.g.

   for(int y=0;y<10;y++){
       for(int x=0;x<10;x++){
          if(array[x][y]!=null)
               //perform task here
       }
   }
   

2. Or would it be better to keep a list of all the used addresses... Say an arraylist of points?

3. Something different I haven't mentioned.

I look forward to any answers :)

Answer 1

Any solution you try needs to be tested in controlled conditions resembling as much as possible the production conditions. Because of the nature of Java, you need to exercise your code a bit to get reliable performance stats, but I'm sure you know that already.

This said, there are several things you may try, which I've used to optimize my Java code with success (but not on Android JVM)

for(int y=0;y<10;y++){
    for(int x=0;x<10;x++){
       if(array[x][y]!=null)
            //perform task here
    }
}

should in any case be reworked into

for(int x=0;x<10;x++){
    for(int y=0;y<10;y++){
       if(array[x][y]!=null)
            //perform task here
    }
}

Often you will get performance improvement from caching the row reference. Let as assume the array is of the type Foo[][]:

for(int x=0;x<10;x++){
    final Foo[] row = array[x];
    for(int y=0;y<10;y++){
       if(row[y]!=null)
            //perform task here
    }
}

Using final with variables was supposed to help the JVM optimize the code, but I think that modern JIT Java compilers can in many cases figure out on their own whether the variable is changed in the code or not. On the other hand, sometimes this may be more efficient, although takes us definitely into the realm of microoptimizations:

Foo[] row;
for(int x=0;x<10;x++){
    row = array[x];
    for(int y=0;y<10;y++){
       if(row[y]!=null)
            //perform task here
    }
}

If you don't need to know the element's indices in order to perform the task on it, you can write this as

for(final Foo[] row: array){
    for(final Foo elem: row
       if(elem!=null)
            //perform task here
    }
}

Another thing you may try is to flatten the array and store the elements in Foo[] array, ensuring maximum locality of reference. You have no inner loop to worry about, but you need to do some index arithmetic when referencing particular array elements (as opposed to looping over the whole array). Depending on how often you do it, it may or not be beneficial.

Since most of the elements will be not-null, keeping them as a sparse array is not beneficial for you, as you lose locality of reference.

Another problem is the null test. The null test itself doesn't cost much, but the conditional statement following it does, as you get a branch in the code and lose time on wrong branch predictions. What you can do is to use a "null object", on which the task will be possible to perform but will amount to a non-op or something equally benign. Depending on the task you want to perform, it may or may not work for you.

Hope this helps.