Spans and Slicing

Suppose that you’re writing a method to sum an array of integers. A micro-optimized implementation would avoid LINQ in favor of a foreach loop:

int Sum (int[] numbers)
{
  int total = 0;
  foreach (int i in numbers) total += i;
  return total;
}

Now imagine that you want to sum just a portion of the array. You have two options:

• First copy the portion of the array that you want to sum into another array

• Add additional parameters (offset and count)

The first option is inefficient; the second option adds clutter and complexity (which worsens with methods that need to accept more than one array).

Spans solve this nicely. All you need to do is to change the parameter type from int[] to ReadOnlySpan<int> (everything else stays the same):

int Sum (ReadOnlySpan<int> numbers)
{
  int total = 0;
  foreach (int i in numbers) total += i;
  return total;
}

We can test this method as follows:

var numbers = new int [1000];
for (int i = 0; i < numbers.Length; i++) numbers [i] = i;

int total = Sum (numbers);

We can call Sum with an array because there’s an implicit conversion from T[] to Span<T> and ReadOnlySpan<T>. Another option is to use the AsSpan extension method:

var span = numbers.AsSpan();

The indexer for ReadOnlySpan<T> uses C#’s ref readonly feature to reach directly into the underlying data: this allows our method to perform almost as well as the original example that used an array. But what we’ve gained is that we can now “slice” the array and sum just a portion of the elements as follows:

// Sum the middle 500 elements (starting from position 250):
int total = Sum (numbers.AsSpan (250, 500));

If you already have a Span<T> or ReadOnlySpan<T>, you can slice it by calling the Slice method:

Span<int> span = numbers;
int total = Sum (span.Slice (250, 500));

You can also use C# 8’s indices and ranges:

Span<int> span = numbers;
Console.WriteLine (span [^1]);            // Last element
Console.WriteLine (Sum (span [..10]));    // First 10 elements
Console.WriteLine (Sum (span [100..]));   // 100th element to end
Console.WriteLine (Sum (span [^5..]));    // Last 5 elements

Although Span<T> doesn’t implement IEnumerable<T> (it can’t implement interfaces by virtue of being a ref struct), it does implement the pattern, which allows C#’s foreach statement to work (see “Enumeration” in Chapter 4).

Span<int> x = new[] { 1, 2, 3, 4 };
Span<int> y = new int[4];
x.CopyTo (y);

Span<int> x = new[] { 1,  2,  3,  4  };
Span<int> y = new[] { 10, 20, 30, 40 };
x[..2].CopyTo (y[2..]);                 // y is now { 10, 20, 1, 2 }

int CountWhitespace (ReadOnlySpan<char> s)
{
  int count = 0;
  foreach (char c in s)
    if (char.IsWhiteSpace (c))
      count++;
  return count;
}

int x = CountWhitespace ("Word1 Word2");   // OK

int y = CountWhitespace (someString.AsSpan (20, 10));

var span = "This ".AsSpan();                    // ReadOnlySpan<char>
Console.WriteLine (span.StartsWith ("This"));   // True
Console.WriteLine (span.Trim().Length);         // 4

Memory<T>

Span<T> and ReadOnlySpan<T> are defined as ref structs to maximize their optimization potential as well as allowing them to work safely with stack-allocated memory (as you’ll see in the next section). However, it also imposes limitations. In addition to being array-unfriendly, you cannot use them as fields in a class (this would put them on the heap). This, in turn, prevents them from appearing in lambda expressions—and as parameters in asynchronous methods, iterators, and asynchronous streams:

async void Foo (Span<int> notAllowed)   // Compile-time error!

(Remember that the compiler processes asynchronous methods and iterators by writing a private state machine, which means that any parameters and local variables end up as fields. The same applies to lambda expressions that close over variables: these also end up as fields in a closure.)

The Memory<T> and ReadOnlyMemory<T> structs work around this, acting as spans that cannot wrap stack-allocated memory, allowing their use in fields, lambda expressions, asynchronous methods, and so on.

You can obtain a Memory<T> or ReadOnlyMemory<T> from an array via an implicit conversion or the AsMemory() extension method:

Memory<int> mem1 = new int[] { 1, 2, 3 };
var mem2 = new int[] { 1, 2, 3 }.AsMemory();

You can easily convert a Memory<T> or ReadOnlyMemory<T> into a Span<T> or Read​OnlySpan<T> via its Span property so that you can interact with it as though it were a span. The conversion is efficient in that it doesn’t perform any copying:

async void Foo (Memory<int> memory)
{
  Span<int> span = memory.Span;
  ...
}

(You can also directly slice a Memory<T> or ReadOnlyMemory<T> via its Slice method or a C# range, and access its length via its Length property.)

We said in the previous section that you cannot write the direct equivalent of string.Split for spans, because you cannot create an array of spans. This limitation does not apply to ReadOnlyMemory<char>:

// Split a string into words:
IEnumerable<ReadOnlyMemory<char>> Split (ReadOnlyMemory<char> input)
{
  int wordStart = 0;
  for (int i = 0; i <= input.Length; i++)
    if (i == input.Length || char.IsWhiteSpace (input.Span [i]))
    {
      yield return input [wordStart..i];   // Slice with C# range operator
      wordStart = i + 1;
    }
}

This is more efficient than string’s Split method: instead of creating new strings for each word, it returns slices of the original string:

foreach (var slice in Split ("The quick brown fox jumps over the lazy dog"))
{
  // slice is a ReadOnlyMemory<char>
}

Forward-Only Enumerators

In the preceding section, we employed ReadOnlyMemory<char> as a solution to implementing a string-style Split method. But by giving up on ReadOnlySpan<char>, we lost the ability to slice spans backed by unmanaged memory. Let’s revisit ReadOnlySpan<char> to see whether we can find another solution.

One possible option would be to write our Split method so that it returns ranges:

Range[] Split (ReadOnlySpan<char> input)
{
  int pos = 0;
  var list = new List<Range>();
  for (int i = 0; i <= input.Length; i++)
    if (i == input.Length || char.IsWhiteSpace (input [i]))
    {
      list.Add (new Range (pos, i));
      pos = i + 1;
    }
  return list.ToArray();
}

The caller could then use those ranges to slice the original span:

ReadOnlySpan<char> source = "The quick brown fox";
foreach (Range range in Split (source))
{
  ReadOnlySpan<char> wordSpan = source [range];
  ...
}

This is an improvement, but it’s still imperfect. One of the reasons for using spans in the first place is to avoid memory allocations. But notice that our Split method creates a List<Range>, adds items to it, and then converts the list into an array. This incurs at least two memory allocations as well as a memory-copy operation.

The solution to this is to eschew the list and array in favor of a forward-only enumerator. An enumerator is clumsier to work with, but it can be made allocation-free with the use of structs:

// We must define this as a ref struct, because _input is a ref struct.
public readonly ref struct CharSpanSplitter
{
  readonly ReadOnlySpan<char> _input;
  public CharSpanSplitter (ReadOnlySpan<char> input) => _input = input;
  public Enumerator GetEnumerator() => new Enumerator (_input);

  public ref struct Enumerator   // Forward-only enumerator
  {
    readonly ReadOnlySpan<char> _input;
    int _wordPos;
    public ReadOnlySpan<char> Current { get; private set; }

    public Rator (ReadOnlySpan<char> input)
    {
      _input = input;
      _wordPos = 0;
      Current = default;
    }

    public bool MoveNext()
    {
      for (int i = _wordPos; i <= _input.Length; i++)
        if (i == _input.Length || char.IsWhiteSpace (_input [i]))
        {
          Current = _input [_wordPos..i];
          _wordPos = i + 1;
          return true;
        }
      return false;
    }
  }
}

public static class CharSpanExtensions
{
  public static CharSpanSplitter Split (this ReadOnlySpan<char> input)
    => new CharSpanSplitter (input);

  public static CharSpanSplitter Split (this Span<char> input)
    => new CharSpanSplitter (input);
}

Here’s how you would call it:

var span = "the quick brown fox".AsSpan();
foreach (var word in span.Split())
{
  // word is a ReadOnlySpan<char>
}

By defining a Current property and a MoveNext method, our enumerator can work with C#’s foreach statement (see “Enumeration” in Chapter 4). We don’t have to implement the IEnumerable<T>/IEnumerator<T> interfaces (in fact, we can’t; ref structs can’t implement interfaces). We’re sacrificing abstraction for micro-optimization.

Working with Stack-Allocated and Unmanaged Memory

Another effective micro-optimization technique is to reduce the load on the garbage collector by minimizing heap-based allocations. This means making greater use of stack-based memory—or even unmanaged memory.

Unfortunately, this normally requires that you rewrite code to use pointers. In the case of our previous example that summed elements in an array, we would need to write another version:

unsafe int Sum (int* numbers, int length)
{
  int total = 0;
  for (int i = 0; i < length; i++) total += numbers [i];
  return total;
}

so that we could do this:

int* numbers = stackalloc int [1000];    // Allocate array on the stack
int total = Sum (numbers, 1000);

Spans solve this problem: you can construct a Span<T> or ReadOnlySpan<T> directly from a pointer:

int* numbers = stackalloc int [1000];
var span = new Span<int> (numbers, 1000);

Or in one step:

Span<int> numbers = stackalloc int [1000];

(Note that this doesn’t require the use of unsafe.) Recall the Sum method that we wrote previously:

int Sum (ReadOnlySpan<int> numbers)
{
  int total = 0;
  int len = numbers.Length;
  for (int i = 0; i < len; i++) total += numbers [i];
  return total;
}

This method works equally well for a stack-allocated span. We have gained on three counts:

• The same method works with both arrays and stack-allocated memory.

• We can use stack-allocated memory with minimal use of pointers.

• The span can be sliced.

You can also use spans to wrap memory that you allocate from the unmanaged heap. In the following example, we allocate unmanaged memory using the Marshal.AllocHGlobal function, wrap it in a Span<char>, and then copy a string into the unmanaged memory. Finally, we employ the CharSpanSplitter struct that we wrote in the preceding section to split the unmanaged string into words:

var source = "The quick brown fox".AsSpan();
var ptr = Marshal.AllocHGlobal (source.Length * sizeof (char));
try
{
  var unmanaged = new Span<char> ((char*)ptr, source.Length);
  source.CopyTo (unmanaged);
  foreach (var word in unmanaged.Split())
    Console.WriteLine (word.ToString());
}
finally { Marshal.FreeHGlobal (ptr); }

A nice bonus is that Span<T>’s indexer performs bounds-checking, preventing a buffer overrun. This protection applies if you correctly instantiate Span<T>: in our example, you would lose this protection if you wrongly obtained the span:

var span = new Span<char> ((char*)ptr, source.Length * 2);

There’s also no protection from the equivalent of a dangling pointer, so you must take care not to access the span after releasing its unmanaged memory with Marshal.FreeHGlobal.