One- Versus Multidimensional Arrays In C#

In this article I’ll take a look at the different types of arrays in C#. Understanding the differences between array types will help you pick the correct data structure for every occasion.

Check out the following code:

public class ArraysTest : PerformanceTest
{
    protected override bool MeasureTestA()
    {
        // fill a 3-dimensional array
        var size = Iterations;
        var array = new int[size, size, size];
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                for (int k = 0; k < size; k++)
                {
                    array[i, j, k] = 3;
                }
            }
        }
        return true;
    }

    protected override bool MeasureTestB()
    {
        // do the same with a flattened 1-dimensional array
        var size = Iterations;
        var array = new int[size * size * size];
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                for (int k = 0; k < size; k++)
                {
                    var index = k + size * (j + size * i);
                    array[index] = 3;
                }
            }
        }
        return true;
    }

    protected override bool MeasureTestC()
    {
        // do the same with a flattened array and incremental access
        var size = Iterations;
        var array = new int[size * size * size];
        var index = 0;
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                for (int k = 0; k < size; k++)
                {
                    array[index] = 3;
                    index++;
                }
            }
        }
        return true;
    }
}

The MeasureTestA method sets up a 3-dimensional array, loops through each array element, and sets it to the value ‘3’.

The MeasureTestB method does pretty much the same, but it uses a 1-dimensional array instead and calculates the array offset by hand using the i, j, and k loop variables.

That shouldn’t make any difference, right? You would expect that 3-dimensional arrays in .NET use the same logic as what I’ve explicitly coded in MeasureTestB.

Well, let’s take a look:

Did you see that coming?

The 3-dimensional array code in MeasureTestA is 31% slower than the 1-dimensional array code in MeasureTestB!

What’s going on here?

Let’s find out. We’ll start by looking at the 3-dimensional array code in MeasureTestA. The inner loop compiles to very efficient intermediate language:

The highlighted section is where the magic happens. The Array.Set method uses the i, j, and k indices to write the value ‘3’ directly into memory.

That’s just 6 instructions with one method call. Not bad at all!

Now let’s take a look at the inner loop of MeasureTestB:

We now have a lot more intermediate language instructions in the inner loop. And you can clearly see the mul and add instructions that manually calculate the array offset from the i, j, and k indices.

But did you notice that there isn’t a single method call in the loop?

Instead, there’s an stelem instruction at IL_0033 that writes the number ‘3’ directly into the 1-dimensional array.

And that’s the reason for the difference in performance: the .NET runtime has specialized intermediate language instructions for working with 1-dimensional arrays!

Because of this, the code in MeasureTestB doesn’t need to make method calls at all in the inner loop, and that saves a lot of time.

So if you’re working with multidimensional arrays in a hot loop in your code, consider flattening the arrays down to 1 dimension. That will remove a method call from your inner loop body and speed up your code considerably.

Finally, let’s take a look at MeasureTestC.

This method also uses a 1-dimensional, array but ignores the i, j, and k indices and avoids calculating the array offset. Since we’re updating the array sequentially anyway, this code simply starts at index zero and increments the index by one each time.

Here’s what the compiled code looks like:

This is as efficient as we’re going to get.

The code uses the stelem instruction to write the number ‘3’ directly into the 1-dimensional array, and then increments the index by one.

Note that there are no mul or add instructions anywhere because we’re not calculating the index from i, j, and k anymore.

This gives us a tiny performance boost. The code in method C is 2% faster than method B.

That just goes to show how fast integer multiplications are on modern CPUs. Getting rid of 2 mul instructions in a tight loop hardly makes a difference.

In practice, this final optimization is probably not worth it.