Fast, potentially unsafe iteration

Daily Knowledge Drop

CollectionsMarshal, MemoryMarshal and Unsafe can be used in conjunction to create a very fast method of iteration (possibly the fastest method of performing for loops in C#)

Iteration

The technique may look a bit complex and complicated at first glance (or at least more complex than a normal for loop) - but going through it step-by-step it is actually relatively simple. This technique is also not as safe as the traditional method, due to the way memory is being handled in a potentially unsafe way.

The full code snippet is at the bottom of the section, but for now we'll have a look at it step-by-step.

Assume we have a list of 50 items we want to iterate through:

List<int> loopItems = Enumerable.Range(1, 50).ToList();

List to Span

The first step is to convert the List to a Span, using the System.Runtime.InteropServices.CollectionsMarshal.AsSpan method:

Span<int> itemsAsSpan = CollectionsMarshal.AsSpan(loopItems);

Once the Span is in use, (as per the documentation) items should not be added or removed from List.

Span reference

The next step is to get a reference to the element of the span at index 0:

ref int searchLocation = ref MemoryMarshal.GetReference(itemsAsSpan);

The variable searchLocation is effectively now pointing to the first item in the Span.

Iterate

Next, we can perform the actual iteration:

// for loop as per usual
for (int i = 0; i < itemsAsSpan.Length; i++)
{
    // Instead of using itemsAsSpan[i], which is still fast
    // we start with the first item (searchLocation)
    // and offset it by i items
    var item = Unsafe.Add(ref searchLocation, i);
    Console.WriteLine(item);
}

The for loop is defined as per normal, but instead of accessing the Span item at position i as one usually would (itemsAsSpan[i]), the Unsafe.Add method is used.

Unsafe.Add adds an element offset to the given reference - in this case it will use searchLocation, the first item in the Span as the given reference, and offset by i items each time. Each iteration, the offset is larger (as i increases) and as the given reference, searchLocation, stays the same the item being referenced each loop is different.

Code snippet

The full code snippet:

List<int> loopItems = Enumerable.Range(1, 50).ToList();
Span<int> itemsAsSpan = CollectionsMarshal.AsSpan(loopItems);

for (var i = 0; i < itemsAsSpan.Length; i++)
{
    var item = Unsafe.Add(ref searchLocation, i);
    Console.WriteLine(item);
}

Benchmarks

A full breakdown of the performance can be seen on Nick Chapsas's video, right here.

But in short, using the above method is the fastest way to iterate, slightly beating out using the index on the span (itemsAsSpan[i]), but significantly faster than all other methods (for loop, foreach loop etc)

Notes

This should probably not be the go-to iteration method for all applications in all use cases - however, when performance is critical and every fraction of a second is important, then this kind of optimization could make a difference. As mentioned, this technique is less "safe" than the usual for or foreach methods, so should be used with caution.

References

The weirdest way to loop in C# is also the fastest

Daily Drop 219: 09-12-2022

At the start of 2022 I set myself the goal of learning one new coding related piece of knowledge a day.
It could be anything - some.NET / C# functionality I wasn't aware of, a design practice, a cool new coding technique, or just something I find interesting. It could be something I knew at one point but had forgotten, or something completely new, which I may or may never actually use.

The Daily Drop is a record of these pieces of knowledge - writing about and summarizing them helps re-enforce the information for myself, as well as potentially helps others learn something new as well.