Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

2d-Array with more than 65535^2 elements --> Array dimensions exceeded supported range

I've a 64-bit PC with 128 GB of RAM and I'm using C# and .NET 4.5. I've the following code:

double[,] m1 = new double[65535, 65535];
long l1 = m1.LongLength;

double[,] m2 = new double[65536, 65536]; // Array dimensions exceeded supported range
long l2 = m2.LongLength;

I'm aware of <gcAllowVeryLargeObjects enabled="true" /> and I've set it to true.

Why can a multidimensional array not have more than 4294967295 elements? I saw the following answer https://stackoverflow.com/a/2338797/7556646.

I checked as well the documentation for gcAllowVeryLargeObjects and I saw the following remark.

The maximum number of elements in array is UInt32.MaxValue (4294967295).

I cannot understand why there is this limit? Is there a workaround? Is it planned to remove this limit in an upcoming version of .net?

I need the elements in that why in the memory because I want to compute for example a symmetric eigen-value decomposition using Intel MKL.

[DllImport("custom_mkl", CallingConvention = CallingConvention.Cdecl, ExactSpelling = true, SetLastError = false)]
internal static extern lapack_int LAPACKE_dsyevd(
    int matrix_layout, char jobz, char uplo, lapack_int n, [In, Out] double[,] a, lapack_int lda, [In, Out] double[] w);
like image 356
Wollmich Avatar asked Dec 15 '17 10:12

Wollmich


2 Answers

Disclaimer: This one turn out waay longer than expected

Why the CLR doesn't support large arrays

There are multiple reasons why the CLR doesn't support large arrays on the managed heap.

Some of them are technical, some of them might be "paradigmal".

This blog post goes into some of the reasons as to why there is a limitation. Essentially there was a decision to limit the maximum size of (capital O) Objects due to memory fragmentation. The cost of implementing the handling of larger objects was weighed against the fact that not many use cases exist[ed] that would require such large objects and those that did, would - in most cases - be due to a design fallacy of the programmer. And since, for the CLR, everything is an Object, this limitation also applies to arrays. To enforce this limitation array indexers were designed with signed integers.

But once you have made sure, that your program design requires you to have such large arrays you are going to need a workaround.

The above mentioned blog post also demonstrates that you can implement big arrays without going into unmanaged territory.

But as Evk has pointed out in the comments you want to pass the array as a whole to an external function via PInvoke. That means you'll need the array on the unmanaged heap, or it'll have to be marshaled during the call. And marshaling the whole thing is a bad idea with arrays this large.

Workaround

So since the managed heap is out of the question you'll need to allocate space on the unmanaged heap and use that space for your array.

Let's say you need 8 GB worth of space:

long size = (1L << 33);
IntPtr basePointer = System.Runtime.InteropServices.Marshal.AllocHGlobal((IntPtr)size);

Great! Now you have a region in virtual memory where you can store up to 8 GB worth of data.

How do I turn this into an array?

Well there are two approaches in C#

The "Unsafe" Approach

This will let you work with pointers. And pointers can be cast to arrays. (In vanilla C they are often one and the same)

If you have a good idea on how to realize 2D Arrays via pointers, then this will be the best option for you.

Here is a pointer

The "Marshal" Approach

You don't need the unsafe context and have to instead "marshal" your data from the managed heap to the unmanaged one. You'll still have to understand pointer arithmetic.

The two main functions you'll want to use are PtrToStructure and the reverse StructureToPtr. With one you'll get a copy of a value type (such as a double) out of a specified position on the unmanaged heap. With the other you'll put a copy of a value type on the unmanaged heap.

Both approaches are "unsafe" in a sense. You'll need to know your pointers

Common Pitfalls include but are not limited to:

  • Forgetting to check bounds rigorously
  • Mixing up the size of my elements
  • Messing up the alignment
  • Mixing up what kind of 2D Array you want
  • Forgetting about padding with 2D Arrays
  • Forgetting to free memory
  • Forgetting to have freed memory and using it anyways

You'll probably want to turn your 2D array desing into a 1D array design


In any case you would want to wrap it all into a class with the appropriate checks and destsructors.

Basic Example for Inspiration

What follows is a generic class that is "like" an array, based on the unmanaged heap.

Features inclulde:

  • It has an index accessor that accepts 64 bit integers.
  • It restricts the types that T can become to value types.
  • It has bounds checking and is disposable.

If you notice, I don't do any type checking, so if Marshal.SizeOf fails to return the correct number we are falling in one of the pits mentioned above.

Features that you'll have to implement yourself include:

  • 2D Accessor and 2D Array arithmetic (depending on what the other library expects, often it's something like p = x * size + y
  • Exposed pointer for PInvoke purposes (Or an internal call)

So use this only as a inspiration, if at all.

using static System.Runtime.InteropServices.Marshal;

public class LongArray<T> : IDisposable where T : struct {
    private IntPtr _head;
    private Int64 _capacity;
    private UInt64 _bytes;
    private Int32 _elementSize;

    public LongArray(long capacity) {
        if(_capacity < 0) throw new ArgumentException("The capacity can not be negative");
        _elementSize = SizeOf(default(T));
        _capacity = capacity;
        _bytes = (ulong)capacity * (ulong)_elementSize;

        _head = AllocHGlobal((IntPtr)_bytes);   
    }

    public T this[long index] {
        get {
            IntPtr p = _getAddress(index);

            T val = (T)System.Runtime.InteropServices.Marshal.PtrToStructure(p, typeof(T));

            return val;
        }
        set {
            IntPtr p = _getAddress(index);

            StructureToPtr<T>(value, p, true);
        }
    }

    protected bool disposed = false;
    public void Dispose() {
        if(!disposed) {
            FreeHGlobal((IntPtr)_head);
            disposed = true;
        }
    }

    protected IntPtr _getAddress(long index) {
        if(disposed) throw new ObjectDisposedException("Can't access the array once it has been disposed!");
        if(index < 0) throw new IndexOutOfRangeException("Negative indices are not allowed");
        if(!(index < _capacity)) throw new IndexOutOfRangeException("Index is out of bounds of this array");
        return (IntPtr)((ulong)_head + (ulong)index * (ulong)(_elementSize));
    }
}
like image 96
MrPaulch Avatar answered Nov 18 '22 21:11

MrPaulch


I've used the basic example of the "Marshal" approach from this answer from MrPaulch to create the following class called HugeMatrix<T>:

public class HugeMatrix<T> : IDisposable
    where T : struct
{
    public IntPtr Pointer
    {
        get { return pointer; }
    }

    private IntPtr pointer = IntPtr.Zero;

    public int NRows
    {
        get { return Transposed ? _NColumns : _NRows; }
    }

    private int _NRows = 0;

    public int NColumns
    {
        get { return Transposed ? _NRows : _NColumns; }
    }

    private int _NColumns = 0;

    public bool Transposed
    {
        get { return _Transposed; }
        set { _Transposed = value; }
    }

    private bool _Transposed = false;

    private ulong b_element_size = 0;
    private ulong b_row_size = 0;
    private ulong b_size = 0;
    private bool disposed = false;


    public HugeMatrix()
        : this(0, 0)
    {
    }

    public HugeMatrix(int nrows, int ncols, bool transposed = false)
    {
        if (nrows < 0)
            throw new ArgumentException("The number of rows can not be negative");
        if (ncols < 0)
            throw new ArgumentException("The number of columns can not be negative");
        _NRows = transposed ? ncols : nrows;
        _NColumns = transposed ? nrows : ncols;
        _Transposed = transposed;
        b_element_size = (ulong)(Marshal.SizeOf(typeof(T)));
        b_row_size = (ulong)_NColumns * b_element_size;
        b_size = (ulong)_NRows * b_row_size;
        pointer = Marshal.AllocHGlobal((IntPtr)b_size);
        disposed = false;
    }

    public HugeMatrix(T[,] matrix, bool transposed = false)
        : this(matrix.GetLength(0), matrix.GetLength(1), transposed)
    {
        int nrows = matrix.GetLength(0);
        int ncols = matrix.GetLength(1);
        for (int i1 = 0; i1 < nrows; i1++)
            for (int i2 = 0; i2 < ncols; i2++)
                this[i1, i2] = matrix[i1, i2];
    }

    public void Dispose()
    {
        if (!disposed)
        {
            Marshal.FreeHGlobal(pointer);
            _NRows = 0;
            _NColumns = 0;
            _Transposed = false;
            b_element_size = 0;
            b_row_size = 0;
            b_size = 0;
            pointer = IntPtr.Zero;
            disposed = true;
        }
    }

    public void Transpose()
    {
        _Transposed = !_Transposed;
    }

    public T this[int i_row, int i_col]
    {
        get
        {
            IntPtr p = getAddress(i_row, i_col);
            return (T)Marshal.PtrToStructure(p, typeof(T));
        }
        set
        {
            IntPtr p = getAddress(i_row, i_col);
            Marshal.StructureToPtr(value, p, true);
        }
    }

    private IntPtr getAddress(int i_row, int i_col)
    {
        if (disposed)
            throw new ObjectDisposedException("Can't access the matrix once it has been disposed");
        if (i_row < 0)
            throw new IndexOutOfRangeException("Negative row indices are not allowed");
        if (i_row >= NRows)
            throw new IndexOutOfRangeException("Row index is out of bounds of this matrix");
        if (i_col < 0)
            throw new IndexOutOfRangeException("Negative column indices are not allowed");
        if (i_col >= NColumns)
            throw new IndexOutOfRangeException("Column index is out of bounds of this matrix");
        int i1 = Transposed ? i_col : i_row;
        int i2 = Transposed ? i_row : i_col;
        ulong p_row = (ulong)pointer + b_row_size * (ulong)i1;
        IntPtr p = (IntPtr)(p_row + b_element_size * (ulong)i2);
        return p;
    }
}

and I can call now the Intel MKL library with huge matrices, e.g.:

[DllImport("custom_mkl", CallingConvention = CallingConvention.Cdecl, ExactSpelling = true, SetLastError = false)]
internal static extern lapack_int LAPACKE_dsyevd(
    int matrix_layout, char jobz, char uplo, lapack_int n, [In, Out] IntPtr a, lapack_int lda, [In, Out] double[] w);

For the argument IntPtr a I pass the Pointer property of the HugeMatrix<T> class.

like image 35
Wollmich Avatar answered Nov 18 '22 19:11

Wollmich