Sequences (RU)

Причины добавления своих коллекций

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

В .NET существуют стандартные типы данных для этих целей, такие как List, LinkedList и Array. У каждого из них есть свои преимущества и недостатки. Например, их скорость перебора через итераторы оставляет желать лучшего. LinkedList особенно медленный при переборе и не слишком быстрый при добавлении. Что касается List, то он потребляет лишнюю оперативную память (из-за резервирования места для будущих элементов) и может вызывать лаги, когда внутренний массив пересоздаётся.

Для параллельного перебора элементов через Parallel класс стандартный Partitioner имеет универсальную реализацию для большинства коллекций. Однако для ряда случаев можно достичь более высокой производительности, равномерно распределяя данные между потоками.

Чтобы решить эти проблемы, в Talkie были добавлены свои собственные коллекции, называемые Sequences (последовательности).

Реализация последовательностей

Любая последовательность реализует интерфейс IReadOnlySequence или ISequence.

IReadOnlySequence позволяет только читать элементы из коллекции.

ISequence вдобавок позволяет их добавлять.

IReadOnlySequence наследуется от IReadOnlyCollection и IParallelEnumerable. Интерфейс IParallelEnumerable позволяет перебирать коллекцию одновременно в нескольких потоках.

В Talkie реализованы две основные последовательности: Sequence и FrozenSequence.

Sequence

Sequence — это последовательность, которая позволяет добавлять элементы в конец и перебирать их с начала. Реализует интерфейс ISequence.

Особенности:

• Потоко-безопасна только при переборе элементов. При добавлении элементов необходимо использовать блокировки, чтобы избежать гонок потоков.

• Чуть медленнее, чем List, но значительно быстрее, чем LinkedList.

• Не выделяет лишнюю память и не вызывает лагов при добавлении элементов.

FrozenSequence

FrozenSequence — это последовательность, которая хранит массив из элементов. Она создаёт новый массив, копируя данные из переданной коллекции. Реализует интерфейс IReadOnlySequence.

Особенности:

• Полностью потоко-безопасна.

• Очень быстрая при переборе — быстрее, чем любой массив, List или LinkedList.

• Скорость перебора сопоставима с ReadOnlySpan, но она не зависит от ref-struct.

Рекомендации по использованию последовательностей

1. Использование LINQ в последовательностях

Когда у нас есть последовательность с типом IReadOnlySequence, рекомендуется кастить её к оригинальному типу перед перебором. Например:

IReadOnlySequence<int> numbers = new FrozenSequence<int>(1, 2, 3);

if (numbers is FrozenSequence<int> castedNumbers)
{
    foreach (var number in castedNumbers) _ = number;
}
else
{
    foreach (var number in numbers) _ = number;
}

2. Если точный тип неизвестен, используйте метод Sequencing

IReadOnlySequence<int> numbers = new FrozenSequence<int>(1, 2, 3);

numbers.Sequencing().ForEach(number => _ = number);

3. Перебор FrozenSequence в асинхронном методе

При переборе FrozenSequence в асинхронном методе можно использовать следующие подходы:

Метод ForEach (самый быстрый способ):

async Task Async()
{
    var numbers = new FrozenSequence<int>(1, 2, 3);
    
    numbers.ForEach(number => _ = number);
}

4. Каст к Enumerable

async Task Async()
{
    var numbers = new FrozenSequence<int>(1, 2, 3);

    foreach (var number in numbers.AsEnumerable()) _ = number;
}

5. Перечисление последовательности параллельно

Для параллельного перебора используйте стандартный Parallel.ForEach или собственный метод Parallelize:

async Task Async()
{
    var numbers = new FrozenSequence<int>(1, 2, 3);

    numbers.Parallelize().ForEach((number, _) => _ = number);
    await numbers.Parallelize().ForEachAsync((number, _) => _ = number);
}

6. Правильное создание FrozenSequence

При создании новой FrozenSequence из статической последовательности используйте конструктор:

var numbers = new FrozenSequence<int>(1, 2, 3);

Чтобы избежать сохранения ссылки на исходный массив, используйте метод From:

var array = new int[] { 1, 2, 3 };

var numbers = FrozenSequence<int>.From(array);

array[0] = 0; // не изменяет numbers, а только array

7. Для преобразования объекта в FrozenSequence используйте метод ToFrozenSequence:

var array = new int[] { 1, 2, 3 };

var numbers = array.ToFrozenSequence();