Using Span<T> to improve performance of C# code
Tags: csharp
Published: 2020-08-25 15:20:15

---
title: Using Span<T> to improve performance of C# code
published: true
description: This article shows how one can easily improve performance with this relatively new C# feature.
tags: csharp
cover_image: https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fwww.mywanderlust.pl%2Fwp-content%2Fuploads%2F2016%2F10%2FDSCF1228.jpg&f=1&nofb=1
canonical_url: https://wkalmar.github.io/post/improving-performance-with-span/
---

In my experience, the main thing to do in order to improve application performance is to reduce the number and duration of IO-calls. However, once this option is exercised another path that developers take is using memory on stack. Stack allows very fast allocation and deallocation although it should be used only for allocating small portions since stack size is pretty small. Also, using stack allows reducing pressure on GC. In order to allocate memory on stack, one uses [value types](https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/builtin-types/value-types) or `stackalloc` operator combined with the usage of unmanaged memory.

The second option is rarely used by developers since API for unmanaged memory access is quite verbose.

`Span<T>` is a family of value types that arrived in C# 7.2 which is an allocation-free representation of memory from different sources. `Span<T>` allows developers to work with regions of contiguous memory in more convenient fashion ensuring memory and type safety.

## Span<T> implementation
### Ref return
The first step in wrapping head around `Span<T>` implementation for those who don't closely follow updates in C# language is learning about [ref returns](https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/classes-and-structs/ref-returns) which were introduced in C# 7.0.

While most of the readers are familiar with passing method argument by reference, now C# allows returning a reference to a value instead of the value itself.

Let us examine how it works. We'll create a simple wrapper around an array of prominent musicians which exhibits both traditional behavior and new ref return feature.
```csharp
public class ArtistsStore
{
	private readonly string[] _artists = new[] { "Amenra", "The Shadow Ring", "Hiroshi Yoshimura" };

	public string ReturnSingleArtist()
	{
		return _artists[1];
	}

	public ref string ReturnSingleArtistByRef()
	{
		return ref _artists[1];
	}

	public string AllAritsts => string.Join(", ", _artists);
}
```

Now let's call those methods
```csharp
var store = new ArtistsStore();
var artist = store.ReturnSingleArtist();
artist = "Henry Cow";
var allArtists = store.AllAritsts; //Amenra, The Shadow Ring, Hiroshi Yoshimura

artist = store.ReturnSingleArtistByRef();
artist = "Frank Zappa";
allArtists = store.AllAritsts; //Amenra, The Shadow Ring, Hiroshi Yoshimura

ref var artistReference = ref store.ReturnSingleArtistByRef();
artistReference = "Valentyn Sylvestrov";
allArtists = store.AllAritsts; //Amenra, Valentyn Sylvestrov, Hiroshi Yoshimura
```
Observe that while in the first and the second example original collection is unmodified in the final example we've managed to alter the second artist of the collection. As you'll see later during the course of the article this useful feature will help us operate arrays located on the stack in a reference-like fashion.

### Ref structs
As we know value types might be allocated on stack. Also, they not necessarily do depending on the context where the value is used. In order to make sure that the value is always allocated on stack the concept of [ref struct](https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/builtin-types/struct?view=netcore-3.1#ref-struct) was introduced in C# 7.0. `Span<T>` is a `ref struct` so we are sure that is always allocated on stack.

### Span<T> implementation
`Span<T>` is a `ref struct` which contains a pointer to memory and length of the span similar to below.
```csharp
public readonly ref struct Span<T>
{
  private readonly ref T _pointer;
  private readonly int _length;
  public ref T this[int index] => ref _pointer + index;
  ...
}
```
Note `ref` modifier near the pointer field. Such construct can't be declared in a plain C# in .NET Core it is implemented via `ByReference<T>`.

So as you can see indexing is implemented via `ref return` which allows reference-type-like behavior for stack-only struct.

## Span<T> limitations
To ensure that the `ref struct` is always used on stack it possesses a number of limitations i.e. including that they can't be boxed, they can't be assigned to variables of type `object`, `dynamic` or to any interface type, they can't be fields in a reference type, and they can't be used across `await` and `yield` boundaries. In addition, calls to two methods, `Equals` and `GetHashCode`, throw a `NotSupportedException`. `Span<T>` is a `ref struct`.

## Using Span<T> instead of string
### Reworking existing codebase
Let's examine code that converts [Linux permissions](https://www.linux.com/training-tutorials/understanding-linux-file-permissions/) to octal representation. You can access it [here](https://github.com/Wkalmar/Orckestra/tree/span)
Here is the original code
```csharp
internal class SymbolicPermission
{
	private struct PermissionInfo
	{
		public int Value { get; set; }
		public char Symbol { get; set; }
	}

	private const int BlockCount = 3;
	private const int BlockLength = 3;
	private const int MissingPermissionSymbol = '-';

	private readonly static Dictionary<int, PermissionInfo> Permissions = new Dictionary<int, PermissionInfo>() {
			{0, new PermissionInfo {
				Symbol = 'r',
				Value = 4
			} },
			{1, new PermissionInfo {
				Symbol = 'w',
				Value = 2
			}},
			{2, new PermissionInfo {
				Symbol = 'x',
				Value = 1
			}} };

	private string _value;

	private SymbolicPermission(string value)
	{
		_value = value;
	}

	public static SymbolicPermission Parse(string input)
	{
		if (input.Length != BlockCount * BlockLength)
		{
			throw new ArgumentException("input should be a string 3 blocks of 3 characters each");
		}
		for (var i = 0; i < input.Length; i++)
		{
			TestCharForValidity(input, i);
		}

		return new SymbolicPermission(input);
	}

	public int GetOctalRepresentation()
	{
		var res = 0;
		for (var i = 0; i < BlockCount; i++)
		{
			var block = GetBlock(i);
			res += ConvertBlockToOctal(block) * (int)Math.Pow(10, BlockCount - i - 1);
		}
		return res;
	}

	private static void TestCharForValidity(string input, int position)
	{
		var index = position % BlockLength;
		var expectedPermission = Permissions[index];
		var symbolToTest = input[position];
		if (symbolToTest != expectedPermission.Symbol && symbolToTest != MissingPermissionSymbol)
		{
			throw new ArgumentException($"invalid input in position {position}");
		}
	}

	private string GetBlock(int blockNumber)
	{
		return _value.Substring(blockNumber * BlockLength, BlockLength);
	}

	private int ConvertBlockToOctal(string block)
	{
		var res = 0;
		foreach (var (index, permission) in Permissions)
		{
			var actualValue = block[index];
			if (actualValue == permission.Symbol)
			{
				res += permission.Value;
			}
		}
		return res;
	}
}

public static class SymbolicUtils
{
	public static int SymbolicToOctal(string input)
	{
		var permission = SymbolicPermission.Parse(input);
		return permission.GetOctalRepresentation();
	}
}
```

The reasoning is pretty straightforward: `string` is an array of `char`, so why not allocate it on stack instead of heap.

So our first goal is to mark field `_value` of `SymbolicPermission` as `ReadOnlySpan<char>` instead of `string`. To achieve this we must declare `SymbolicPermission` as `ref struct` since field or property cannot be of type `Span<T>` unless it's an instance of a `ref struct`.

```csharp
internal ref struct SymbolicPermission
{
	...
	private ReadOnlySpan<char> _value;
}
```

Now we just change every `string` within our reach to `ReadOnlySpan<char>`. The only point of interest is `GetBlock` method since here we replace `Substring` with `Slice`.
```csharp
private ReadOnlySpan<char> GetBlock(int blockNumber)
{
	return _value.Slice(blockNumber * BlockLength, BlockLength);
}
```

### Evaluation
Let's measure the outcome

<img src="https://wkalmar.github.io/7/1.PNG" width="600"/>

We notice the speed up which accounts for 50 nanoseconds which is about 10% of performance improvement. One can argue that 50 nanoseconds are not that much but it costed almost nothing for us to achieve it!

Now we're going to evaluate this improvement on permission having 18 blocks of 12 characters each to see whether we can gain significant improvements.

<img src="https://wkalmar.github.io/7/2.PNG" width="600"/>

As you can see we've managed to gain 0.5 microsecond or 5% performance improvement. Again it may look like a modest achievement. But remember that this was really low hanging fruit.

## Using Span<T> instead of arrays
Let's expand on arrays of other types. Consider the example from [ASP.NET Channels pipeline](https://github.com/davidfowl/Channels/blob/master/src/Channels.Text.Primitives/ReadableBufferExtensions.cs#L81). The reasoning behind the code below is that data often arrives in chunks over the network which means that the piece of data may reside in multiple buffers simultaneously. In the example such data is parsed to `int`.

```csharp
public unsafe static uint GetUInt32(this ReadableBuffer buffer) {
    ReadOnlySpan<byte> textSpan;

    if (buffer.IsSingleSpan) { // if data in single buffer, it’s easy
        textSpan = buffer.First.Span;
    }
    else if (buffer.Length < 128) { // else, consider temp buffer on stack
        var data = stackalloc byte[128];
        var destination = new Span<byte>(data, 128);
        buffer.CopyTo(destination);
        textSpan = destination.Slice(0, buffer.Length);
    }
    else {
        // else pay the cost of allocating an array
        textSpan = new ReadOnlySpan<byte>(buffer.ToArray());
    }

    uint value;
    // yet the actual parsing routine is always the same and simple
    if (!Utf8Parser.TryParse(textSpan, out value)) {
        throw new InvalidOperationException();
    }
    return value;
}
```

Let's break it down a bit about what happens here. Our goal is to parse the sequence of bytes `textSpan` into `uint`.
```csharp
if (!Utf8Parser.TryParse(textSpan, out value)) {
	throw new InvalidOperationException();
}
return value;
```
Now let's have a look at how we populate our input parameter into `textSpan`. The input parameter is an instance of a buffer that can read a sequential series of bytes. `ReadableBuffer` is inherited from `ISequence<ReadOnlyMemory<byte>>` which basically means that it consists of multiple memory segments.

In case buffer consists of a single segment we just use the underlying `Span` from the first segment.
```csharp
if (buffer.IsSingleSpan) {
	textSpan = buffer.First.Span;
}
```
Otherwise, we allocate data on the stack and create a `Span<byte>` based on it.
```csharp
var data = stackalloc byte[128];
var destination = new Span<byte>(data, 128);
```
Then we use method `buffer.CopyTo(destination)` which iterates over each memory segment of a buffer and copies it to a destination `Span`. After that we just slice a `Span` of buffer's length.
```csharp
textSpan = destination.Slice(0, buffer.Length);
```
This example shows us that the new `Span<T>` API allows us to work with memory manually allocated on a stack in a much more convenient fashion than prior to its arrival.

## Conclusion
`Span<T>` provides safe and easy to use alternative to `stackalloc` which allows easy to get performance improvement. While gain from each usage of it is relatively small the consistent usage of it allows to avoid what is known as a death by thousand cuts. `Span<T>` is widely used across .NET Core 3.0 codebase which allowed to get a [perfomance improvement comparing to the previous version](https://devblogs.microsoft.com/dotnet/performance-improvements-in-net-core-3-0/).

Here are some things you might consider when you decide whether you should use `Span<T>`:

- If your method accepts an array of data and doesn't change its size. If you don't modify an input you might consider `ReadOnlySpan<T>`.

- If your method accepts a string to count some statistics or to perform a syntactical analysis you should accept `ReadOnlySpan<char>`.

- If your method returns a short array of data you can return `Span<T>` with the help of `Span<T> buf = stackalloc T[size]`. Remember that `T` should be a value type.