My favorite C# micro-optimizations #2: 1D Arrays

This is my second post on my favorite C# micr0-optimizations. Everything I said in the first post applies to this one as well, namely, don’t optimize until you know that you need to; and spend most of your optimization budget optimizing the algorithms, rather than figuring out which way to access an array is faster.

That said, this was a surprise to me: jagged arrays (e.g., arrays of arrays) are much faster than rectangular arrays: but indexed access into a 1D array is faster yet.

In other words, this is relatively slow:

   1:  for (int x = 0; x < size1; x++)

   2:  {

   3:      for (int y = 0; y < size2; y++)

   4:      {

   5:          result = twoDArray[x, y];

   6:      }

   7:  }

This is significantly faster:

   1:  for (int x = 0; x < size1; x++)

   2:  {

   3:      for (int y = 0; y < size2; y++)

   4:      {

   5:          result = jaggedArray[x][y];

   6:      }

   7:  }

But this is the fastest:

   1:  for (int x = 0; x < size1; x++)

   2:  {

   3:      for (int y = 0; y < size2; y++)

   4:      {

   5:          result = oneDArray[x * size2 + y];

   6:      }

   7:  }

Benchmark results on my machine (1000 iterations through a 1000x1000 array):

2DArrayTest action completed: iteration = 5, completionTime = 3111, averageCompletionTime = 3101.400
JaggedArrayTest action completed: iteration = 5, completionTime = 2283, averageCompletionTime = 2256.000
1DArrayTest action completed: iteration = 5, completionTime = 1698, averageCompletionTime = 1638.800

It’s also very much worth noting that the order in which the iteration happens is important. Sequential memory access is faster than purely random memory access, most likely because data is fetched from main memory to the CPU’s cache in chunks, so that subsequent sequential reads are from cache.

In other words, if instead of this at the center of each loop:

result = jaggedArray[x][y];
result = twoDArray[x, y];
result = oneDArray[x * size2 + y];

We switch the order of the indexes, so that memory is accessed out-of-order (this is called “diagonal access”):

result = jaggedArray[y][x];
result = twoDArray[y, x];
result = oneDArray[y * size1 + x];

Then the tests take more than twice as long:

JaggedArrayTest action completed: iteration = 5, completionTime = 7499, averageCompletionTime = 7676.400
2DArrayTest action completed: iteration = 5, completionTime = 6790, averageCompletionTime = 6818.600
1DArrayTest action completed: iteration = 5, completionTime = 5862, averageCompletionTime = 5883.200

It’s interesting that in a diagonal access pattern, rectangular arrays are indeed faster than jagged arrays: but one-dimensional arrays are still the fastest.