Pull to refresh

Память: LOH и Chunked Lists

Reading time 3 min
Views 11K
Управляемая память в .Net поделена на стек и несколько хипов. Самые важные из хипов – это обычная (эфемерная) куча и LOH. Эфемерная куча – это то место, где живут все обычные объекты. LOH – это то место где живут большие (больше 85000 байт) объекты.

LOH обладает некоторыми особенностями:
  • Объекты в LOH никогда не перемещаются
  • LOH только растет и никогда не уменьшается (т.е. если объект собран сборщиком мусора, размер LOH все равно остается неизменным)
  • Хип LOH освобождается только тогда, когда LOH полностью пуст

Из этих двух особенностей LOH происходят два важных следствия, про которые часто забывают:
  • Память в LOH может оказаться фрагментированной. Т.е. происходит то, с чем так боролись в unmanaged мире: в какой-то момент у вас может быть 10Mb свободной памяти, но вы не сможете выделить память под объект размером 1Mb
  • Если вы однажды выделили память под большой объект, а потом используете только маленькие, то вы фактически лишаете себя большого куска памяти. При чем, если у вас в LOH был список или хэш-таблица размером N, а вы добавили в него один элемент, то список реаллоцируется и растет в два раза, сответственно размер LOH составит как минимум 3*N (N – исходные данные, 2N – копия данных и резерв под новый размер). Следующий рост потребует в LOH непрерывный кусок памяти размером в 4*N, а так как такого куска в LOH у нас нет (есть только N), его придется позаимствовать из адресного пространства процесса. В итоге размер LOH вырастет до 7*N, и так далее.


Если вспомнить, что LOH аллоцируется кусками по 16Mb, то все происходящее покажется еще более разрушительными. С первым следствием можно бороться аккуратно переиспользуя объекты. Со вторым — не используя большие объекты. Получается как-то не очень, особенно если с большими коллекциями работать все-таки хочется. Посмотрим, что как можно решить эту проблему.


Реализация контейнеров на chunk-ах


Можно попытаться реализовать свои контейнеры на chunk-ак (на кусках, т.е. выделять память под массив не целиком, а небольшими частями, которые не попадут в LOH). При чем непосредственно на chunk-ах надо делать надо реализовать только IList<T>, все остальные контейнеры будут использовать IList<T> как хранилище для своих данных.

Начнем реализовывать такой список:

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.


В _Chunks будем хранить N страниц по _ChunkSize объектов в каждой, динамически удаляя или добавляя новые страницы. Собственно, саму реализацию я оставлю желающим в качестве домашнего задания. Она не так и сложна, надо только аккуратно написать все операции.

Но уже в том коде, который я привел, есть ошибка. Ошибка в значении по-умолчанию для _ChunkSize. Дело в том, что для reference-типов это значение адекватно, а для структур – нет. Ведь структура будет занимать в массиве _Chunks столько памяти, сколько ее данные. Значит надо как-то узнать размер данных типа T, а количество chunks посчитать как 85000/sizeof(T). Но не смотря на кажущуюся простоту, эта задача легко не решается.

Если обратиться к статье Computing the Size of a Structure, то можно найти такое решение задачи поиска размера:

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.


Таким образом можно дополнить наш 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.


Все хорошо, но только в каких-то случаях (достаточно редких) этот код будет создавать экземпляр структуры. Если это неважно, то можно так и оставить. Если важно, то придется создать конструктор, в который каждый пользователь списка сможет самостоятельно передавать размер объекта или желаемый размер chunk-ов.

А вы как боретесь с большими объектами?
Tags:
Hubs:
+30
Comments 88
Comments Comments 88

Articles