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

Конкурентные коллекции в C# предлагают встроенные механизмы для обработки конкурентного доступа, что делает их мощным инструментом в программировании с конкурентным доступом.

В рамках статьи я попробую объяснить System.Collections.Concurrent настолько, насколько это возможно, включая примеры и сценарии использования. Также будет затронута тема сравнения с неизменяемыми (immutable) и замороженными (frozen) коллекциями.

▍ Для чего нужны конкурентные коллекции в C#?

В C# 1.0 была представлена библиотека System.Collections, включающая в себя такие классы коллекций, как ArrayList, Hashtable, Stack, Queue и другие. Проблема с этими классами коллекций заключается в том, что они не являются типобезопасными. То есть они хранят элементы в виде объектов типа object, и из-за этого можно получить исключения, связанные с несоответствием типов, а также снижение производительности из-за упаковки и распаковки.

Далее, в C# 2.0 появилось пространство имён System.Collections.Generic вместе с классами коллекций List<T>, Dictionary<TKey, TValue>, Stack<T>, Queue<T> и другими, содержащимися внутри этого пространства имён. Эти классы коллекций безопасны с точки зрения типов, но не безопасны с точки зрения многопоточности. Типобезопасность означает, что необходимо каждый раз при создании экземпляра какой-либо обобщённой коллекции указывать тип, который будет храниться в этой коллекции, в качестве формального типового параметра. И всякий раз при получении какого-либо элемента из этой коллекции будет вытаскиваться реальный тип элемента. Это означает, что упаковка и распаковка не требуются.

Но классы обобщённых коллекций не гарантируют потокобезопасность. Поэтому обязанность разработчиков её обеспечить. Допустим, имеется словарь, который используется несколькими потоками. Тогда можно столкнуться с проблемами параллелизма, когда два или более потока пытаются получить доступ к элементам словаря в один и тот же момент времени. Например, такая ситуация может возникнуть при попытке одновременного добавления/удаления элементов из одного и того же словаря.

▍ Пример для понимания проблемы потокобезопасности с обобщёнными коллекциями в C#

В приведённом ниже примере был создан единый экземпляр словаря типа Dictionary<int, string> с целочисленным ключом и строковым значением. Затем были созданы два метода, а именно Method1 и Method2. Оба эти метода пытаются добавить некоторые элементы в словарь dictionary. Затем в рамках программы создаются два потока t1 и t2. Поток t1 указывает на Method1, а поток t2 — на Method2. И, наконец, происходит запуск обоих потоков через вызовы метода Start для одновременного исполнения двух методов.

Dictionary<int, string> dictionary = [];

var t1 = new Thread(Method1);
var t2 = new Thread(Method2);
t1.Start();
t2.Start();

void Method1()
{
    for (var i = 0; i < 10; i++)
    {
        dictionary.Add(i, "Added By Method1 " + i);
        Thread.Sleep(100);
    }
}

void Method2()
{
    for (var i = 0; i < 10; i++)
    {
        dictionary.Add(i, "Added By Method2 " + i);
        Thread.Sleep(100);
    }
}

Теперь при запуске приведённого выше кода с высокой долей вероятности программа выбросит исключение System.ArgumentException.

Unhandled exception. System.ArgumentException: An item with the same key has already been added. Key: 0
   at System.Collections.Generic.Dictionary`2.TryInsert(TKey key, TValue value, InsertionBehavior behavior)
   at System.Collections.Generic.Dictionary`2.Add(TKey key, TValue value)
   at Program.<>c__DisplayClass0_0.<<Main>$>g__Method2|1() in /Users/stepanminin/RiderProjects/ConsoleApp1/ConsoleApp1/Program.cs:line 22
   at System.Threading.Thread.StartCallback()

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

Соответственно, перед разработчиком встаёт закономерный вопрос: каким образом её гарантировать? Можно было бы воспользоваться примитивами синхронизации, но блокирование коллекции для любой операции с ней — не самое производительное решение.

Тут на помощь и приходят коллекции из пространства имён System.Collections.Concurrent, представленные в C# 4. Благодаря им стал возможен многопоточный доступ к распределённым ресурсам без использования явных блокировок, увеличивающий производительность приложения в сравнении с самостоятельным использованием примитивов синхронизации.

Соответственно, пример выше можно переписать, используя конкурентный словарь ConcurrentDictionary<TKey, TValue>, что позволит заставить программу работать и завершиться успешно. Обновлённый код выглядит следующим образом:

using System.Collections.Concurrent;

ConcurrentDictionary<int, string> dictionary = [];

var t1 = new Thread(Method1);
var t2 = new Thread(Method2);
t1.Start();
t2.Start();

// Не даём программе завершиться до завершения потоков t1 и t2
t1.Join();
t2.Join();

foreach (var item in dictionary)
    Console.WriteLine($"Key:{item.Key}, Value:{item.Value}");

void Method1()
{
    for (var i = 0; i < 10; i++)
    {
        dictionary.TryAdd(i, "Added By Method1 " + i);
        Thread.Sleep(100);
    }
}

void Method2()
{
    for (var i = 0; i < 10; i++)
    {
        dictionary.TryAdd(i, "Added By Method2 " + i);
        Thread.Sleep(100);
    }
}

И действительно, программа успешно завершается со следующим выводом, показывая содержимое словаря:

Key:0, Value:Added By Method2 0
Key:1, Value:Added By Method2 1
Key:2, Value:Added By Method2 2
Key:3, Value:Added By Method2 3
Key:4, Value:Added By Method1 4
Key:5, Value:Added By Method1 5
Key:6, Value:Added By Method2 6
Key:7, Value:Added By Method1 7
Key:8, Value:Added By Method1 8
Key:9, Value:Added By Method2 9

▍ System.Collections.Concurrent

Классы коллекций этого пространства имён предназначены для использования в сценариях с многопоточностью. К этим коллекциям могут обращаться несколько потоков одновременно, поэтому они называются конкурентными коллекциями. Они позволяют делиться данными между несколькими потоками безопасно. Далее, будут рассмотрены следующие классы коллекций:

• ConcurrentQueue<T>
• ConcurrentStack<T>
• ConcurrentDictionary<TKey, TValue>
• ConcurrentBag<T>
• BlockingCollection<T>

Однако прежде чем это будет сделано, необходимо учесть несколько важных моментов.

Для достижения потокобезопасности эти типы используют различные виды эффективных lock-free механизмов синхронизации. Что это за примитивы синхронизации? Обычно это вариации спинлоков с неблокирующим ожиданием. При таких примитивах синхронизации поток, пытающийся получить лок, ожидает в цикле, который раз за разом проверяет доступность этого лока.

В общем случае спинлок проверяет некоторое условие в бесконечном цикле, что позволяет возобновить работу потока на следующем такте процессора с нулевой стоимостью для операционной системы. В худшем случае активный поток может не дать процессору выполнять другую работу. То есть остальные потоки потратят очень много времени на ожидание. Поэтому спинлок предпочтительнее использовать для непродолжительных операций чтения или записи критической структуры данных. Более подробно про сценарий применения SpinLock можно прочитать на MSDN.

Некоторые из типов конкурентных коллекций используют облегчённые примитивы синхронизации, такие как SpinLock, SpinWait, SemaphoreSlim и CountdownEvent. Классы ConcurrentQueue<T> и ConcurrentStack<T> вообще не используют блокировки. Вместо этого они полагаются на операции Interlocked для достижения безопасности потоков.

Например, так выглядит реализация метода ConcurrentStack<T>.TryPop:

public bool TryPop([MaybeNullWhen(false)] out T result)
{
    Node? head = _head;
    //stack is empty
    if (head == null)
    {
        result = default(T)!;
        return false;
    }
    if (Interlocked.CompareExchange(ref _head, head._next, head) == head)
    {
        result = head._value;
        return true;
    }

    // Fall through to the slow path.
    return TryPopCore(out result);
}

Синхронизация добавляет накладные расходы на выполнение операции. Величина накладных расходов зависит от типа используемой синхронизации, типа выполняемых операций и других факторов, таких как количество потоков, которые пытаются одновременно получить доступ к коллекции.

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

Если важна производительность программы, то лучший способ подбора подходящей коллекции заключается в определении сценария использования, которым может оказаться один из приведённых ниже:

• Чистый producer-consumer.
  Любой поток либо добавляет, либо удаляет элементы, но не то и другое одновременно.
• Смешанный producer-consumer.
  Любой поток одновременно добавляет и удаляет элементы.
• Ускорение.
  Более высокая производительность алгоритма по сравнению с другим типом в том же сценарии.
• Масштабируемость.
  Увеличение производительности, пропорциональное количеству ядер в компьютере. Масштабируемый алгоритм работает быстрее на восьми ядрах, чем на двух.

Теперь перейдём к обзору самих классов конкурентных коллекций.

▍ ConcurrentQueue<T>

Потокобезопасный двойник обобщённой FIFO коллекции Queue<T>. Важные методы:

• Enqueue(T element): добавляет элемент типа T в коллекцию.
• TryPeek(out T): пытается получить следующий элемент из коллекции, не удаляя его. Если метод срабатывает успешно, то значение устанавливается в out параметр. В противном случае возвращается false.
• TryDequeue(out T): пытается получить первый элемент. Он удаляет элемент из коллекции и устанавливает параметр out в значение полученного элемента. В противном случае метод возвращает false.

Приставка «Try» в названиях методов подразумевает, что код должен подготовиться к событию, когда элемент не может быть получен. Если несколько потоков извлекают элементы из одной и той же очереди, нельзя быть уверенным в том, что в ней находится, когда конкретный поток пытается прочитать из неё.

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

Цикл while гарантирует, что элементы будут удаляться до тех пор, пока коллекция не останется пустой. После ожидания выполнения всех задач будет выведено количество обработанных элементов — счётчик должен иметь то же значение, что и количество элементов в очереди.

ConcurrentQueue<int> concurrentQueue = [];
for (var i = 0; i < 5000; i++)
    concurrentQueue.Enqueue(i);

var counter = 0;
var queueTasks = new Task[20];
for (var i = 0; i < queueTasks.Length; i++)
    queueTasks[i] = Task.Factory.StartNew(() =>
    {
        while (!concurrentQueue.IsEmpty)
        {
            var success = concurrentQueue.TryDequeue(out _);
            if (success)
                Interlocked.Increment(ref counter);
        }
    });

await Task.WhenAll(queueTasks);
Console.WriteLine($"Counter: {counter}");

В сценарии «чистый producer-consumer», где время обработки каждого элемента очень мало, ConcurrentQueue<T> может предложить скромные преимущества в производительности по сравнению с Queue<T>, имеющим внешнюю блокировку. В сценарии, когда один выделенный поток ставит в очередь и один выделенный поток снимает очередь, ConcurrentQueue<T> работает лучше всего. Если не соблюдать это правило, то на машинах с несколькими ядрами Queue<T> может работать даже немного быстрее, чем ConcurrentQueue<T>.

Когда время обработки составляет около 500 FLOPS (операций с плавающей запятой) или больше, правило двух потоков не применяется к ConcurrentQueue<T>, который в этом случае обладает очень хорошей масштабируемостью. Queue<T> не очень хорошо масштабируется в этом сценарии.

В сценарии «смешанный producer-consumer», когда время обработки очень мало, Queue<T> с внешней блокировкой масштабируется лучше, чем ConcurrentQueue<T>. Однако когда время обработки составляет около 500 FLOPS или более, ConcurrentQueue<T> масштабируется лучше.

▍ ConcurrentStack<T>

Потокобезопасный двойник обобщённой LIFO коллекции Stack<T>. Важные методы:

• Push(T element): добавляет элемент типа T в коллекцию.
• PushRange(T[] elements) и PushRange(T[] elements, int, int): то же самое, что и Push, но используется для добавления массива элементов в коллекцию.
• TryPeek(out T): пытается получить следующий элемент из коллекции, не удаляя его. Если метод срабатывает успешно, то значение устанавливается в out параметр. В противном случае возвращается false.
• TryPop(out T): пытается получить первый элемент. Он удаляет элемент из коллекции и устанавливает в out параметр-значение полученного элемента. В противном случае метод возвращает false.
• TryPopRange(out T[] elements) и TryPopRange(out T[], int, int): то же самое, что и TryPop, но используется для массивов.

В качестве примера можно написать программу, аналогичную той, что была представлена в предыдущем разделе про конкурентную очередь:

ConcurrentStack<int> concurrentStack = [];
concurrentStack.PushRange(Enumerable.Range(0, 5000).ToArray());

var counter = 0;
var stackTasks = new Task[20];
for (var i = 0; i < stackTasks.Length; i++)
    stackTasks[i] = Task.Factory.StartNew(() =>
    {
        while (!concurrentStack.IsEmpty)
        {
            var success = concurrentStack.TryPop(out _);
            if (success)
                Interlocked.Increment(ref counter);
        }
    });

await Task.WhenAll(stackTasks);
Console.WriteLine($"Counter: {counter}");

В сценарии «чистый producer-consumer», когда время обработки очень мало, ConcurrentStack<T> и Stack<T> с внешней блокировкой будут работать примерно одинаково с одним выделенным потоком, предназначенным для Push-операций, и одним выделенным потоком, предназначенным для Pop-операций. Однако при увеличении числа потоков оба типа замедляются из-за возрастающего соперничества, и Stack<T> может работать лучше, чем ConcurrentStack<T>. Когда время обработки составляет около 500 FLOPS или более, оба типа масштабируются примерно одинаково.

В сценарии «смешанный producer-consumer» ConcurrentStack<T> быстрее как для малых, так и для больших рабочих нагрузок.

Использование PushRange и TryPopRange может значительно ускорить время доступа.

▍ ConcurrentDictionary<TKey, TValue>

Потокобезопасный эквивалент стандартной коллекции пар ключ-значение, т.е. Dictionary<TKey, TValue>. Это, несомненно, самая универсальная коллекция из пространства имён System.Collections.Concurrent. Несмотря на отсутствие ConcurrentList или ConcurrentSet, можно имитировать список или множество с помощью ConcurrentDictionary. Таким образом, если действительно нужен безопасный для потоков список, то быстрым решением будет использование ConcurrentDictionary с ключом типа int и значением любого выбранного типа. Ключ тогда может обозначать позицию элемента в имитируемом списке.

В следующем примере будут созданы 20 задач, каждая из которых в цикле увеличивает некоторое значение в общем словаре на 1000. Таким образом, ожидается, что конечное значение будет равно 20000. Заполнение массива задач в цикле их запуск происходит по отдельности.

ConcurrentDictionary<int, int> concurrentDictionary = [];

var taskArray = new Task<int>[20];
for (var i = 0; i < taskArray.Length; i++)
{
    concurrentDictionary.TryAdd(i, 0);

    taskArray[i] = Task.Factory.StartNew(taskParameter =>
    {
        var key = Convert.ToInt32(taskParameter);
        for (var j = 0; j < 1000; j++)
        {
            concurrentDictionary.TryGetValue(key, out var current);
            concurrentDictionary.TryUpdate(key, current + 1, current);
        }

        var valueRetrieved = concurrentDictionary.TryGetValue(key, out var result);
        if (valueRetrieved)
            return result;

        throw new Exception($"No data item available for key {taskParameter}");
    }, i);
}

var resultArray = await Task.WhenAll(taskArray);
Console.WriteLine($"Expected value 20000, Actual: {resultArray.Sum()}");

Также неплохо понимать, что на определённом этапе пары ключ-значение в словаре могут выглядеть следующим образом:

key: 0, value: 40
key: 1, value 46
key: 2: value 43
.
.
.
key: 19, value 45

В общем случае используйте ConcurrentDictionary<TKey, TValue> в любом сценарии, где вы добавляете и обновляете ключи или значения одновременно из нескольких потоков. В сценариях с частыми обновлениями и относительно небольшим количеством чтений ConcurrentDictionary<TKey, TValue> обычно даёт скромные преимущества. В сценариях, предполагающих много чтений и много обновлений, ConcurrentDictionary<TKey, TValue> обычно значительно быстрее на компьютерах с любым количеством ядер.

В сценариях с частыми обновлениями можно увеличить степень параллелизма в ConcurrentDictionary<TKey, TValue> и затем проверить, увеличится ли производительность на компьютерах с большим количеством ядер. Если изменяется уровень параллелизма, то по возможности стоит избегать глобальных операций.

Если вы читаете только ключи или значения, то Dictionary<TKey, TValue> будет быстрее, потому что синхронизация не требуется, если словарь не изменяется никакими потоками.

▍ ConcurrentBag<T>

Это также потокобезопасная коллекция, но у неё нет конкретного однопоточного двойника. Это неупорядоченная коллекция, то есть нет заранее определённого порядка, в котором элементы извлекаются из ConcurrentBag. На практике ConcurrentBag будет работать похожим образом на ConcurrentDictionary.

В чём-то ConcurrentBag похож на ConcurrentStack ConcurrentQueue. Как уже было сказано, коллекция не упорядочена, то есть порядок элементов не совпадает с тем, как они были вставлены. Поэтому ConcurrentBag идеален, если требуется разделить, например, обобщённый список между несколькими задачами.

Важные методы:

• Add(T element): добавляет элемент типа T в коллекцию.
• TryPeek(out T): пытается получить следующий элемент из коллекции, не удаляя его. Если метод срабатывает успешно, то значение устанавливается в out параметр. В противном случае возвращается false.
• TryTake(out T): пытается получить первый элемент. Он удаляет элемент из коллекции и устанавливает значение полученного элемента в out параметр. В противном случае метод возвращает false.

В качестве примера можно написать программу, аналогичную той, что вы видели в разделах про конкурентные стек и очередь.

ConcurrentBag<int> concurrentBag = [];
for (var i = 0; i < 5000; i++)
    concurrentBag.Add(i);

var counter = 0;
var bagTasks = new Task[20];
for (var i = 0; i < bagTasks.Length; i++)
    bagTasks[i] = Task.Factory.StartNew(() =>
    {
        while (!concurrentBag.IsEmpty)
        {
            var success = concurrentBag.TryTake(out _);
            if (success)
                Interlocked.Increment(ref counter);
        }
    });

await Task.WhenAll(bagTasks);
Console.WriteLine($"Counter: {counter}");

В сценарии «чистый producer-consumer» ConcurrentBag<T>, вероятно, будет работать медленнее, чем другие типы конкурентных коллекций.

В сценарии «смешанный producer-consumer» ConcurrentBag<T>, как правило, работает гораздо быстрее и масштабируется лучше, чем любой другой тип конкурентной коллекции, как при больших, так и при малых рабочих нагрузках.

▍ BlockingCollection<T>

BlockingCollection — это ещё один потокобезопасный класс конкурентной коллекции в C#. Несколько потоков могут одновременно как добавлять, так и удалять объекты из BlockingCollection.

BlockingCollection реализует паттерн Producer-Consumer в C#. В этом паттерне есть два потока, один из которых называется Producer потоком, а другой — Consumer потоком. И самый важный момент заключается в том, что оба потока будут использовать общий ресурс для обмена данными между ними. В этом сценарии можно использовать BlockingCollection в качестве общего ресурса для Producer и Consumer потоков.

Producer поток будет генерировать данные, а Consumer поток — их потреблять. Также можно ограничить вместимость коллекции BlockingCollection. Как только установленный предел будет достигнут, Producer не сможет добавлять новые объекты, а Consumer не сможет удалять данные из пустой коллекции.

BlockingCollection имеет важную особенность, которая помогает реализовать паттерн Producer-Consumer и отличает его от других классов конкурентных коллекций в C#. Она заключается в поддержке bounding и blocking семантик:

• Bounding означает, как уже было сказано, возможность ограничить количество хранимых элементов в коллекции. Когда Producer поток достигает предела BlockingCollection, он блокируется для добавления новых объектов. На этапе блокировки Producer поток переходит в спящий режим. Он разблокируется, как только Consumer поток удалит объекты из коллекции.
• Blocking означает, как уже было сказано, что когда BlockingCollection пуста, Consumer поток блокируется до тех пор, пока Producer поток не добавит новые объекты в коллекцию.

В конце концов, Producer поток вызовет метод CompleteAdding, который установит свойство IsCompleted в true. Consumer поток внутренне отслеживает свойство IsCompleted, чтобы определить, есть ли элементы для потребления из коллекции.

В качестве примера для начала рассмотрим программу, где Producer поток добавляет элементы в коллекцию и помечает наполнение завершённым, а Consumer поток вычитывает в цикле эти элементы, пока IsCompleted не примет значение true:

BlockingCollection<int> blockingCollection = [];

var producerThread = Task.Factory.StartNew(() =>
{
    for (var i = 0; i < 10; i++)
        blockingCollection.Add(i);

    blockingCollection.CompleteAdding();
});

var consumerThread = Task.Factory.StartNew(() =>
{
    while (!blockingCollection.IsCompleted)
    {
        var item = blockingCollection.Take();
        Console.Write($"{item} ");
    }
});

await Task.WhenAll(producerThread, consumerThread);

Чтобы увидеть вживую bounding и blocking семантику, напишем программу, в которой Producer поток будет добавлять больше элементов, чем установлен предел вместимости, а Consumer поток будет медленно потреблять элементы, что позволит коллекции быстро наполниться:

var dataItems = new BlockingCollection<Data>(10);

var consumer = Task.Run(() =>
{
    var counter = 0;
    while (!dataItems.IsCompleted)
    {
        Data? data = null;
        try
        {
            data = dataItems.Take();
            counter++;
        }
        catch (InvalidOperationException)
        {
        }

        if (data != null)
            Console.WriteLine($"{counter}: {data}");
        Thread.SpinWait(100000);
    }

    Console.WriteLine("No more items to take.");
});

var producer = Task.Run(() =>
{
    for (var i = 0; i < 20; i++)
    {
        var data = Data.New();
        dataItems.Add(data);
        Console.WriteLine($"Add:{data} Number={dataItems.Count + 1}");
    }

    dataItems.CompleteAdding();
});

await Task.WhenAll(producer, consumer);

// ReSharper disable once NotAccessedPositionalProperty.Global
internal record Data(Guid Content)
{
    public static Data New() =>
        new(Content: Guid.NewGuid());
}

Иногда с коллекцией могут работать несколько потоков производителей и потребителей. В следующем примере три Producer-потока запущены для добавления новых элементов в BlockingCollection. В последнем цикле while вызывается TryTakeFromAny, чтобы удалить один элемент любой из трёх коллекций и вывести его на консоль:

BlockingCollection<int>[] producers =
[
    new BlockingCollection<int>(boundedCapacity: 10),
    new BlockingCollection<int>(boundedCapacity: 10),
    new BlockingCollection<int>(boundedCapacity: 10)
];

Task.Factory.StartNew(() =>
{
    for (var i = 1; i <= 10; i++)
    {
        producers[0].Add(i);
        Thread.Sleep(100);
    }

    producers[0].CompleteAdding();
});

Task.Factory.StartNew(() =>
{
    for (var i = 11; i <= 20; i++)
    {
        producers[1].Add(i);
        Thread.Sleep(150);
    }

    producers[1].CompleteAdding();
});

Task.Factory.StartNew(() =>
{
    for (var i = 21; i <= 30; i++)
    {
        producers[2].Add(i);
        Thread.Sleep(250);
    }

    producers[2].CompleteAdding();
});

while (!producers.All(producer => producer.IsCompleted))
{
    BlockingCollection<int>.TryTakeFromAny(
        producers,
        out var item,
        TimeSpan.FromSeconds(1));
    if (item != default)
    {
        Console.Write($"{item} ");
    }
}

Когда требуется bounding и blocking семантика, BlockingCollection<T>, вероятно, будет работать быстрее, чем любая пользовательская реализация.

▍ System.Collections.Immutable и System.Collections.Frozen

И вот прочитав всё это, кто-то может сказать: «да есть же неизменяемые коллекции!»

Действительно, в пространстве имён System.Collections.Immutable присутствуют аналоги стандартных коллекций, которые ведут себя по-другому при операциях обновления. Взять, например, неизменяемый стек:

var s1 = ImmutableStack<int>.Empty;
var s2 = s1.Push(1);
// s2 = [1]

var s3 = s2.Push(2);
// s2 = [1]
// s3 = [1,2]

// заметьте, что в s2 всё ещё один элемент

var s4 = s3.Pop(ref var i);

// s2 = [1];
// у s2 всё так же один элемент

Задерживаться на внутреннем устройстве коллекций не буду, об этом можно узнать в этой статье и из следующего доклада:

Очевидны две вещи: в силу своей неизменяемости такие коллекции имеют потокобезопасность в качестве побочного эффекта и перформят значительно хуже на операциях обновления. Соответственно, интересно их рассматривать с точки зрения read-only сценариев, либо редких обновлений, где накладными расходами на них можно пренебречь.

Однако если сделать простой бенчмарк для замера чтения, например, в словаре, то окажется, что ImmutableDictionary гораздо медленнее ConcurrentDictionary. Это не значит, что неизменяемые не стоит использовать. Наоборот, они значительно облегчают понимание работы конкретного кода, потому что гарантируют сохранность структуры данных и задают ограничения через API.

Также в .NET 8 представили новое пространство имён System.Collections.Frozen? содержащее две коллекции: FrozenDictionary и FrozenSet. Они вообще не допускают любых изменений и призваны использоваться в ситуациях, когда надо один раз загрузить некоторую конфигурацию и затем часто читать её:

private readonly FrozenDictionary<string, bool> _configuration = LoadConfiguration().ToFrozenDictionary();

// ...

if (_configuration.TryGetValue(key, out var setting) && setting)
    DoSomething();

Соответственно, в указанных read-only сценариях FrozenDictionary покажет себя гораздо лучше, чем ImmutableDictionary, в чём можно опять же убедиться из бенчмарков. Например, мой следующий бенчмарк:

public class DictionariesBenchmark
{
    private class Item
    {
        public int Id { get; set; }
        public int Value { get; set; }
    }

    [Params(1_000_000, 10_000_000)]
    public int ItemCount;

    private Item[] _itemList = [];
    private int[] _searchIds = [];

    private ConcurrentDictionary<int, Item> _concurrentDictionary = [];
    private ImmutableDictionary<int, Item> _immutableDictionary = ImmutableDictionary<int, Item>.Empty;
    private FrozenDictionary<int, Item> _frozenDictionary = FrozenDictionary<int, Item>.Empty;

    private Consumer _consumer = new();

    [GlobalSetup]
    public void Setup()
    {
        _itemList = new Item[ItemCount];
        _searchIds = new int[ItemCount];
        var rand = new Random();
        for (var i = 0; i < _itemList.Length; i++)
        {
            var item = new Item
            {
                Id = i,
                Value = Random.Shared.Next()
            };

            _searchIds[i] = item.Id;
            _itemList[i] = item;
            _concurrentDictionary.TryAdd(item.Id, item);
        }

        _immutableDictionary = _concurrentDictionary.ToImmutableDictionary();
        _frozenDictionary = _concurrentDictionary.ToFrozenDictionary();

        rand.Shuffle(_itemList);
    }

    [Benchmark]
    public void ConcurrentDictionarySearch()
    {
        foreach (var id in _searchIds)
        {
            if (!_concurrentDictionary.TryGetValue(id, out var result))
                continue;

            _consumer.Consume(result);
        }
    }

    [Benchmark]
    public void ImmutableDictionarySearch()
    {
        foreach (var id in _searchIds)
        {
            if (!_immutableDictionary.TryGetValue(id, out var result))
                continue;

            _consumer.Consume(result);
        }
    }

    [Benchmark]
    public void FrozenDictionarySearch()
    {
        foreach (var id in _searchIds)
        {
            if (!_frozenDictionary.TryGetValue(id, out var result))
                continue;

            _consumer.Consume(result);
        }
    }
}

Показал следующие результаты, которые вы вольны интерпретировать сами:

▍ Заключение

Если вы дошли до конца статьи, то, прежде всего, вы большой молодец, поскольку усвоили огромный пласт полезной и ценной информации.

Прочитав этот материал, вы узнали о том, для чего нужны конкурентные коллекции, какими они бывают, в каких ситуациях их предпочтительнее использовать, как с этим связаны immutable и frozen коллекции.

Ещё я веду Telegram-канал StepOne, куда выкладываю много интересного контента про коммерческую разработку, C# и мир IT глазами эксперта.

Telegram-канал со скидками, розыгрышами призов и новостями IT 💻