Improving Performance of Multidimensional Arrays in C#

Vercidium — Tue, 14 Feb 2023 07:31:39 +0000

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.

C# - Improving Array Performance with .NET 7

Vercidium — Fri, 10 Feb 2023 06:46:35 +0000

.NET 7 introduced a new static class called NativeMemory, which can be used to allocate unmanaged memory.

Normally when working with arrays in C#, the .NET runtime manages the allocation of memory and frees it when it's no longer used, hence the name managed memory.

When using NativeMemory, you're on your own. The .NET garbage collector won't free it when you no longer need it, and the .NET runtime won't perform bounds checks when reading or writing to it. The advantage is it's faster to work with as the bounds checks performed by .NET aren't present.

Warning! Allocating 1024 integers and then writing to the 1025th one will overwrite memory that may be in use elsewhere. Be careful!

Usage

Allocate a 1kb block of unmanaged memory:

var byteCount = 1024;
void* data = NativeMemory.Alloc(byteCount);

Allocate and zero a block of unmanaged memory:

void* data = NativeMemory.AllocZeroed(1024);

Resize a block of unmanaged memory to 2kb:

NativeMemory.Realloc(data, 2048);

Free a block of unmanaged memory:

NativeMemory.Free(data);
data = null;

Example - Accumulating an Array

Using managed memory:

// Allocate managed memory
const int LENGTH = 1024;
int[] data = new int[LENGTH];


// Accumulate
int total = 0;

for (int i = 0; i < LENGTH ; i++)
    total += data[i];


// Log the result
Console.WriteLine(total);

Using unmanaged memory:

// Allocate unmanaged memory
const int LENGTH = 1024;
int byteCount = LENGTH * sizeof(int);
int* data = (int*)NativeMemory.Alloc(byteCount);


// Option 1
// - Same syntax as the managed example
int total = 0;

for (int i = 0; i < LENGTH; i++)
    total += data[i];


// Option 2
// - Different syntax, same functionality
for (int i = 0; i < LENGTH; i++)
    total += *(data + i);


// Option 3 - 
// - Make a copy of the data pointer, read from it, then increment it
// - This works because pointers are essentially a 32 or 64 bit
//   integer, meaning we can increment and compare them
var readPtr = data;
var endPtr = data + LENGTH;

while (readPtr < endPtr)
{
    total += *readPtr;
    readPtr++;
}


// Log the result
Console.WriteLine(total);

Benchmarks

The above managed and unmanaged examples were benchmarked using BenchmarkDotNet, with an array length of 32768.

Forem: Vercidium

Improving Performance of Multidimensional Arrays in C#

C# - Improving Array Performance with .NET 7

Usage

Example - Accumulating an Array

Benchmarks