Converting from a jagged array to double pointer in C#

Question

Simple question here: is there any way to convert from a jagged array to a double pointer?

e.g. Convert a double[][] to double**

This can't be done just by casting unfortunately (as it can in plain old C), unfortunately. Using a fixed statement doesn't seem to resolve the problem either. Is there any (preferably as efficient as possible) way to accomplish this in C#? I suspect the solution may not be very obvious at all, though I'm hoping for a straightforward one nonetheless.

Zorn

I guess this question boils down to: can you convert from single pointer (to an object) to pointer to a pointer? – Hanoi

The solution with the "ToPointer" extension method is a bad idea, because then you'd use the pointer outside the 'fixed' area by which time the .NET runtime might have moved the array to another memory location – Kandace

A smarter design Microsoft should have considered: Make "fixed" an underlying property of array objects, then make arrays convertible to pointers (matching C/C++) without needing a weird fixed "statement." That way when you convert an array to a pointer, as part of the conversion, the array automatically "fixes" itself indefinitely (since there's no way to predict how long the pointer might be alive). I can't think of any other functional, safe way to implement array pointer support in a managed OOP language - and I personally believe Microsoft was fairly shortsighted to have missed this. – Wehrle

Just curious. @Noldorin, are you aware that memory, allocated for each inner array could be not continuous? In other words, there could be gaps between each inner array. – Penetration

I think it's time to change the accepted answer now. :) @cassandradied has provided a much more detailed answer, with all of the unsafe pointer problems fixed. – Wehrle

Answer 1

A double[][] is an array of double[], not of double* , so to get a double** , we first need a double*[]

double[][] array = //whatever
//initialize as necessary

fixed (double* junk = &array[0][0]){

    double*[] arrayofptr = new double*[array.Length];
    for (int i = 0; i < array.Length; i++)
        fixed (double* ptr = &array[i][0])
        {
            arrayofptr[i] = ptr;
        }

    fixed (double** ptrptr = &arrayofptr[0])
    {
        //whatever
    }
}

I can't help but wonder what this is for and if there is a better solution than requiring a double-pointer.

Minelayer

Unfortunately I can't avoid the user of a double pointer, since I'm calling an external C function, and C# can't automatically marshall jagged arrays. – Zorn

I'll give this a go as soon as possible by the way. Thanks. – Zorn

I had to edit this like 6 times to get around SO wanting to parse the *s as italics. The preview window and the actual post were inconsistent in their interpretation... – Minelayer

@zachrrs: So your method seems to do the job well enough. Looping through one of the dimensions isn't the ideal solution in my mind, though I'm thinking it might be necessary in C#. I'm going to leave this question open for a bit longer in case anyone else has something new to add. If not, the answer will be yours. :) – Zorn

Are you sure this will work? It seems to me that you pin the inner arrays only when you're assigning them to arrayofptr[i]. That would mean the array can move while you're working with its pointer, which can corrupt memory and cause unpredictable bugs. – Wavy

Sample of code to prove that @bsneeze's code could lead to errors if inner arrays are moved if someone is interested. – Penetration

Answer 2

A little bit of safety.
As mentioned in comments to the first solution, nested arrays could be moved, so they should be pinned too.

unsafe
{
    double[][] array = new double[3][];
    array[0] = new double[] { 1.25, 2.28, 3, 4 };
    array[1] = new double[] { 5, 6.24, 7.42, 8 };
    array[2] = new double[] { 9, 10.15, 11, 12.14 };

    GCHandle[] pinnedArray = new GCHandle[array.Length];
    double*[] ptrArray = new double*[array.Length];

    for (int i = 0; i < array.Length; i++)
    {
        pinnedArray[i] = GCHandle.Alloc(array[i], GCHandleType.Pinned);
    }

    for (int i = 0; i < array.Length; ++i)
    {
        // as you can see, this pointer will point to the first element of each array
        ptrArray[i] = (double*)pinnedArray[i].AddrOfPinnedObject();
    }

    // here is your double**
    fixed(double** doublePtr = &ptrArray[0])
    {
        Console.WriteLine(**doublePtr);
    }

    // unpin all the pinned objects,
    // otherwise they will live in memory till assembly unloading
    // even if they will went out of scope
    for (int i = 0; i < pinnedArray.Length; ++i)
        pinnedArray[i].Free();
}

A brief explanation of the problem:

When we allocate some objects on the heap, they could be moved to another location on garbage collecting. So, imagine next situation: you have allocated some object and your inner arrays, they are all placed in zero generation on the heap.

Now, some object has gone from scope and became garbage, some objects just been allocated. Garbage collector will move old objects out of heap and move other objects closer to the beginning or even to the next generation, compacting heap. The result will looks like:

So, our goal is to “pin” some objects in heap, so they would not move. What we have to achieve this goal? We have fixed statement and GCHandle.Allocate method.

First, what GCHandle.Allocate does? It creates new entry in inner system table that have a reference to the object that passed to method as a parameter. So, when garbage collector will examine heap, he will check inner table for entries and if he will find one, he will mark object as alive and will not move it out of heap. Then, he will look on how this object is pinned and will not move the object in memory in compacting stage. fixed statement does almost the same, except it “unpins” object automatically when you leave scope.

Summarizing: each object that has been pinned with fixed will be automatically “unpinned” once he left a scope. In our case, it will be on next iteration of loop.

How to check that your objects will not be moved or garbage collected: just consume all the heap's budget for zero generation and force GC to compact heap. In other words: create a lot of objects on the heap. And do it after you pinned your objects or “fixed” them.

for(int i = 0; i < 1000000; ++i)
{
    MemoryStream stream = new MemoryStream(10);
    //make sure that JIT will not optimize anything, make some work
    stream.Write(new Byte[]{1,2,3}, 1, 2);
}
GC.Collect();

Small notice: there are two types of heaps — for large objects and for small ones. If your object is large, you should create large objects to check your code, otherwise small objects will not force GC to start garbage collection and compacting.

Lastly, here's some sample code, demonstrating the dangers of accessing the underlying arrays with unpinned/unfixed pointers - for anybody who is interested.

namespace DangerousNamespace
{
    // WARNING!
    // This code includes possible memory access errors with unfixed/unpinned pointers!
    public class DangerousClass
    {
        public static void Main()
        {
            unsafe
            {
                double[][] array = new double[3][];
                array[0] = new double[] { 1.25, 2.28, 3, 4 };
                array[1] = new double[] { 5, 6.24, 7.42, 8 };
                array[2] = new double[] { 9, 10.15, 11, 12.14 };

                fixed (double* junk = &array[0][0])
                {
                    double*[] arrayofptr = new double*[array.Length];
                    for (int i = 0; i < array.Length; i++)
                        fixed (double* ptr = &array[i][0])
                        {
                            arrayofptr[i] = ptr;
                        }

                    for (int i = 0; i < 10000000; ++i)
                    {
                        Object z = new Object();
                    }
                    GC.Collect();

                    fixed (double** ptrptr = &arrayofptr[0])
                    {
                        for (int i = 0; i < 1000000; ++i)
                        {
                            using (MemoryStream z = new MemoryStream(200))
                            {
                                z.Write(new byte[] { 1, 2, 3 }, 1, 2);
                            }
                        }
                        GC.Collect();
                        // should print 1.25
                        Console.WriteLine(*(double*)(*(double**)ptrptr));
                    }
                }
            }
        }
    }
}

Penetration

Could you edit this answer to show the creation of a double** ? As you mentioned in an earlier comment, the arrays are not contiguous, so you'd need to create a separate array of the pinned pointers, and then return a pointer to that separate array. Perhaps with another method to un-pin everything later, when the double** is no longer needed. Actually, this is starting to sound like a really good candidate for extension methods for System.Array. :) – Wehrle

@Wehrle well, yeah, I can, but I think it will be like we are answering different question. Necessity of creating of continuous arrays is subjective for me and could be implemented in several ways, and these ways will depend on initial purpose and receiving side. But anyway, I will add some “simple” realization of such extension to my answer. – Penetration

@Wehrle now I realized that I didn't get your point. Well, I have edited answer to show where is double**. Hope it is what you asked me to do. For the first time I was thinking that you asked me to write a class which could get a jagged array and convert it to a continuous array with GetAddr function to expose this array outside, with thread safety, resource management, IDispossable and other SafeHandleZeroOrMinusOneIsInvalid interfaces. Spent several hours implementing it, haha. – Penetration

Haha, hopefully the time wasn't completely wasted. Keep that class in case you need it for something in the future. :) Yeah, we just needed to see the double** in the answer, that's all. Thanks again for going the extra mile, in many ways! – Wehrle

I edited your answer to include the sample code you mentioned in one of your comments. I think this answer is fabulous. I'll award the bounty now. – Wehrle

@Wehrle thanks. Sorry if I understood you wrong in some places. – Penetration

Answer 3

I've gone with zachrrs solution for the time being (which was what I was suspecting might need to be done in the first place). Here it is an extension method:

public static double** ToPointer(this double[][] array)
{
    fixed (double* arrayPtr = array[0])
    {
        double*[] ptrArray = new double*[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            fixed (double* ptr = array[i])
                ptrArray[i] = ptr;
        }

        fixed (double** ptr = ptrArray)
            return ptr;
    }
}

Zorn

You can't use a pointer outside of the fixed block where you declared it, because the object could have moved in the meantime. – Wavy

@svick: Sure you can. It just might not work all the time. As it happens, it does in this case... Maybe one of the Marshal static methods would help make it more robust though. – Zorn

Well, maybe it seems to work right now. But you change one line in an unrelated or just have bad luck one day and it won't work. Your code is wrong. The fact that it currently works is mostly an accident. – Wavy

Yes, that's what I just said. No need to be so fanatical. ;) It also helps to post a solution rather than just down-vote & criticise. – Zorn