Мы все привыкли писать 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 Benchmarks
{
    [ShortRunJob(RuntimeMoniker.Net48)]
    [ShortRunJob(RuntimeMoniker.Net60)]
    [ShortRunJob(RuntimeMoniker.Net80)]
    [MemoryDiagnoser]
    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.13.8, Windows 10 (10.0.19045.3930/22H2/2022Update)
AMD Ryzen 7 7840H with Radeon 780M Graphics, 1 CPU, 16 logical and 8 physical cores
.NET SDK 8.0.101
  [Host]                      : .NET 6.0.26 (6.0.2623.60508), X64 RyuJIT AVX2
  ShortRun-.NET 6.0           : .NET 6.0.26 (6.0.2623.60508), X64 RyuJIT AVX2
  ShortRun-.NET 8.0           : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2
  ShortRun-.NET Framework 4.8 : .NET Framework 4.8.1 (4.8.9195.0), X64 RyuJIT VectorSize=256

IterationCount=3  LaunchCount=1  WarmupCount=3  

Когда мы устанавливаем начальную емкость, это не приводит к ненужным выделениям памяти, и мы видим лучшую производительность. И нет избыточного трафика памяти. Чем больше элементов мы добавляем в список, тем большую разницу мы видим в бенчмарках.

Анализатор

Если производительность критична для вашего проекта, вы должны обращать внимание на эти ситуации. Автоматическая диагностика может вам помочь. Я поддерживаю набор диагностических инструментов на основе Roslyn - Collections.Analyzer, и теперь он может обнаруживать списки с инициализатором коллекции и без начальной емкости.

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

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

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

Ссылки

• Collection initializers
• Collections.Analyzer