Memory: LOH and Chunked Lists

Managed memory in .Net is divided into a stack and several heaps. The most important heaps are the usual (ephemeral) heap and LOH. The ephemeral heap is the place where all ordinary objects live. LOH is the place where large (more than 85,000 bytes) objects live.

LOH has some features:

• Objects in LOH never move
• LOH only grows and never decreases (i.e. if the object is collected by the garbage collector, the size of the LOH still remains the same)
• Hip LOH is released only when the LOH is completely empty.

Of these two features of LOH, two important consequences arise, which are often forgotten:

• LOH memory may be fragmented. Those. something happens that was fought in the unmanaged world: at some point you may have 10Mb of free memory, but you cannot allocate memory for an object of 1Mb size
• If you once allocated memory for a large object, and then use only small ones, then you actually deprive yourself of a large piece of memory. Moreover, if your LOH had a list or a hash table of size N, and you added one element to it, the list is reallocated and doubles, respectively, the size of LOH will be at least 3 * N (N is the original data, 2N - a copy of the data and a reserve for the new size). The next growth will require a continuous piece of memory of 4 * N in LOH, and since we do not have such a piece in LOH (there is only N), it will have to be borrowed from the address space of the process. As a result, the size of LOH will grow to 7 * N, and so on.

If we recall that LOH is allocated in chunks of 16Mb, then everything that happens will seem even more destructive. The first effect can be fought by carefully reusing objects. With the second - without using large objects. It turns out somehow not very, especially if you still want to work with large collections. Let's see how you can solve this problem.

')

Implementing containers on chunk

You can try to implement your containers on chunk-ak (in chunks, i.e. allocate memory for the array not in its entirety, but in small parts that do not fall into the LOH). With that directly on the chunk-ah you need to do only implement IList<T> , all other containers will use IList<T> as storage for their data.

Let's start to implement this list:

public class ChunkList<T> : IList<T>
{
private readonly int _ChunkSize = 4096;

private int _Count;
private T[][] _Chunks;
}

* This source code was highlighted with Source Code Highlighter .

In _Chunks we will store N pages by _ChunkSize objects in each, dynamically deleting or adding new pages. Actually, I will leave the implementation itself to those who wish as homework. It is not so complicated, you just need to carefully write all the operations.

But already in the code that I gave, there is an error. Error in default value for _ChunkSize . The fact is that for reference types this value is adequate, but for structures it is not. After all, the structure will occupy in the _Chunks array _Chunks much memory as its data. So you need to somehow find out the size of the data type T , and count the number of chunks as 85000/sizeof(T) . But despite the apparent simplicity, this problem is not easily solved.

If you turn to the article Computing the Size of a Structure , you can find the following solution to the problem of finding the size:

public static int GetSize<T>()
{
Type tt = typeof (T);
int size;
if (tt.IsValueType)
{
if (tt.IsGenericType)
{
var t = default (T);
size = Marshal.SizeOf(t);
}
else
{
size = Marshal.SizeOf(tt);
}
}
else
{
size = IntPtr .Size;
}
return size;
}

* This source code was highlighted with Source Code Highlighter .

So you can add our ChunkList :

public class ChunkList<T> : IList<T>
{
static ChunkList()
{
_ChunkSize = 80000 / GetSize<T>();
}

private static readonly int _ChunkSize = 4096;

private int _Count;
private T[][] _Chunks;
}

* This source code was highlighted with Source Code Highlighter .

Everything is good, but only in some cases (rather rare) this code will create an instance of the structure. If it does not matter, then you can leave. If it is important, you will have to create a constructor in which each user of the list will be able to independently transfer the size of the object or the desired size to the chunk.

How do you fight big objects?