Конкурентні та незмінні колекції

Конкурентні колекції

Простір імен System.Collections.Concurrent містить колекції, безпечні для одночасного використання з багатьох потоків без додаткової синхронізації в коді користувача (табл. 4.1). За документацією, ConcurrentQueue<T> і ConcurrentStack<T> взагалі не використовують блокувань, а спираються на Interlocked; інші колекції використовують дрібні блокування окремих частин.

Таблиця 4.1. Колекції простору імен System.Collections.Concurrent

Колекція	Порядок	Основні методи
ConcurrentQueue<T>	FIFO (черга)	Enqueue, TryDequeue, TryPeek, IsEmpty
ConcurrentStack<T>	LIFO (стек)	Push, PushRange, TryPop, TryPopRange
ConcurrentBag<T>	без порядку	Add, TryTake, TryPeek
ConcurrentDictionary<TKey, TValue>	за ключем	TryAdd, TryGetValue, TryRemove, TryUpdate, GetOrAdd, AddOrUpdate
BlockingCollection<T>	як у вкладеної колекції	Add, Take, CompleteAdding, GetConsumingEnumerable

Методи з префіксом Try поєднують перевірку й дію в одну атомарну операцію та повідомляють результат значенням bool:

ConcurrentQueue<Job> jobs = new();
jobs.Enqueue(new Job(1));

// Неправильно: між Count і Dequeue черга могла спорожніти.
// if (jobs.Count > 0) Process(jobs.Dequeue()); – методу Dequeue
// у ConcurrentQueue<T> немає саме тому.

if (jobs.TryDequeue(out Job? job))  // перевірити й вилучити атомарно
{
    Process(job);
}

Властивості Count та IsEmpty повертають стан на момент виклику, і до наступного рядка він уже може змінитися; для рішень їх не використовують. Перебір foreach черги, стеку й «мішка» працює зі знімком вмісту, а перебір ConcurrentDictionary безпечний під час змін, але не є знімком: він може побачити частину змін, зроблених під час перебору.

ConcurrentBag<T> («мішок») зберігає елементи без порядку й дозволяє дублікати. Кожен потік має власний локальний список (thread-local list): Add додає елемент у список поточного потоку, а TryTake спершу бере з нього і лише коли той порожній – «краде» елемент зі списку іншого потоку. Тому мішок ефективний, коли ті самі потоки і додають, і вилучають елементи (наприклад, пул повторно використовуваних буферів), і повільніший за чергу в класичній схемі, де одні потоки лише додають, а інші лише вилучають.

Словник ConcurrentDictionary

ConcurrentDictionary<TKey, TValue> – найуживаніша конкурентна колекція. Замість пари «перевірити – діяти» вона пропонує атомарні методи:

• TryAdd(key, value) – додати, якщо ключа немає;
• TryRemove(key, out value) – вилучити й повернути значення;
• TryUpdate(key, newValue, comparisonValue) – замінити значення, лише якщо поточне дорівнює comparisonValue (CAS для значення словника);
• GetOrAdd(key, valueFactory) – повернути наявне значення або створити й додати нове;
• AddOrUpdate(key, addValue, updateValueFactory) – додати або оновити на основі старого значення.

ConcurrentDictionary<string, int> counts = new();
// Атомарно «додати 1 або збільшити на 1» з будь-яких потоків.
counts.AddOrUpdate(word, 1, (_, old) => old + 1);

// Значення за замовчуванням створюється лише для нового ключа.
List<string> list = groups.GetOrAdd(key, _ => []);

Фабрики значень викликаються поза блокуванням

За документацією, делегати GetOrAdd і AddOrUpdate виконуються поза внутрішніми блокуваннями словника, щоб невідомий код користувача не спричинив взаємоблокування. Наслідки:

• якщо два потоки одночасно викликають GetOrAdd для відсутнього ключа, фабрика може виконатися двічі; у словник потрапить лише одне значення, а друге буде відкинуто;
• AddOrUpdate може викликати функцію оновлення кілька разів, якщо значення тим часом змінив інший потік; тому функція має бути чистою: лише обчислювати нове значення з old, без побічних ефектів (виведення, лічильників, запитів);
• об’єкт, повернутий GetOrAdd, сам не стає потокобезпечним: List<string> у прикладі вище змінювати з кількох потоків не можна.

Якщо фабрика дорога (завантаження файлу, довге обчислення) або має побічні ефекти, у словнику зберігають Lazy<T>. Кілька потоків можуть створити кілька об’єктів Lazy<T>, але до словника потрапить лише один, і всі потоки отримають саме його; Lazy<T> у режимі за замовчуванням (LazyThreadSafetyMode.ExecutionAndPublication) виконає обчислення один раз:

ConcurrentDictionary<string, Lazy<Report>> reports = new();

Report report = reports.GetOrAdd(name,
    key => new Lazy<Report>(() => BuildReport(key))).Value;

Незмінні та заморожені колекції

Інший підхід до спільних даних – взагалі їх не змінювати. Незмінні колекції (immutable collections) простору імен System.Collections.Immutable (ImmutableList<T>, ImmutableDictionary<TKey, TValue>, ImmutableHashSet<T>, ImmutableArray<T>, ImmutableQueue<T>, ImmutableStack<T>) після створення не змінюються. Метод Add повертає нову колекцію, яка спільно використовує більшу частину внутрішньої структури зі старою. Будь-яка кількість потоків читає незмінну колекцію без блокувань: кожен працює зі своїм знімком (snapshot), якого ніхто не змінить.

ImmutableList<string> v1 = ["red", "green"];
ImmutableList<string> v2 = v1.Add("blue");   // v1 не змінився

Щоб оновити спільне поле, яке посилається на незмінну колекцію, потрібна атомарна заміна посилання. Запис settings = settings.Add(x) із кількох потоків – знову гонитва «прочитати – змінити – записати». Клас ImmutableInterlocked виконує таку заміну через CAS: метод Update читає поточну колекцію, застосовує перетворення й записує результат, лише якщо поле тим часом не змінилося, інакше повторює перетворення:

private ImmutableList<Setting> settings = [];

public void Add(Setting item) =>
    ImmutableInterlocked.Update(ref settings, list => list.Add(item));

Для словників є ImmutableInterlocked.AddOrUpdate, GetOrAdd, TryAdd, TryUpdate, TryRemove, для стеку й черги – Push, TryPop, Enqueue, TryDequeue. Незмінні колекції зручні, коли читань значно більше, ніж записів: кожен запис створює нову версію, а при частих конкурентних записах перетворення доводиться багато разів повторювати.

Заморожені колекції (frozen collections) FrozenDictionary<TKey, TValue> і FrozenSet<T> простору імен System.Collections.Frozen (з .NET 8) створюються один раз методами ToFrozenDictionary і ToFrozenSet. Створення відносно дороге, зате пошук швидший, ніж у звичайного словника; змінити таку колекцію неможливо. Типовий сценарій – довідник, який завантажують під час запуску і потім лише читають з багатьох потоків. Щоб оновити довідник, будують нову заморожену колекцію та атомарно замінюють посилання (Interlocked.Exchange(ref catalog, newCatalog)).