CODEWITHSUNDEEP
c#
David Mulder
David Mulder

Reputation: 8027

Is C# List<char[]> allocated in contiguous memory?

If I declare a List of char arrays, are they allocated in contiguous memory, or does .NET create a linked list instead?

If it's not contiguous, is there a way I can declare a contiguous list of char arrays? The size of the char arrays is know ahead of time and is fixed (they are all the same size).

Upvotes: 11

Views: 3242

Answers (2)

Ed Swangren
Ed Swangren

Reputation: 124692

Yes, but not in the way that you want. List<T> guarantees that its elements are stored contiguously.

Arrays are a reference type, so the references are stored cotiguously as List<T> guarantees. However, the arrays themselves are allocated separately and where they are stored has nothing to do with the list. It is only concerned with its elements, the references.

If you require that then you should simply use one large array and maintain boundary data.

EDIT: Per your comment:

The inner arrays are always 9 chars.

So, in this case, cache coherency may be an issue because the sub-arrays are so small. You'll be jumping around a lot in memory getting from one array to the next, and I'll just take you on your word about the performance sensitivity of this code.

Just use a multi-dimensional if you can. This of course assumes you know the size or that you can impose a maximum size on it.

Is it possible to trade some memory to reduce complexity/time and just set a max size for N? Using a multi-dimensional array (but don't use the latter) is the only way you can guarantee contiguous allocation.

EDIT 2:

Trying to keep the answer in sync with the comments. You say that the max size of the first dimension is 9! and, as before, the size of the second dimension is 9.

Allocate it all up front. You're trading some memory for time. 9! * 9 * 2 / 1024 / 1024 == ~6.22MB.

As you say, the List may grow to that size anyway, so worst case you waste a few MB of memory. I don't think it's going to be an issue unless you plan on running this code in a toaster oven. Just allocate the buffer as one array up front and you're good.

Upvotes: 12

Paul Bellora
Paul Bellora

Reputation: 55223

List functions as a dynamic array, not a linked list, but this is beside the point. No memory will be allocated for the char[]s until they themselves are instantiated. The List is merely responsible for holding references to char[]s, of which it will contain none when first created.

If it's not contiguous, is there a way I can declare a contiguous list of char arrays? The size of the char arrays is know ahead of time and is fixed (they are all the same size).

No, but you could instantiate a 2-dimensional array of chars, if you also know how many char arrays there would have been:

char[,] array = new char[x, y];

Upvotes: 5

Related Questions