Memory confusion

Question

I have an app in which I'm trying to create a very large "cube" of bytes. A 3 dimensional array (~1000x1000x500) saves all of the values that I'm interested in - but I'm getting out of memory problems. While this was expected, the BEHAVIOR of the various OOM messages that I'm getting has been quite confusing. First:

Foo[,,] foo1 = new Foo[1000, 1000, 500];

Fails with an OOM error, but this does not:
Foo[,,] foo1 = new Foo[250, 1000, 500];
Foo[,,] foo2 = new Foo[250, 1000, 500];
Foo[,,] foo3 = new Foo[250, 1000, 500];
Foo[,,] foo4 = new Foo[250, 1000, 500];


Shouldn't these two sets of code consume essentially the same amount of memory?

Also, I was originally getting the error message when ~1.5GB had been consumed, but I assumed that by switching it to a 64bit application would let me use MUCH more memory before failing.

Am I running into stack space limitations? And if so, how can I instantiate this structure entirely on the heap without it ever having to exist (as a single entity) on the stack?

Thanks in advance - I look forward to any light that anyone can shead on this behavior.

Answer 1

Thing is, when you allocate an array, you need contiguous memory.

It is more likely to find 10 blocks of contiguous memory in RAM with a size of 10MB each than to find 1 huge block of 100MB.

Let's say you had 100 bytes of RAM with addresses 0 to 99. If you allocated a block of memory with size 1 byte at position 23 for example, although you have 99 bytes of RAM remaining, if you wanted to allocate a block of memory with a size of 99 bytes, you will fail because the memory must be contiguous. The biggest block you'd be able to allocate in such a case would be 76 bytes long.

Answer 2

A 32 bit app is limited to 4 GB of address space, so that's the upper limit. If the process runs on a 32 bit OS, this is further limited to 2 or 3 GB depending on the setup of the app and the OS.

In the first case you're allocating one big array. In .NET arrays are allocated on the heap, so the stack space is not the issue here. Given the numbers in the question I assume the array is around 1.5 GB. To handle that the CLR needs a contiguous block of memory. If you allocate the same number of bytes in smaller chunks (as in the second example) the runtime will stand a better chance of allocating the memory as needed.

Still, with at least 2 GB available you would think that 1.5 GB should not be a problem, but the fact is that a process doesn't use address space strictly from one end to the other. Once DLLs have been loaded into the process the address space is fragmented.

In my experience 32 bit managed apps (on 32 bit OS) are usually limited to around 1.5 GB of heap space, which would explain the OOM you're seeing.

Running the same app on 64 bit OS will give the app access to the entire 4 GB address space, which will affect the space available for the managed heap.

Turning the app into a 64 bit app, changes the address space size from 4 GB to 8 TB. However, even in this case you should keep in mind that the default maximum size of any .NET object is 2 GB. See this question for details.

Answer 3

EDIT

I was musing on a more fully featured implementation of my answer, I thought I'd append. I'm not sure if the parallelization would help, perhaps it depends on the initializer.

using System;
using System.Linq;

public static T[][][] NewJagged<T>(
        int h,
        int w,
        ing d,
        Func<int, int, int, T> initializer = null,
        bool parallelize = true)
{
    if (h < 1)
    {
        throw new ArgumentOutOfRangeException("h", h, "Dimension less than 1.")
    }

    if (w < 1)
    {
        throw new ArgumentOutOfRangeException("w", w, "Dimension less than 1.")
    }

    if (d < 1)
    {
        throw new ArgumentOutOfRangeException("d", d, "Dimension less than 1.")
    }

    if (initializer == null)
    {
        initializer = (i, j, k) => default(T);
    }

    if (parallelize)
    {
        return NewJaggedParalellImpl(h, w, d, initializer);
    } 

    return NewJaggedImpl(h, w, d, initializer);
}

private static T[][][] NewJaggedImpl<T>(
        int h,
        int w,
        int d,
        Func<int, int, int, T> initializer)
{
    var result = new T[h][][];
    for (var i = 0; i < h; i++)
    {
        result[i] = new T[w][];
        for (var j = 0; j < w; j++)
        {
            result[i][j] = new T[d];
            for (var k = 0; k < d; k++)
            {
                result[i][j][k] = initializer(i, j, k);
            }
        }
    }

    return result;
}

private static T[][][] NewJaggedParalellImpl<T>(
        int h,
        int w,
        int d,
        Func<int, int, int, T> initializer)
{
    var result = new T[h][][];
    ParallelEnumerable.Range(0, h).ForAll(i =>
    {
        result[i] = new T[w][];
        ParallelEnumerable.Range(0, w).ForAll(j =>
        {
            result[i][j] = new T[d];
            ParallelEnumerable.Range(0, d).ForAll(k =>
            {
                result[i][j][k] = initializer(i, j, k);
            });
        });
    });

    return result;
}            

This makes the function completely generic but still leaves you the simple syntax,

var foo1 = NewJagged<Foo>(1000, 1000, 500);

You could however get fancy and populate in paralell on initialization,

var foo2 = NewJagged<Foo>(
    1000,
    1000,
    5000,
    (i, j, k) =>
        {
            var pos = (i * 1000 * 500) + (j * 500) + k;
            return ((pos % 2) == 0) ? new Foo() : null;
        });

in this instance, populating with a checkerboard effect (I think.);

---

This may not initially seem to answer your problem ...

If you had a function, something like this

public static T[][][] ThreeDimmer<T>(int h, int w, int d) where T : new()
{
    var result = new T[h][][];
    for (var i = 0; i < h; i++)
    {
        result[i] = new T[w][];
        for (var j = 0; j < w; j++)
        {
            result[i][j] = new T[d];
            for (var k = 0; k < d; k++)
            {
                result[i][j][k] = new T();
            }
        }
    }

    return result;
}

Then you would have encapsulated the initialization of a 3 dimensional jagged array of reference types. This would allow you to do,

Foo[][][] foo1 = ThreeDimmer<Foo>(1000, 1000, 500);

This would avoid the memory fragmentation issues of multidimensional arrays. It would also avoid other pitfalls and limitations, giving you a faster more flexible jagged array instead.