День 1144. #ЗаметкиНаПолях #AsyncTips
Неизменяемые стеки и очереди

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

Решение
Неизменяемые стеки и очереди из пространства имён System.Collections.Immutable по поведению очень близки к стандартным коллекциям Stack<T> и Queue<T> и обладают практически такой же временной сложностью. Впрочем, в простых сценариях с частым обновлением стандартные стеки и очереди работают быстрее.

Неизменяемый стек

var stack = ImmutableStack<int>.Empty;
stack = stack.Push(13);
stack = stack.Push(7);

// Выводит "7", затем "13".
foreach (int item in stack)
  Console.WriteLine(item);

stack = stack.Pop(out int last);
// last == 7

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

var stack = ImmutableStack<int>.Empty;
stack = stack.Push(13);
var biggerStack = stack.Push(7);

// Выводит "7", затем "13".
foreach (int item in biggerStack)
  Console.WriteLine(item);

// Выводит только "13".
foreach (int item in stack)
  Console.WriteLine(item);

Во внутренней реализации два стека совместно используют память, выделенную для хранения элемента 13. Такая реализация весьма эффективна, к тому же она позволяет легко создавать снимки текущего состояния. Каждый экземпляр неизменяемой коллекции потокобезопасен по своей природе.

Неизменяемая очередь

var queue = ImmutableQueue<int>.Empty;
queue = queue.Enqueue(13);
queue = queue.Enqueue(7);
// Выводит "13", затем "7".
foreach (int item in queue)
  Console.WriteLine(item);

queue = queue.Dequeue(out int next);
// Выводит "13".
Console.WriteLine(next);

Вот некоторые важные принципы проектирования, справедливые для всех неизменяемых коллекций:
- Экземпляр неизменяемой коллекции никогда не изменяется.
- Экземпляр неизменяемой коллекции потокобезопасен по своей природе, но ссылка на него потокобезопасной не является. Переменная, ссылающаяся на неизменяемую коллекцию, нуждается в такой же синхронизационной защите, как и любая другая переменная.
- При вызове изменяющего метода для неизменяемой коллекции возвращается новая измененная коллекция.

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

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

Источник: Стивен Клири “Конкурентность в C#”. 2-е межд. изд. — СПб.: Питер, 2020. Глава 9.