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

#c_sharp #list

Пока писал диплом (использую вложенные 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. Если долго объяснять, посоветуйте что-нибудь почитать по этому поводу, если
эти вещи где-то объяснены. Да, я чайник, знаю.

Всем спасибо!
    

Ответы

Ответ 1

Число максимальных эелементов в списке будет зависеть от многих параметров. Но я
просто попытаюсь объяснить, как выделяется память под эти элементы внутри класса 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