Sequentially Accessing a Rectangular Array

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.