Мы все привыкли писать 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, и теперь он может обнаруживать списки с инициализатором коллекции и без начальной ёмкости.

Важно понимать, что анализатор устанавливает только начальный размер коллекции, чтобы избежать лишних аллокаций на начальном этапе заполнения коллекции. Он не может предсказать, как изменится размер коллекции в будущем.

Рекомендации

• Если вам нужна статическая коллекция, которую вы не будете изменять (добавлять или удалять элементы) — используйте массивы.

• Если вы создаёте список и точно знаете его будущий размер — установите начальную ёмкость с этим размером.

• Если вы создаёте список и не знаете его будущий размер — установите ожидаемый размер.

Ссылки

• Collection initializers

• Collections.Analyzer