Особенности реализации List в C#
List является одной из самых популярных коллекций в C#. Давайте разберёмся в некоторых особенностях работы с ним и посмотрим на внутреннюю реализацию его отдельных частей.
Введение
Данная статья будет посвящена полностью List
Внутри List
Исходный код класса List
Класс List
Класс List
T[] _items — внутренний массив, на основе которого строится список;
int _size — хранит информацию о количестве элементов в списке;
int _version — содержит версию коллекции.
Добавление элемента в список
Как уже было сказано, размер списка динамически изменяется. Взглянем поподробнее, что же происходит при добавлении элемента в список.
public void Add(T item)
{
_version++;
T[] array = _items;
int size = _size;
if ((uint)size < (uint)array.Length)
{
_size = size + 1;
array[size] = item;
}
else
{
AddWithResize(item);
}
}
В первую очередь значение поля _version увеличивается на 1 (смысл данного действия мы разберём чуть позже). После этого происходит создание двух локальных переменных — массива array с элементами типа T и size типа int. Им присваиваются соответствующие поля. Далее если в массиве ещё есть место для одного элемента, то происходит изменение элемента массива по индексу size + 1. Если же размер массива не позволяет добавить ещё один элемент, то вызывается метод AddWithResize.
private void AddWithResize(T item)
{
Debug.Assert(_size == _items.Length);
int size = _size;
Grow(size + 1);
_size = size + 1;
_items[size] = item;
}
Здесь вызывается метод Grow для увеличения текущего размера внутреннего массива. Далее производятся те же действия, что и в методе Add, для добавления при доступном месте.
Рассмотрим метод Grow подробнее:
private void Grow(int capacity)
{
....
int newcapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length;
if ((uint)newcapacity > Array.MaxLength) newcapacity = Array.MaxLength;
if (newcapacity < capacity) newcapacity = capacity;
Capacity = newcapacity;
}
Алгоритм работы метода Grow:
если внутренний массив пуст, то ёмкость списка будет равна 4, иначе удвоенной длине массива;
если новое значение ёмкости получается больше максимально возможной длины массива, то данная ёмкость станет равна Array.MaxLength;
если новое значение ёмкости коллекции получилось меньше текущего, то новая ёмкость станет равна текущей;
в конце newcapacity записывается в свойство Capacity.
Зачем нужно поле _version?
Но зачем же всё-таки нужно поле _version, значение которого менялось в методе Add? Как уже было написано ранее, это поле, которое позволяет отслеживать версию списка. Его значение проверяется при обходе списка. К примеру, рассмотрим метод ForEach:
public void ForEach(Action action)
{
....
int version = _version;
for (int i = 0; i < _size; i++)
{
if (version != _version)
{
break;
}
action(_items[i]);
}
if (version != _version)
ThrowHelper
.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
Перед началом обхода значение поля _version сохраняется в переменную. Если во время обхода список будет изменён, то обход прекращается и выбрасывается исключение типа System.InvalidOperationException. Похожим образом _version отслеживается и в List
Capacity
У List
List list = new List(8);
Если разработчик заранее знает нужный размер списка, то он может задать его. Это избавляет от ненужных операций копирования и выделения памяти под новый массив при добавлении новых элементов.
Кстати, размером внутреннего массива можно управлять, ещё и используя свойство Capacity:
list.Capacity = 8;
Рассмотрим код данного свойства:
public int Capacity
{
get => _items.Length;
set
{
if (value < _size)
{
ThrowHelper.ThrowArgumentOutOfRangeException(....);
}
if (value != _items.Length)
{
if (value > 0)
{
T[] newItems = new T[value];
if (_size > 0)
{
Array.Copy(_items, newItems, _size);
}
_items = newItems;
}
else
{
_items = s_emptyArray;
}
}
}
}
Аксессор get возвращает значение _items.Length, то есть длину внутреннего массива.
Аксессор set действует по следующему алгоритму:
если value меньше количества элементов в коллекции, то будет выброшено исключение;
если value не равно длине внутреннего массива и value больше 0, то будет создан новый массив с ёмкостью, равной value;
если количество элементов в списке больше 0, то будет выполнено копирование элементов из старого массива в новый;
если value равно 0, то полю, которое представляет собой внутренний массив, будет присвоен пустой массив.
Прочие особенности методов List
Insert
Метод Insert позволяет вставить элемент в коллекцию только в рамках начала и конца этой коллекции. Если количество элементов в коллекции будет равно размерности внутреннего массива, то произойдёт увеличение ёмкости массива с помощью метода Grow (_size + 1). При попытке вставить элемент на индекс, который больше list.Count, будет выброшено исключение System.ArgumentOutOfRangeException.
List list = new List() { "1", "2"};
list.Insert(1, "10"); // OK
list.Insert(2, "15"); // OK
list.Insert(10, 12); // throw exception
Подобное поведение останется даже при явном управлении размером внутреннего массива.
Рассмотрим пример:
List list = new List() { "1", "2"};
list.Capacity = 8;
list.Insert(3, "3");
В свойство Capacity присваивается 8, что приводит к изменению размера внутреннего массива. Однако это не даёт возможности вставить элемент на позицию, превышающую list.Count. Результатом выполнения приведённого кода будет выбрасывание исключения.
Clear
Данный метод производит очистку коллекции. В результате этой операции свойство Count будет иметь значение 0. Элементы коллекции ссылочного типа получают значение по умолчанию. Если элементы коллекции являются структурами и имеют поля ссылочного типа, то данные поля тоже получат значение по умолчанию. Стоит заметить, что размер внутреннего массива остаётся неизменным. Если до вызова Clear свойство Capacity было равно 8, то и после Clear размер массива останется равным 8. Для освобождения памяти, выделяемой под сам массив, необходимо после Clear вызвать метод TrimExcess.
TrimExcess
Данный метод делает размер внутреннего массива равным количеству элементов в списке. Его стоит использовать, например, когда вы знаете, что в коллекцию больше не будут добавлены новые элементы.
list.Clear();
list.TrimExcess();
Sort и OrderBy
Между двумя этими методами есть несколько различий:
метод Sort принадлежит классу List
, а метод OrderBy является методом расширения из LINQ; метод Sort модифицирует исходную коллекцию, а OrderBy возвращает отсортированную копию с типом IOrderedEnumerable
; метод OrderBy производит устойчивую сортировку, а Sort — нет. Если вы используете метод Sort, то эквивалентные элементы могут быть переупорядочены.
Немного о производительности
List против ArrayList
List
List list = new List();
Джеффри Рихтер в своей книге «CLR via C#» приводит следующие преимущества обобщений:
защита исходного кода;
безопасность типов;
более простой и понятный код;
повышение производительности.
В той же книге в начале 12-ой главы про обобщения имеется хороший пример сравнения List
Пример кода для тестирования ArrayList со значимым типом:
public void ValueTypeArrayList()
{
ArrayList a = new ArrayList();
for (Int32 n = 0; n < _count; n++)
{
a.Add(n);
Int32 x = (Int32)a[n];
}
}
Тестирование производилось с объектами значимых (Int32) и ссылочных (String) типов.
Переписав приведённый в книге код и протестировав его с помощью BenchmarkDotNet, я получил следующие результаты:
Из результатов видно, что c Int32 алгоритм List
Из-за того что при работе ArrayList производится множество операций упаковки, увеличивается и число сборок мусора. При этом получение элемента требует выполнения распаковки. Всё это приводит к снижению производительности.
Разница при использовании ссылочных типов несущественная, так как нет операций упаковки и распаковки, которые являются очень тяжёлыми. Судя по коду, небольшая разница в скорости появляется из-за операции преобразования типов.
Преимущества задания Capacity
Как уже было сказано ранее, если разработчик заранее знает размер списка, то он может указать его.
Проведём небольшой тест.
public void ListWithoutCapacity()
{
for (int i = 0; i < Count; i++)
{
List list = new List();
for (int j = 0; j < Length; j++)
{
list.Add(j);
}
}
}
В данном случае происходит добавление в list 150 000 элементов. Для наглядности проведём эту операцию 1000 раз. И сравним производительность с таким же методом, но с указанным capacity, который равен количеству операций добавления.
Из результатов видно, что затраченное время на выполнение метода без capacity в 2 раза больше, чем с заранее установленным. Также памяти выделяется почти в 4 раза больше. Подобные действия убирают 17 ненужных операций копирования на каждой итерации внешнего цикла.
Как быстрее всего определить, что в списке есть элементы?
Возьмём три варианта определения того, что список непустой:
использовать метод Count из LINQ и сравнить результат с 0;
использовать свойство Count и сравнить результат с 0;
использовать метод расширения Any из LINQ.
Проведя тестирование, получаем следующие результаты для списка из 1 500 000 элементов:
Самым быстрым оказался доступ к свойству Count, так как оно просто возвращает значение поля _size.
Метод Count пытается преобразовать исходную коллекцию к ICollection. При успешном преобразовании метод вернёт значение свойства Count. В случае неудачи потребуется обойти всю коллекцию для высчитывания количества элементов. К счастью, List
Метод Any при обнаружении хотя бы одного элемента в коллекции вернёт true.
Заключение
Можно сказать, что List
C# содержит ещё множество коллекций, которые помогают в работе разработчикам. Какие-то из них более специфичные, а какие-то менее. Надеюсь, что данная статья поможет вам в работе и сделает ваше понимание списков чуть лучше:).
Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Artem Rovenskii. List in C#: implementation and features.
