Memory: LOH and Chunked Lists

    Managed memory in .Net is divided into a stack and several heaps. The most important of the hips is the regular (ephemeral) heap and LOH. The ephemeral heap is the place where all ordinary objects live. LOH is the place where large (over 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 LOH size still remains unchanged)
    • Hip LOH is released only when LOH is completely empty

    Of these two features of LOH, there are two important consequences that are often forgotten:
    • The memory in the LOH may be fragmented. Those. something happens that was so fought in the unmanaged world: at some point you may have 10Mb of free memory, but you will not be able to 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 are actually depriving yourself of a large chunk of memory. Moreover, if you had a list or a hash table of size N in LOH, and you added one element to it, then the list is implemented and doubles, so the size of LOH will be at least 3 * N (N is the initial data, 2N - copy of data and reserve for a new size). The next growth will require in LOH a continuous piece of memory 4 * N in size, 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 LOH size will grow to 7 * N, and so on.


    If we recall that LOH is allocated by 16Mb chunks, then everything that happens will seem even more destructive. The first consequence can be carefully controlled using 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 to solve this problem.


    Container implementation on chunk


    You can try to implement your containers on chunk-ak (in pieces, i.e. allocate memory for the array not in its entirety, but in small parts that won’t fall into LOH). At what directly on chunk-ah it is necessary to do it is necessary to implement only , all other containers will be used as storage for their data. Let's start implementing the following list:IListIList



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

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

    * This source code was highlighted with Source Code Highlighter.


    In _Chunkswe will store Npages by _ChunkSizeobjects in each, dynamically deleting or adding new pages. Actually, I will leave the implementation itself to my wish as homework. It is not so complicated, you just need to carefully write all the operations.

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

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

    public static int GetSize()
    {
     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.


    Thus, we can supplement our ChunkList:

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

      private static readonly int _ChunkSize = 4096;

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

    * This source code was highlighted with Source Code Highlighter.


    Everything is fine, but only in some cases (rather rare) will this code create an instance of the structure. If it doesn’t matter, then you can leave it that way. 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 of the chunk.

    How do you deal with large objects?

    Also popular now: