Мы все привыкли писать new List<int> { 1, 2, 3, 4 } или new int[] { 1, 2, 3, 4 }, чтобы инициализировать коллекции какими-то значениями. Синтаксически это выглядит похоже, но поведение отличается, и вам следует быть осторожными, если вы заботитесь о производительности.
Массив
Как мы знаем, массивы содержат последовательность элементов фиксированного размера. После создания размер нельзя изменить в течение всего времени жизни массива.
var array = new int[] { 1, 2, 3, 4 };
List<T>
Когда мы не знаем конечный размер коллекции или нам нужно добавлять/удалять элементы в течение её жизненного цикла, подходит использование типа List<T>.
var list = new List<int>(); list.Add(1); list.Add(2);
На первый взгляд может показаться, что мы всегда можем использовать список вместо массива — у него есть все возможности массива, но его также можно динамически изменять. Но чтобы решить, использовать ли список, нам нужно больше узнать о его внутренней структуре.
Часть исходного кода:
public class List<T> : IList<T>, IList, IReadOnlyList<T> { private const int DefaultCapacity = 4; internal T[] _items; internal int _size; private static readonly T[] s_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 DefaultCapacity, and then increased in multiples of two // as required. public List() { _items = s_emptyArray; } ... public int Capacity { get => _items.Length; set {...} } public int Count => _size; }
_items— внутренний массив для хранения элементов;_size— количество элементов в массиве и общий размер списка;Capacity— размер массива_itemsи максимальное количество элементов, которые могут в него поместиться без изменения размера.
Изменение размера списка
Проще говоря, можно сказать, что список — это массив, который может изменять размер при необходимости.
Каждый раз, когда мы пытаемся добавить ещё один элемент, список проверяет, достаточно ли в _items свободного места, в противном случае он устанавливает новую ёмкость:
internal void Grow(int capacity) { ... int newCapacity = _items.Length == 0 ? DefaultCapacity : 2 * _items.Length; ... Capacity = newCapacity; }
Посмотрим поближе на свойство 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 => _items.Length; set { if (value < _size) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity); } 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; } } } }
Что мы видим? Изначально каждый список создаётся с пустым внутренним массивом. После добавления первого элемента список создает новый массив на 4 элемента (DefaultCapacity равно 4). И когда текущий массив исчерпан, создаётся новый с удвоенным размером, и все элементы копируются.
Производительность
Что происходит, когда мы создаем новый список и инициализируем его значениями?
var list = new List<int> { 1, 2, 3, 4, 5 };
Это выглядит как инициализация массива, но работает совершенно по-другому. Согласно документации, любой тип, который реализует IEnumerable и имеет метод Add может использоваться с инициализатором коллекции.
Таким образом, предыдущий пример — это просто краткая форма последовательных вызовов метода Add:
var list = new List<int>(); list.Add(1); list.Add(2); list.Add(3); list.Add(4); list.Add(5);
Компилятор просто преобразует короткий инициализатор коллекции и автоматически добавляет необходимые вызовы. И это может вызвать снижение производительности.
Давайте подробнее рассмотрим процесс добавления 5 элементов:
Перед первым вызовом
Addсписок пуст, внутренний массив пуст.Первый добавленный элемент создает новый внутренний массив на 4 элемента.
Элементы 2, 3, 4 при добавлении ничего не меняют.
Когда мы добавляем пятый элемент, внутренний массив заполнен и требует изменения размера. Создаётся новый массив размером 8, все элементы копируются из предыдущего массива, и добавляется пятый элемент.
В итоге у нас есть список с 5 элементами и внутренний массив на 8 элементов. При этом мы создали 2 массива, и конечный тратит 37.5% своего пространства впустую. Как вы могли догадаться, создание новых массивов и копирование элементов приводит к выделению памяти и занимает дополнительное время.
Это может стать неприятным сюрпризом в критически важных местах. Есть ли у нас решение? Да!
Capacity
Если мы знаем или предполагаем конечный размер списка, мы можем создать его с начальной ёмкостью (Capacity):
var list = new List<int>(5); list.Add(1); list.Add(2); list.Add(3); list.Add(4); list.Add(5);
Или
var list = new List<int>(5) { 1, 2, 3, 4, 5 };
Теперь мы сразу создаём один внутренний массив на 5 элементов и больше нет никаких ненужных выделений памяти.
Бенчмарк
Давайте сравним создание списков с начальной ёмкостью и без нее.
Код бенчмарка. Нажмите, чтобы развернуть.
using System.Collections.Generic; using BenchmarkDotNet.Attributes; using BenchmarkDotNet.Jobs; namespace ListBenchmark { [ShortRunJob(RuntimeMoniker.Net48)] [ShortRunJob(RuntimeMoniker.NetCoreApp31)] [ShortRunJob(RuntimeMoniker.Net80)] [ShortRunJob(RuntimeMoniker.Net10_0)] [MemoryDiagnoser] [HideColumns("Job", "Error", "StdDev", "Gen0")] public class InitListBenchmark { [BenchmarkCategory("One")] [Benchmark] public List<int> InitList1() { return new List<int> {1}; } [BenchmarkCategory("One")] [Benchmark] public List<int> InitListWithSize1() { return new List<int>(1) {1}; } [BenchmarkCategory("Five")] [Benchmark] public List<int> InitList5() { return new List<int> {1, 2, 3, 4, 5}; } [BenchmarkCategory("Five")] [Benchmark] public List<int> InitListWithSize5() { return new List<int>(5) {1, 2, 3, 4, 5}; } [BenchmarkCategory("Ten")] [Benchmark] public List<int> InitList10() { return new List<int> {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}; } [BenchmarkCategory("Ten")] [Benchmark] public List<int> InitListWithSize10() { return new List<int>(10) {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}; } } }
BenchmarkDotNet v0.15.6, Windows 10 (10.0.19045.6456/22H2/2022Update) AMD Ryzen 7 7840H with Radeon 780M Graphics 3.80GHz, 1 CPU, 16 logical and 8 physical cores .NET SDK 10.0.100 [Host] : .NET 10.0.0 (10.0.0, 10.0.25.52411), X64 RyuJIT x86-64-v4 ShortRun-.NET 10.0 : .NET 10.0.0 (10.0.0, 10.0.25.52411), X64 RyuJIT x86-64-v4 ShortRun-.NET 8.0 : .NET 8.0.22 (8.0.22, 8.0.2225.52707), X64 RyuJIT x86-64-v4 ShortRun-.NET Core 3.1 : .NET Core 3.1.32 (3.1.32, 4.700.22.55902), X64 RyuJIT VectorSize=256 ShortRun-.NET Framework 4.8 : .NET Framework 4.8.1 (4.8.9310.0), X64 RyuJIT VectorSize=256 IterationCount=3 LaunchCount=1 WarmupCount=3 | Method | Runtime | Mean | Allocated | |--------------------|--------------------|----------:|----------:| | InitList1 | .NET Framework 4.8 | 13.904 ns | 80 B | | InitListWithSize1 | .NET Framework 4.8 | 6.658 ns | 72 B | | InitList1 | .NET Core 3.1 | 11.091 ns | 72 B | | InitListWithSize1 | .NET Core 3.1 | 7.407 ns | 64 B | | InitList1 | .NET 8.0 | 10.084 ns | 72 B | | InitListWithSize1 | .NET 8.0 | 6.838 ns | 64 B | | InitList1 | .NET 10.0 | 8.170 ns | 72 B | | InitListWithSize1 | .NET 10.0 | 6.638 ns | 64 B | | InitList5 | .NET Framework 4.8 | 31.298 ns | 136 B | | InitListWithSize5 | .NET Framework 4.8 | 12.013 ns | 88 B | | InitList5 | .NET Core 3.1 | 26.466 ns | 128 B | | InitListWithSize5 | .NET Core 3.1 | 9.446 ns | 80 B | | InitList5 | .NET 8.0 | 23.714 ns | 128 B | | InitListWithSize5 | .NET 8.0 | 15.587 ns | 80 B | | InitList5 | .NET 10.0 | 20.002 ns | 128 B | | InitListWithSize5 | .NET 10.0 | 8.712 ns | 80 B | | InitList10 | .NET Framework 4.8 | 53.488 ns | 225 B | | InitListWithSize10 | .NET Framework 4.8 | 18.185 ns | 104 B | | InitList10 | .NET Core 3.1 | 44.371 ns | 216 B | | InitListWithSize10 | .NET Core 3.1 | 12.496 ns | 96 B | | InitList10 | .NET 8.0 | 38.707 ns | 216 B | | InitListWithSize10 | .NET 8.0 | 12.024 ns | 96 B | | InitList10 | .NET 10.0 | 33.854 ns | 216 B | | InitListWithSize10 | .NET 10.0 | 15.822 ns | 96 B |
Когда мы устанавливаем начальную ёмкость, это не приводит к ненужным выделениям памяти, и мы видим лучшую производительность. И нет избыточного трафика памяти. Чем больше элементов мы добавляем в список, тем большую разницу мы видим в бенчмарках.
История из жизни
В одном проекте в Контуре столкнулся с тем, что приложение держит гигабайты памяти — это некий огромный кэш, который поднимается в памяти на старте. Ну, казалось бы, бывает. Кэш этот нельзя было выбросить, но я решил посмотреть профайлером, из чего же он состоит. Оказалось, что почти вся память занята объектами типа
List<Data>. Нюанс же был в том, что создавались эти списки таким образом:new List<Data> { value }. Как вы можете догадаться, примерно 3/4 всей памяти было занято «пустотой».Решение было простым. Там, где коллекция точно не менялась, стал создаваться массив:
new[] { value }, в остальных же случаях обязательно стали указывать размер коллекции:new List<Data>(1) { value }.
Анализатор
Если производительность критична для вашего проекта, вы должны обращать внимание на эти ситуации. Автоматическая диагностика может вам помочь. Я поддерживаю набор диагностических инструментов на основе Roslyn — Collections.Analyzer, и теперь он может обнаруживать списки с инициализатором коллекции и без начальной ёмкости.
Важно понимать, что анализатор устанавливает только начальный размер коллекции, чтобы избежать лишних аллокаций на начальном этапе заполнения коллекции. Он не может предсказать, как изменится размер коллекции в будущем.
Рекомендации
Если вам нужна статическая коллекция, которую вы не будете изменять (добавлять или удалять элементы) — используйте массивы.
Если вы создаёте список и точно знаете его будущий размер — установите начальную ёмкость с этим размером.
Если вы создаёте список и не знаете его будущий размер — установите ожидаемый размер.
