Sequences

Reasons for Adding Custom Collections

In Talkie, as in many other projects, there is often a need to create a collection once and then only iterate over it in the future. Additionally, sometimes it's necessary to parallelize the iteration of elements in a collection.

In .NET, there are standard data types for these purposes, such as List, LinkedList, and Array. Each of them has its advantages and disadvantages. For example, their iteration speed via iterators leaves much to be desired. LinkedList is especially slow when iterating and not very fast when adding. As for List, it consumes excess memory (due to reserving space for future elements) and can cause lags when the internal array is recreated.

For parallel iteration of elements via the Parallel class, the standard Partitioner has a universal implementation for most collections. However, for certain cases, it is possible to achieve higher performance by evenly distributing the data between threads.

To address these issues, custom collections called Sequences (sequences) were added to Talkie.

Sequence Implementation

Any sequence implements the IReadOnlySequence or ISequence interface.

IReadOnlySequence allows only reading elements from the collection.

ISequence additionally allows adding them.

IReadOnlySequence inherits from IReadOnlyCollection and IParallelEnumerable. The IParallelEnumerable interface allows iterating over the collection in multiple threads simultaneously.

Two main sequences are implemented in Talkie: Sequence and FrozenSequence.

Sequence

Sequence is a sequence that allows adding elements to the end and iterating over them from the beginning. It implements the ISequence interface.

Features:

• Thread-safe only when iterating over elements. When adding elements, locks must be used to avoid race conditions.

• Slightly slower than List, but much faster than LinkedList.

• Does not allocate unnecessary memory and does not cause lags when adding elements.

FrozenSequence

FrozenSequence is a sequence that stores an array of elements. It creates a new array by copying data from the provided collection. It implements the IReadOnlySequence interface.

Features:

• Fully thread-safe.

• Extremely fast when iterating — faster than any array, List, or LinkedList.

• Iteration speed is comparable to ReadOnlySpan, but it does not depend on ref-struct.

Sequence Usage Recommendations

1. Using LINQ with Sequences

When we have a sequence of type IReadOnlySequence, it is recommended to cast it to the original type before iterating. For example:

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. If the exact type is unknown, use the Sequencing method

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

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

3. Iterating over FrozenSequence in an Async Method

When iterating over a FrozenSequence in an async method, the following approaches can be used:

The ForEach method (the fastest way):

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

4. Casting to Enumerable

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

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

5. Enumerating the sequence in parallel

For parallel iteration, use the standard Parallel.ForEach or the custom Parallelize method:

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

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

6. Properly Creating a FrozenSequence

When creating a new FrozenSequence from a static sequence, use the constructor:

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

To avoid keeping a reference to the original array, use the From method:

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

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

array[0] = 0; // does not change numbers, only array

7. To convert an object into a FrozenSequence, use the ToFrozenSequence method:

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

var numbers = array.ToFrozenSequence();