How to iterate through a fixed tridimensional matrix efficiently (java)

Question

As part of a program I'm building I need to iterate through all the points in a tridimensional matrix. On each point I need to execute a method that takes int x, int y, int z as parameters.

The tridimensional matrix always has the same width(16) length(16) & height(256).

What is the most performant way of doing the iteration?(i'm specially concerned about CPU, not so concerned about ram usage)

Based on what i know , I think this are the most efficient methods, but I'm open to other suggestions if they are faster.

A. Iterate directly:

public void doSomethingForAllPointsInMatrix(Matrix matrix){
  for(int x= 0; x<16; x++){
    for(int z = 0; z<16; z++){
      for(int y = 0; y<256; y++){
        matrix.doSomething(x,y,z);//A method out of my control without any alternatives
      }
    }
  }
}

B. Iterate an array containing the coordinates

private static final int[] zeroToFifteen; //Contains every number from 0 to 15
private static final int[] zeroToTwoHundredFiftyFive; //Contains every number from 0 to 255
public void doSomethingForAllPointsInMatrix(Matrix matrix){
  for(int x: zeroToFifteen){
    for(int z: zeroToFifteen){
      for(int y: zeroToTwoHundredFiftyFive){
        matrix.doSomething(x,y,z);//A method out of my control without any alternatives
      }
    }
  }
}

Thanks in advance for any help you can provide!

You could try this, posted on a similar question: https://stackoverflow.com/a/2996752/8104777 — Caleb George, Jun 01 '21 at 18:36
Thanks for the link, I've checked it out, the optimizations of that thread are to things that aren't part of my question — HappilyCoding, Jun 01 '21 at 18:47
In both cases, your method is called `x*y*z` times. Without knowing what exactly your method does and what it returns, it is difficult to suggest a general optimisation approach. Perhaps you are just thinking about performance too early/unnecessarily. Implement the functionality, test it with a cube with few demensions and ask your question again when you face performance issues. Things you might want to look at: see if there is any symmetry to not call your method multiple times with the same parameters, see if there is any pattern between `doSomething(xi,yi,zi)` and `doSomething(xn,yn,zn)` . — Eritrean, Jun 01 '21 at 19:20
While I agree that a general optimisation approach would be nicer, the method is part of the API of another program, which is out of my control, and there aren't other alternative methods, so the loop is all i can optimize, not the method itself. I'll add a bit more information in the example though. — HappilyCoding, Jun 01 '21 at 20:50
The layout of the matrix in memory can make a difference because of cache use. I think your best bet is traverse the matrix ensuring that you access consecutive data. — 1010, Jun 03 '21 at 00:45

score 1 · Accepted Answer · answered Jun 09 '21 at 13:22

A counting loop is already one of the most efficient iteration mechanisms.

Your idea to incorporate an array indicates that you are not aware that the for-each loop over an array is just syntactic sugar for a counting loop over the indices from zero to the array length.
In other words, your

public void doSomethingForAllPointsInMatrix(Matrix matrix){
  for(int x: zeroToFifteen){
    for(int z: zeroToFifteen){
      for(int y: zeroToTwoHundredFiftyFive){
        matrix.doSomething(x,y,z);//A method out of my control without any alternatives
      }
    }
  }
}

is basically equivalent to

  public void doSomethingForAllPointsInMatrix(Matrix matrix){
    for(int index1 = 0; index1 < zeroToFifteen.length; index1++){
      int x = zeroToFifteen[index1];
      for(int index2 = 0; index2 < zeroToFifteen.length; index2++){
        int z = zeroToFifteen[index2];
        for(int index3 = 0; index3 < zeroToTwoHundredFiftyFive.length; index3++){
          int y = zeroToTwoHundredFiftyFive[index3];
          matrix.doSomething(x,y,z);//A method out of my control without any alternatives
        }
      }
    }
  }

differing from the counting loop of your first approach only by doing additional array operations, which is very unlikely to improve the performance.

Since your bounds are powers of two, you could do the entire operation with a single loop

public void doSomethingForAllPointsInMatrix(Matrix matrix) {
  for(int coord = 0; coord < 0x10000; coord++) {
    matrix.doSomething(coord >> 12, coord & 0xff, (coord >> 8)&0xf);
  }
}

reducing the number of conditionals. However, the actual performance depends on what the JVM’s optimizer makes out of it and it might be that it can deal better with the nested loops.

So you can only try and benchmark the approaches, to find “the best”, whereas “the best” may be different, depending on the system and the JVM implementation/version.

As said in the comments, the performance is likely dominated by whatever doSomething does and if the processing order is not important for your program logic, you should try with alternative iteration orders, as it may affect how the caches are utilized.

I was aware that the two were functionally equivalent, but I wasn't sure that in this case they compiled to exactly the same code, thanks for clearing that up, and thanks for your suggested alternative. — HappilyCoding, Jun 09 '21 at 19:07

How to iterate through a fixed tridimensional matrix efficiently (java)

1 Answers1