We know that .NET performs optimizations when accessing rectangular arrays, but for sequential access should the inner loop be on the first or second index? Is there even a difference?
The Code
using System;class Program{static void Main(string[] args)
{ int size = 512; int count = 1000;int[,] array = new int[size, size];
int total = 0;var watch = System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < count; i++)
for (int x = 0; x < size; x++)
for (int y = 0; y < size; y++)
total += array[x, y];
watch.Stop();
Console.WriteLine(String.Format("Sequential access by [x,y]: {0}ms", watch.ElapsedMilliseconds));watch = System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < count; i++)
for (int x = 0; x < size; x++)
for (int y = 0; y < size; y++)
total += array[y, x];
watch.Stop();
Console.WriteLine(String.Format("Sequential access by [y,x]: {0}ms", watch.ElapsedMilliseconds));Console.WriteLine(total);
Console.Read();
}
}
The Output
Sequential access by [x,y]: 825ms Sequential access by [y,x]: 2414ms 0
What a difference! Incrementing the first index in the inner loop takes almost 3 times longer, probably because there are so many more cache misses.
The Verdict
For best performance, process your rectangular arrays by incrementing the first index in an outer loop, and the second index in an inner loop.
