Мы все привыкли писать 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 |
Когда мы устанавливаем начальную емкость, это не приводит к ненужным выделениям памяти, и мы видим лучшую производительность. И нет избыточного трафика памяти. Чем больше элементов мы добавляем в список, тем большую разницу мы видим в бенчмарках.
Анализатор
Если производительность критична для вашего проекта, вы должны обращать внимание на эти ситуации. Автоматическая диагностика может вам помочь. Я поддерживаю набор диагностических инструментов на основе Roslyn - Collections.Analyzer, и теперь он может обнаруживать списки с инициализатором коллекции и без начальной емкости.
Важно понимать, что анализатор устанавливает только начальный размер коллекции, чтобы избежать лишних аллокаций на начальном этапе заполнения коллекции. Он не может предсказать, как изменится размер коллекции в будущем.
Рекомендации
- Если вам нужна статическая коллекция, которую вы не будете изменять (добавлять или удалять элементы) — используйте массивы.
- Если вы создаете список и точно знаете его будущий размер — установите начальную емкость с этим размером.
- Если вы создаете список и не знаете его будущий размер — установите ожидаемый размер.