Improving Performance of Multidimensional Arrays in C#

C# has support for multidimensional arrays, which are useful for representing elements in a 2D or 3D grid:

int[,] twoDimensions = new int[20, 20];
int[,,] threeDimensions = new int[20, 20, 20];

Under the covers, these arrays are allocated as a single-dimensional array:

// Your code
int[,] twoDimensions = new int[20, 20];

// Under the covers:
int[] actualArray = new int[20 * 20];

When accessing a multidimensional array, C# performs bounds checks on each dimension, then converts each separate access value (x, y, z, etc) into a single access value. Reference source.

T[] data = new T[];
int[] lengths = new int[3];

T Get(int x, int y, int z)
{
    // Bounds checks
    if (x < 0 || x >= lengths[0])
        throw new OutOfRangeException(...);

    if (y < 0 || y >= lengths[1])
        throw new OutOfRangeException(...);

    if (z < 0 || z >= lengths[2])
        throw new OutOfRangeException(...);

    // Convert 3D access to a 1D access
    var access = x + y * lengths[0] + z * lengths[0] * lengths[1];    
    return data[access];
}

Converting to a single-dimensional array is straightforward and can reduce access speeds by 37-47% (see the the benchmarks below).

// 2D array example
int[,] twoDimensions = new int[20, 20];
int randomValue = twoDimensions[6, 6];

// 1D array example
int[] oneDimension = new int[20 * 20];
int randomValue = oneDimension[6 + 6 * 20];

Arrays with dimensions that are a power of 2 can be optimised further by replacing additions and multiplications with bitwise operators and bit-shifts:

int[] oneDimension = new int[32 * 32];
int randomValue = oneDimension[6 | (6 << 5)];

Here are the results of accessing 1,000,000 random items inside a 256x256x256 array:

For more information on the faster unsafe approach using unmanaged memory, check out this article.