C# Fastest dimension to traverse a 3D array

user_12431275 0
Viewed 315

I have an 3D multidimensional array, with sizes 20, 240 and 20.

var stuff = new Stuff[20, 240, 20]

Which order should I traverse the array for best performance?

Currently I'm doing: X, Z, Y in a nested for loop as this is what I've seem some other people use.

for (byte x = 0; x < 20; x++)
    for (byte z = 0; z < 20; z++)
        for (byte y = 0; y < 240; y++)
multidimensional-array performance c#
2 Answers

You can benchmark it yourself, for example:

public class Traversal
{
    public static int[,,] stuff  = new int[20,240,20];

    [Benchmark]
    public int[,,] XYZ()
    {
        var result = new int [20, 240, 20];
        for (byte x = 0; x < 20; x++)
        for (byte y = 0; y < 240; y++)
        for (byte z = 0; z < 20; z++)
        {
            result[x, y, z] = stuff[x, y, z];
        }

        return result;
    }

    [Benchmark]
    public int[,,] XZY()
    {
        var result = new int [20, 240, 20];
        for (byte x = 0; x < 20; x++)
        for (byte z = 0; z < 20; z++)
        for (byte y = 0; y < 240; y++)
        {
            result[x, y, z] = stuff[x, y, z];
        }

        return result;
    }
}

BenchmarkRunner.Run<Traversal>();

On my computer it gives next results:

| Method |     Mean |    Error |   StdDev |
|------- |---------:|---------:|---------:|
|    XYZ | 412.4 us |  9.73 us | 27.92 us |
|    XZY | 429.0 us | 11.48 us | 33.50 us |

As CLI spec spec states:

Array elements shall be laid out within the array object in row-major order (i.e., the elements associated with the rightmost array dimension shall be laid out contiguously from lowest to highest index). The actual storage allocated for each array element can include platform-specific padding.

So in general it should be faster process items by row (especially if you are storing value types in array) due to CPU caching and maybe some optimizations, but for most every day scenarios improvement should be minor, and as always - benchmark your concrete case (and concrete hardware) first.

user_25012790

C# stores array in a row-major order, so it will be faster if you "keep operations on the same row near". That's because your CPU will use changing and in some cases SIMD instructions to vectorize the problem in the same row. So if you can it's better for performance to avoid jumping rows in a loop. On the other hand the number of iterations you have to do doesn't change so we are talking about some minor performance improvement.

user_136687670
Related