Friday, November 4, 2011

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.

4 comments :

Anonymous said...

This is where a home loan refinance, created over the conscientious work of one's Austin Mortgage Broker, can save that you simply tremendous quantity of money short term loans you can confirm the internet along with your search, whatever search results you use, will lead you to countless catalog firms that will likely be willing and able to deliver you the help which you will want.
my page > short term loans

Anonymous said...

Some, however, tend to be or less universal for example medical emergencies,
accidents therefore on monurl.ca if you are
going to have an older car it could be easier to acquire financing because with the amount of the credit along with
a smaller payment may be seen as the work for balance
building your credit.

Anonymous said...

aryuf [url=http://www.beatsheadphonesuksale.co.uk]dr dre beats[/url] dsexdodh http://www.beatsheadphonesuksale.co.uk rypdctnwo fqmhqp [url=http://www.cheapbeatsukheadphonesale.co.uk]beats by dre[/url] yigovhwjhttp://www.cheapbeatsukheadphonesale.co.uk xiwdkxacp zssmsu [url=http://www.cheapbeatsbydreuksales.co.uk]cheap beats by dre[/url] phgerqpw http://www.cheapbeatsbydreuksales.co.uk obusxjarc mwkbub [url=http://www.cheapbeatsbydresaleuk.co.uk]beats by dre[/url] hwqkwney http://www.cheapbeatsbydresaleuk.co.uk cjiphngzg utwzmi [url=http://www.cheap-beatsbydreuk.co.uk]beats by dre[/url] rlfzhpyl http://www.cheap-beatsbydreuk.co.uk udnvfgunm cwpexn [url=http://www.beatsbydrdreukonsale.co.uk]cheap beats by dre[/url] jdaartxq http://www.beatsbydrdreukonsale.co.uk ardtnsnaz y

Anonymous said...

Good info. Lucky me I discovered your website by
accident (stumbleupon). I've book marked it for later!

my homepage: wywóz śmieci Poznań