Efficient implementation of multi-dimensional arrays in Java?

Question

As far as I understand (from answers such as this), java has no native multi-dimensional continuous memory arrays (unlike C#, for example).

While the jagged array syntax (arrays of arrays) might be good for most applications, I would still like to know what's the best practice if you do want the raw efficiency of a continuous-memory array (avoiding unneeded memory reads)

I could of course use a single-dimensional array that maps to a 2D one, but I prefer something more structured.

Answer 1

it's not difficult to do it manually:

int[] matrix = new int[ROWS * COLS];

int x_i_j = matrix[ i*COLS + j ];

now, is it really faster than java's multi dimension array?

int x_i_j = matrix[i][j];

for random access, maybe. for continuous access, probably not - matrix[i] is almost certainly in L1 cache, if not in register cache. in best scenario, matrix[i][j] requires one addition and one memory read; while matrix[i*COLS + j] may cost 2 additions, one multiply, one memory read. but who's counting?

Answer 2

It depends on your access pattern. Using this simple program, comparing an int[][] with a 2D mapped over a 1D int[] array treated as a matrix, a native Java 2D matrix is:

1. 25% faster when the row is on the cache, ie: accessing by rows:
2. 100% slower when the row is not in the cache, ie: accessing by colums:

ie:

// Case #1
for (y = 0; y < h; y++)
    for (x = 0; x < w; x++)
        // Access item[y][x]

// Case #2
for (x = 0; x < w; x++)
    for (y = 0; y < h; y++)
        // Access item[y][x]

The 1D matrix is calculated as:

public int get(int x, int y) {
    return this.m[y * width + x];
}