.NET Rectangular Arrays: how to access in a loop?

Question

Basically you have two ways for doing this:

for (int x = 0; x < UPPER_X; x++)
    for (int y = 0; y < UPPER_Y; y++)
    {        
        arr1[x, y] = get_value();
        arr2[y, x] = get_value();
    }

The only difference is what variable to change in the inner loop: first or second. I heard that the results differ from language to language.

What is right order for .NET?

Answer 1

You should benchmark your particular circumstances to be sure.

You would think that there would be no difference for rectangular arrays (i.e. contiguously allocated memory), BUT according to this MSDN article there is a difference:

You can get even better results by converting a multidimensional array into a single-dimensional array. If you don't mind the syntax, this can be trivial; just use one index as an offset. For example, the following declares a single-dimensional array to be used as a two-dimensional array:

double[] myArray = new double[ROW_DIM * COLUMN_DIM];

For indexing the elements of this array, use the following offset:

myArray[row * COLUMN_DIM + column];

This will undoubtedly be faster than an equivalent jagged or rectangular array.

Answer 2

The reason one is faster than the other has to do with the processor's cache, and the way the data is laid out in memory.

There are two normal ways to store the two-dimensional data is in one-dimensional address space, Either you can store all of the data for the first row, then the second row, and so on (aka row major order), or you can do it by columns (aka column major order). Below is what the memory locations would be for a 3x3 array for both of these options.

Rows:

1 2 3
4 5 6
7 8 9

Columns:

1 4 7
2 5 8
3 6 9

When you access one memory location, an entire cache line (which can be between 8 and 512 bytes, according to Wikipedia) is loaded into the cache. So if you access the next memory location it will already be in the cache. Thus, it can be much faster to access memory sequentially than to jump around in the address space. Thus, with large two-dimensional arrays, there can be a significant speed difference between choosing rows or columns as your inner loop variable.