Tag Archives: optimization

Memory access patterns in high-level languages

Programming,

Like many developers that work in high-level languages, I think don’t spend a lot of time thinking about memory access patterns. This is probably a good thing… for the most part, worrying about this is premature optimization. But there are times when it matters, and the compiler won’t magically “optimize” it away for you, even if you have optimizations turned on:

Code

class MemoryAccessPatterns
{
    static void Main(string[] args)
    {
        var timer = new Stopwatch();
 
        timer.Start();
        for (var i = 0; i < 25; i++)
        {
            doFast();
        }
        timer.Stop();
        Console.WriteLine("Fast array: {0}", timer.ElapsedMilliseconds);
 
        timer.Restart();
        for (var i = 0; i < 25; i++)
        {
            doSlow();
        }
        timer.Stop();
        Console.WriteLine("Slow array: {0}", timer.ElapsedMilliseconds);
        Console.ReadKey();
    }
 
    private static void doFast()
    {
        var fast = new int[5000, 5000];
        for (var i = 0; i < 5000; i++)
        {
            for (var j = 0; j < 5000; j++)
            {
                fast[i, j]++;
            }
        }
    }
 
    private static void doSlow()
    {
        var slow = new int[5000, 5000];
        for (var i = 0; i < 5000; i++)
        {
            for (var j = 0; j < 5000; j++)
            {
                slow[j, i]++;
            }
        }
    }
}

Results

Release x86, optimizations on:
Fast array: 3829
Slow array: 8495

Release x86, optimizations off:
Fast array: 4357
Slow array: 8675

Release x64, optimizations on:
Fast array: 5074
Slow array: 10445

Release x64, optimizations off:
Fast array: 5954
Slow array: 10781

I tried this out after seeing this discussion thread on Quora this morning.