What's better in regards to performance? type[,] or type[][]?

Question

Is it more performant to have a bidemnsional array (type[,]) or an array of arrays (type[][]) in c#?

Particularly for initial allocation and item access

Answer 1

[out of date; see post with example and results]

I really doubt that there will be a significant difference, but a bi-directional array may possibly be slightly quicker since it is just one offset rather than two. More important is the usage: if you are representing a rectangular array, consider [,] - if your data is jagged consider [][].

But first consider if you even want an array in the first place - list/dictionary/etc are often better choices.

A rectangular array may be more convenient to initialize, since all you need is one "new" - a jagged array needs 1+m "new"s, where m is the number of inner arrays. But a single large array may be harder to allocate in in memory (due to fragmentation). Of course, if this is being a problem you are probably already using too much data...

Answer 2

I believe that [,] can allocate one contiguous chunk of memory, while [][] is N+1 chunk allocations where N is the size of the first dimension. So I would guess that [,] is faster on initial allocation.

Access is probably about the same, except that [][] would involve one extra dereference. Unless you're in an exceptionally tight loop it's probably a wash. Now, if you're doing something like image processing where you are referencing between rows rather than traversing row by row, locality of reference will play a big factor and [,] will probably edge out [][] depending on your cache size.

As Marc Gravell mentioned, usage is key to evaluating the performance...

Answer 3

type[,] will work faster. Not only because of less offset calculations. Mainly because of less constraint checking, less memory allocation and greater localization in memory. type[][] is not a single object -- it's 1 + N objects that must be allocated and can be away from each other.

Answer 4

Of course, if all else fails... test it! Following gives (in "Release", at the console):

Size 1000, Repeat 1000
    int[,] set: 3460
    int[,] get: 4036 (chk=1304808064)
    int[][] set: 2441
    int[][] get: 1283 (chk=1304808064)

So a jagged array is quicker, at least in this test. Interesting! However, it is a relatively small factor, so I would still stick with whichever describes my requirement better. Except for some specific (high CPU/processing) scenarios, readability / maintainability should trump a small performance gain. Up to you, though.

Note that this test assumes you access the array much more often than you create it, so I have not included timings for creation, where I would expect rectangular to be slightly quicker unless memory is highly fragmented.

using System;
using System.Diagnostics;
static class Program
{
    static void Main()
    {
        Console.WriteLine("First is just for JIT...");
        Test(10,10);
        Console.WriteLine("Real numbers...");
        Test(1000,1000);

        Console.ReadLine();
    }

    static void Test(int size, int repeat)
    {
        Console.WriteLine("Size {0}, Repeat {1}", size, repeat);
        int[,] rect = new int[size, size];
        int[][] jagged = new int[size][];
        for (int i = 0; i < size; i++)
        { // don't cound this in the metrics...
            jagged[i] = new int[size];
        }
        Stopwatch watch = Stopwatch.StartNew();
        for (int cycle = 0; cycle < repeat; cycle++)
        {
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    rect[i, j] = i * j;
                }
            }
        }
        watch.Stop();
        Console.WriteLine("\tint[,] set: " + watch.ElapsedMilliseconds);

        int sum = 0;
        watch = Stopwatch.StartNew();
        for (int cycle = 0; cycle < repeat; cycle++)
        {
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    sum += rect[i, j];
                }
            }
        }
        watch.Stop();
        Console.WriteLine("\tint[,] get: {0} (chk={1})", watch.ElapsedMilliseconds, sum);

        watch = Stopwatch.StartNew();
        for (int cycle = 0; cycle < repeat; cycle++)
        {
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    jagged[i][j] = i * j;
                }
            }
        }
        watch.Stop();
        Console.WriteLine("\tint[][] set: " + watch.ElapsedMilliseconds);

        sum = 0;
        watch = Stopwatch.StartNew();
        for (int cycle = 0; cycle < repeat; cycle++)
        {
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                {
                    sum += jagged[i][j];
                }
            }
        }
        watch.Stop();
        Console.WriteLine("\tint[][] get: {0} (chk={1})", watch.ElapsedMilliseconds, sum);
    }
}

Answer 5

It really depends. The MSDN Magazine article, Harness the Features of C# to Power Your Scientific Computing Projects, says this:

Although rectangular arrays are generally superior to jagged arrays in terms of structure and performance, there might be some cases where jagged arrays provide an optimal solution. If your application does not require arrays to be sorted, rearranged, partitioned, sparse, or large, then you might find jagged arrays to perform quite well.