Array Types In C#

As a C# Performance Architect, your job is to create solution architectures that provide the best possible performance for your business or organization. And to do your job well, you’ll need a solid understanding of basic C# code optimizations.

In this post, we’ll look at the different types of arrays in C#. Understanding the difference will help you pick the correct data structure for every occasion.

Take a look at the following code.

static void Main(string[] args)
{
    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]++;
            }
        }
    }
}

It’s a simple 3-way nested loop that increments every item in the multidimensional array.

But wait! There’s another way of doing this. Check out this code:

static void Main(string[] args)
{
    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]++;
            }
        }
    }
}

It’s basically the same code, but now I’ve flattened the array into a 1-dimensional data structure. I still have the three loop variables, so I’m using a new variable index to calculate the index of the array element to increment.

Which code do you think is faster?

It’s pretty much the same code. Either I am doing the array element index calculation myself, or I use a 3-dimensional array and let the .NET runtime do it for me. But in both cases, it’s the same expression. So you wouldn’t expect any difference, right?

Well, check it out. I’ve coded a quick benchmark to compare the two:

Did you see the results? The first benchmark with the multidimensional array took 125 milliseconds. The second benchmark with the flattened array took only 93 milliseconds. Flattening the array sped up my code by about 26%.

That’s quite a difference. The reason becomes clear when we look at the compiled code. This is what the first code fragment compiles to:

// compute memory address of array element
IL_0024: ldloc.0
IL_0025: ldloc.1
IL_0026: ldloc.2
IL_0027: ldloc.3
IL_0028: callvirt instance int32& int32[,,]::Address(int32, int32, int32)

// increment array element
IL_002d: dup
IL_002e: ldind.i4
IL_002f: ldc.i4.1
IL_0030: add
IL_0031: stind.i4

The runtime simply calls the class method  int32[,,]::Address to calculate the memory address of the array element, and then increments it. Pretty straightforward.

This is what the second code fragment compiles to:

// index = k + SIZE * (j + SIZE * i)
IL_0026: ldloc.3
IL_0027: ldc.i4 300
IL_0030: ldloc.2
IL_0031: ldlc.i4 300
IL_0034: ldloc.1
IL_0035: mul
IL_0036: add
IL_0037: mul
IL_0038: add
IL_0039: stloc.s 4

// increment array[index]
IL_0041: ldloc.0
IL_0042: ldloc.s 4
IL_0044: ldelema [System.Runtime]System.Int32  // <-- look at this
IL_0048: dup
IL_0049: ldlind.i4
IL_004a: ldc.i4.1
IL_004b: add
IL_004c: stind.i4

Note that there isn’t a single method call in the compiled code. The runtime calculates the array index expression and then uses a specialized IL instruction ldelema to load the address of the array element. Once the address is known, the runtime uses the same ldind and stind instruction pair to increment the memory location.

Not having to call the int32[,,]::Address method but having a specialized IL instruction for calculating the array item address is a small optimization. But in mission-critical loops, it can really add up.

So here’s what you need to do:

  • For non-critical code, feel free to use multidimensional arrays.
  • But if you need optimal performance, consider flattening your arrays and grab that extra 26% speed boost.

 

 

Would you like to know more? I’ve created a series of blog posts on C# performance optimization. Each post is based on content from my courses and from actual techniques I’ve used in the field.

Take a look: