Another 2 Dimensional Array Allocation Problem c#

I am trying to figure out why "Choice A" performs better that "Choice B". My test shows something like 228 vs 830 or there about, it's like a 4 x difference. Looking at the IL, the untrained eye doesn't pick-out the subtly between the 2 calls.

Thank you, Stephen

const int SIZE = 10000;
void Main()
{
    var sw = Stopwatch.StartNew();

    int[,]A = new int[SIZE, SIZE];
    int total, x, y;

    // Choice A
    total = 0;
    for (x = 0; x < SIZE; x++)
    {
        for (y = 0; y < SIZE; y++)
        {
            total += A[x, y];
        }
    }

    Console.WriteLine(sw.ElapsedMilliseconds);

    sw.Reset();
    sw.Start();

    // Choice B
    total = 0;
    for (y = 0; y < SIZE; y++)
    {
        for (x = 0; x < SIZE; x++)
        {
            total += A[x, y];
        }
    }

    Console.WriteLine(sw.ElapsedMilliseconds);
}

// Define other methods and classes here

Ok, I broke this out so that they would run independently of each other and mitigate any caching and or diagnostics... and B is ALWAYS coming in behind A

namespace ConsoleApplication1
{
    class ProgramA
    {
        const int SIZE = 10000;
        static void Main(string[] args)
        {
            var sw = Stopwatch.StartNew();

            int[,] A = new int[SIZE, SIZE];
            int total, x, y;

            // Choice A
            total = 0;
            for (x = 0; x < SIZE; x++)
            {
                for (y = 0; y < SIZE; y++)
                {
                    total += A[x, y];
                }
            }

            Console.WriteLine(sw.ElapsedMilliseconds);
            Console.ReadLine();
        }
    }

    class ProgramB
    {
        const int SIZE = 10000;
        static void Main(string[] args)
        {
            var sw = Stopwatch.StartNew();

            int[,] A = new int[SIZE, SIZE];
            int total, x, y;

            // Choice B
            total = 0;
            for (y = 0; y < SIZE; y++)
            {
                for (x = 0; x < SIZE; x++)
                {
                    total += A[x, y];
                }
   开发者_运维百科         }

            Console.WriteLine(sw.ElapsedMilliseconds);
            Console.ReadLine();
        }
    }
}

At a guess, cache effects would be the big one here.

A two-dimensional array is layed out in memory like so:

(0, 0) (0, 1) (0, 2) (0, 3) (1, 0) (1, 1) (1, 2) ...

In option A, you're accessing successive elements in memory - this means that when the CPU fetches a cache line, it gets several successive elements. While option B is jumping around through memory. Thus option B requires significantly more memory accesses once the array becomes larger than the cache size.

Ahh I think I remember.

If you think of a 2d array as a table in memory, the first value is the row, the second value is a column.

[0, 0] [0, 1] [0, 2] [0, 3]... [1, 0] [1, 1] [1, 2] [1, 3]...

When you iterate over it, the first loop is the row, the second loop is the column. It's quicker to iterate by doing foreach row, assign each column.

In the second scenario it's values are assigned as

[0, 0] [1, 0] [2, 0] [3, 0]... [0, 1] [1, 1] [2, 1] [3, 1]...

So this is slower because your looping, you're assigning foreach column, foreach row. You're only assigning the first column, for each row.

Does that make sense?

Edit: This was one of the things I was looking for:

http://en.wikipedia.org/wiki/Row-major_order

In row-major storage, a multidimensional array in linear memory is accessed such that rows are stored one after the other.

So when iterating over a row at a time, it's not jumping around memory looking for each next row to assign the value to the column, it has the row, assigns all columns, then jumps to the next row in memory.

To expand upon the cacheing answers:

The values in question are 4 bytes each and IIRC current memory architecture reads 16 byte lines from memory assuming a properly populated motherboard. (I don't know about DDR3, it's three-chip nature suggests the reads are even bigger.) Thus when you read a line of memory you get 4 values.

When you do it the first way you use all of these values before going back to the memory for the next line. Done the second way you use only one of them and it then gets flushed from the on-chip cache long before it's called for again.