Размеры вложенных List в C#

Пока писал диплом (использую вложенные List < List<...>> c кучей данных), понадобилось проверить, сколько элементов влезает в List: оказалось, 33554432. В пересчёте (double - 8 байт) получается ровно 256 Мб памяти.
Далее я создал List < List< double>>: оказалось, что при максимальном количестве элементов внутреннего листа (всё те же 33554432) внешний лист успевает создать 3 внутренних - а потом происходит всё то же "System.OutOfMemoryException". То есть, в List< List> влезает уже 256 * 3 Мб.
А потом я создал всё тот же List< List< double>>, но при этом заполнял внутренний лист только на четверть от максимально возможного (33554432/4). Казалось бы, очевидно, что внешних листов должно получиться 12 (3 * 4=12) - но нет! Внешних листов создаётся 16. То есть, получается уже 256 * 4 Мб. А если заполнять внутренние количеством элементов (33554432/64), то внешних листов получается аж 265 (хотя 3 * 64=192) - то есть, 1060 Мб.
Уже ничего не понимая, я создал List< List< List< double>>>: при всё тех же максимально 33554432 элементах во внутреннем листе удаётся создать ровно два с половиной промежуточных листа -- после этого всё падает со всё тем же Exception'ом. То есть, получается 256 * 2,5 Мб.

Можете объяснить, как вообще выделяется память под List? И почему система не может занять пару гигабайт оперативки (у меня 4 Гб, х64), потом перейти в файл подкачки - и только потом откинуться со словами "System.OutOfMemoryException"? Зачем надо объявлять, что памяти больше нет, хотя её еще полно?
P.S. Если долго объяснять, посоветуйте что-нибудь почитать по этому поводу, если эти вещи где-то объяснены. Да, я чайник, знаю.
Всем спасибо!

Ответ

Число максимальных эелементов в списке будет зависеть от многих параметров. Но я просто попытаюсь объяснить, как выделяется память под эти элементы внутри класса List
List - это ничто иное как обертка над обычным массивом T[]. Этот массив инициализируется при создании списка, либо инициализируется повторно уже в процессе работы с созданным списком. Первый случай довольно прост - это начальная инициализация, которая происходит при вызове конструкторов. Немного кода из класса List
private const int _defaultCapacity = 4; private T[] _items; static T[] _emptyArray = new T[0];
// Constructs a List. The list is initially empty and has a capacity // of zero. Upon adding the first element to the list the capacity is // increased to 16, and then increased in multiples of two as required. public List() { _items = _emptyArray; }
// Constructs a List with a given initial capacity. The list is // initially empty, but will have room for the given number of elements // before any reallocations are required. public List(int capacity) { if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_SmallCapacity); _items = new T[capacity]; }
Второй случай может произойти во время добавления в список новых элементов или при присвоении нового значение свойству Capacity. Рассмотрим случай с добавлением новых элементов. Из комментария над первым конструктором видно, что размер внутреннего массива увеличивается вдвое. Происходит это тогда, когда текущий массив уже полностью занят элементами. Соответствующий код:
// Gets and sets the capacity of this list. The capacity is the size of // the internal array used to hold items. When set, the internal // array of the list is reallocated to the given capacity. public int Capacity { get { return _items.Length; } set { if (value != _items.Length) { if (value < _size) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity); }
if (value > 0) { T[] newItems = new T[value]; if (_size > 0) { Array.Copy(_items, 0, newItems, 0, _size); } _items = newItems; } else { _items = _emptyArray; } } } }
// Ensures that the capacity of this list is at least the given minimum // value. If the currect capacity of the list is less than min, the // capacity is increased to twice the current capacity or to min, // whichever is larger. private void EnsureCapacity(int min) { if (_items.Length < min) { int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2; if (newCapacity < min) newCapacity = min; Capacity = newCapacity; } }
Метод EnsureCapacity вызывается внутри всех методов списка, добавляющих в него новые элементы (Add(), Insert() и т.д.).
Какой из этого всего можно сделать вывод? Во время добавления элементов в список наступают моменты, когда памяти под элементы выделено в 3 раза больше, чем требуется на самом деле (момент, когда создался новый, в 2 раза больший массив и в него копируются данные из старого массива).
Исходники смотрел здесь: .NET List sources