Fastest way to convert T[,] to T[][]?

arrays, c#, jagged-arrays, multidimensional-array

Solution

A view caveats/assumptions up front:

- You seem to use only `int` as your data type (or at least seem to be OK with using `Buffer.BlockCopy` which would imply you can life with primitive types in general).

- For the test data you show, I don't think there will be much different using any somewhat sane approach.

Having that said, the following implementation (which needs to be specialized for a specific primitive type (here `int`) because it uses `fixed`) is around 10 times faster than the approach using the inner loop:

    unsafe public static int[][] AsJagged2(int[,] rect)
    {
        int row1 = rect.GetLowerBound(0);
        int rowN = rect.GetUpperBound(0);
        int col1 = rect.GetLowerBound(1);
        int colN = rect.GetUpperBound(1);

        int height = rowN - row1 + 1;
        int width = colN - col1 + 1;
        int[][] jagged = new int[height][];

        int k = 0;
        for (int i = row1; i < row1 + height; i++)
        {
            int[] temp = new int[width];

            fixed (int *dest = temp, src = &rect[i, col1])
            {
                MoveMemory(dest, src, rowN * sizeof(int));
            }

            jagged[k++] = temp;
        }

        return jagged;
    }

    [DllImport("kernel32.dll", EntryPoint = "RtlMoveMemory")]
    unsafe internal static extern void MoveMemory(void* dest, void* src, int length);

Using the following "test code":

    static void Main(string[] args)
    {
        Random rand = new Random();
        int[,] data = new int[100,1000];
        for (int i = 0; i < data.GetLength(0); i++)
        {
            for (int j = 0; j < data.GetLength(1); j++)
            {
                data[i, j] = rand.Next(0, 1000);
            }
        }

        Stopwatch sw = Stopwatch.StartNew();

        for (int i = 0; i < 100; i++)
        {
            int[][] dataJagged = AsJagged(data);
        }

        Console.WriteLine("AsJagged:  " + sw.Elapsed);

        sw = Stopwatch.StartNew();

        for (int i = 0; i < 100; i++)
        {
            int[][] dataJagged2 = AsJagged2(data);
        }

        Console.WriteLine("AsJagged2: " + sw.Elapsed);
    }

Where `AsJagged` (the first case) is your original function, I get the following output:

AsJagged:  00:00:00.9504376
AsJagged2: 00:00:00.0860492

So there is indeed a faster way of doing it, however depending on the size of the test data, the number of times you actually perform this operation, and your willingness to allow unsafe and P/Invoke code, you're probably not going to need it.

Having that said, we were using large matrixes of `double` (say 7000x10000 elements) where it indeed did make a huge difference.

Update: about using Buffer.BlockCopy

I might overlook some `Marshal` or other trick, but I don't think using `Buffer.BlockCopy` is possible here. This is due to the fact that it requires both the source and destination array to, well, be an `Array`.

In our example, the destination is an array (e.g. `int[] temp = ...`) however the source is not. While we "know" that for two dimensional arrays of primitive types the layout is such, that each "row" (i.e. first dimension) is an array of the type in memory, there is no safe (as in `unsafe`) way to get that array without the overhead of copying it first. So we basically need to use a function that simply deals with memory and doesn't care about the actual content of it - like `MoveMemory`. BTW, the internal implementation of `Buffer.BlockCopy` does something similar.

Problem

Original source

Related problems

• Getting a double[] row array of a double[,] rectangular array
• What is the difference between T[,] and T[*,*]?