Row / column vs linear indexing speed (spatial locality)

Question

Related question: This one

I am using a spatial grid which can potentially get big (10^6 nodes) or even bigger. I will regularly have to perform displacement operations (like a particle from a node to another). I'm not a crack in informatics but I begin to understand the concepts of cache lines and spatial locality, though not well yet. So, I was wandering if it is preferible to use a 2D array (and if yes, which one? I'd prefer to avoid boost for now, but maybe I will link it later) and indexing the displacement for example like this:

Array[i][j] -> Array[i-1][j+2]

or, with a 1D array, if NX is the "equivalent" number of columns:

Array[i*NX+j] -> Array[(i-1)*NX+j+2]

Knowing that it will be done nearly one million times per iteration, with nearly one million iteration as well.

Answer 1

With modern compilers and optimization enabled both of these will probably generate the exact same code

Array[i-1][j+2]  // Where Array is 2-dimensional

and

Array[(i-1)*NX+j+2]  // Where Array is 1-dimensional

assuming NX is the dimension of the second subscript in the 2-dimensional Array (the number of columns).