Span<T> usage examples

A human by nature cannot fully understand the purpose of a certain instrument until he or she gets some experience. So, let’s turn to some examples.

ValueStringBuilder

One of the most interesting examples in respect to algorithms is the ValueStringBuilder type. However, it is buried deep inside mscorlib and marked with the internal modifier as many other very interesting data types. This means we would not find this remarkable instrument for optimization if we haven’t researched the mscorlib source code.

What is the main disadvantage of the StringBuilder system type? Its main drawback is the type and its basis — it is a reference type and is based on char[], i.e. a character array. At least, this means two things: we use the heap (though not much) anyway and increase the chances to miss the CPU cash.

Another issue with StringBuilder that I faced is the construction of small strings, that is when the resulting string must be short e.g. less than 100 characters. Short formatting raises issues on performance.

This chapter was translated from Russian jointly by author and by professional translators. You can help us with translation from Russian or English into any other language, primarily into Chinese or German.

Also, if you want thank us, the best way you can do that is to give us a star on github or to fork repository github/sidristij/dotnetbook.

    $"{x} is in range [{min};{max}]"

To what extent is this variant worse than manual construction through StringBuilder? The answer is not always obvious. It depends on the place of construction and the frequency of calling this method. Initially, string.Format allocates memory for internal StringBuilder that will create an array of characters (SourceString.Length + args.Length * 8). If during array construction it turns out that the length was incorrectly determined, another StringBuilder will be created to construct the rest. This will lead to the creation of a single linked list. As a result, it must return the constructed string which means another copying. That is a waste. It would be great if we could get rid of allocating the array of a formed string on the heap: this would solve one of our problems.

Let’s look at this type from the depth of mscorlib:

ValueStringBuilder class
/src/mscorlib/shared/System/Text/ValueStringBuilder

    internal ref struct ValueStringBuilder
    {
        // this field will be active if we have too many characters
        private char[] _arrayToReturnToPool;
        // this field will be the main
        private Span<char> _chars;
        private int _pos;
        // the type accepts the buffer from the outside, delegating the choice of its size to a calling party
        public ValueStringBuilder(Span<char> initialBuffer)
        {
            _arrayToReturnToPool = null;
            _chars = initialBuffer;
            _pos = 0;
        }

        public int Length
        {
            get => _pos;
            set
            {
                int delta = value - _pos;
                if (delta > 0)
                {
                    Append('\0', delta);
                }
                else
                {
                    _pos = value;
                }
            }
        }

        // Here we get the string by copying characters from the array into another array
        public override string ToString()
        {
            var s = new string(_chars.Slice(0, _pos));
            Clear();
            return s;
        }

        // To insert a required character into the middle of the string
        //you should add space into the characters of that string and then copy that character
        public void Insert(int index, char value, int count)
        {
            if (_pos > _chars.Length - count)
            {
                Grow(count);
            }

            int remaining = _pos - index;
            _chars.Slice(index, remaining).CopyTo(_chars.Slice(index + count));
            _chars.Slice(index, count).Fill(value);
            _pos += count;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Append(char c)
        {
            int pos = _pos;
            if (pos < _chars.Length)
            {
                _chars[pos] = c;
                _pos = pos + 1;
            }
            else
            {
                GrowAndAppend(c);
            }
        }

        [MethodImpl(MethodImplOptions.NoInlining)]
        private void GrowAndAppend(char c)
        {
            Grow(1);
            Append(c);
        }

        // If the original array passed by the constructor wasn’t enough
        // we allocate an array of a necessary size from the pool of free arrays
        // It would be ideal if the algorithm considered
        // discreteness of array size to avoid pool fragmentation. 
        [MethodImpl(MethodImplOptions.NoInlining)]
        private void Grow(int requiredAdditionalCapacity)
        {
            Debug.Assert(requiredAdditionalCapacity > _chars.Length - _pos);

            char[] poolArray = ArrayPool<char>.Shared.Rent(Math.Max(_pos + requiredAdditionalCapacity, _chars.Length * 2));

            _chars.CopyTo(poolArray);

            char[] toReturn = _arrayToReturnToPool;
            _chars = _arrayToReturnToPool = poolArray;
            if (toReturn != null)
            {
                ArrayPool<char>.Shared.Return(toReturn);
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void Clear()
        {
            char[] toReturn = _arrayToReturnToPool;
            this = default; // for safety, to avoid using pooled array if this instance is erroneously appended to again
            if (toReturn != null)
            {
                ArrayPool<char>.Shared.Return(toReturn);
            }
        }

        // Missing methods:  the situation is crystal clear
        private void AppendSlow(string s);
        public bool TryCopyTo(Span<char> destination, out int charsWritten);
        public void Append(string s);
        public void Append(char c, int count);
        public unsafe void Append(char* value, int length);
        public Span<char> AppendSpan(int length);
    }

This class is functionally similar to its senior fellow StringBuilder, although having one interesting and very important feature: it is a value type. That means it is stored and passed entirely by value. Also, a new ref type modifier, which is a part of a type declaration signature, indicates that this type has an additional constraint: it can be allocated only on the stack. I mean passing its instances to class fields will produce an error. What is all this stuff for? To answer this question, you just need to look at the StringBuilder class, the essence of which we have just described:

StringBuilder class /src/mscorlib/src/System/Text/StringBuilder.cs

public sealed class StringBuilder : ISerializable
{
    // A StringBuilder is internally represented as a linked list of blocks each of which holds
    // a chunk of the string.  It turns out string as a whole can also be represented as just a chunk,
    // so that is what we do.
    internal char[] m_ChunkChars;                // The characters in this block
    internal StringBuilder m_ChunkPrevious;      // Link to the block logically before this block
    internal int m_ChunkLength;                  // The index in m_ChunkChars that represent the end of the block
    internal int m_ChunkOffset;                  // The logical offset (sum of all characters in previous blocks)
    internal int m_MaxCapacity = 0;

    // ...

    internal const int DefaultCapacity = 16;

StringBuilder is a class that contains a reference to an array of characters. Thus, when you create it, there appear two objects in fact: StringBuilder and an array of characters which is at least 16 characters in size. This is why it is essential to set the expected length of a string: it will be built by generating a single linked list of arrays with 16 characters each. Admit, that is a waste. In terms of ValueStringBuilder type, it means no default capacity, as it borrows external memory. Also, it is a value type, and it makes a user allocate a buffer for characters on the stack. Thus, the whole instance of a type is put on the stack together with its contents and the issue of optimization is solved. As there is no need to allocate memory on the heap, there are no problems with a decrease in performance when dealing with the heap. So, you might have a question: why don’t we always use ValueStringBuilder (or its custom analog as we cannot use the original because it is internal)? The answer is: it depends on a task. Will a resulting string have a definite size? Will it have a known maximum length? If you answer “yes” and if the string doesn’t exceed reasonable boundaries, you can use the value version of StringBuilder. However, if you expect lengthy strings, use the usual version.

ValueListBuilder

internal ref partial struct ValueListBuilder<T>
{
    private Span<T> _span;
    private T[] _arrayFromPool;
    private int _pos;

    public ValueListBuilder(Span<T> initialSpan)
    {
        _span = initialSpan;
        _arrayFromPool = null;
        _pos = 0;
    }

    public int Length { get; set; }

    public ref T this[int index] { get; }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Append(T item);

    public ReadOnlySpan<T> AsSpan();

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Dispose();

    private void Grow();
}

The second type of data that I especially want to note is the ValueListBuilder type. It is used when you need to create a collection of elements for a short time and pass it to an algorithm for processing.

Admit, this task looks pretty similar to the ValueStringBuilder task. And it is solved in a similar way:

File ValueListBuilder.cs coreclr/src/../Generic/ValueListBuilder.cs

To put it clearly, these situations are often. However, previously we solved the issue another way. We used to create a List, fill it with data and lose the reference to it. If the method is called frequently, this will lead to a sad situation: many List instances (and associated arrays) get suspended on the heap. Now this problem is solved: no additional objects will be created. However, as in case of ValueStringBuilder it is solved only for Microsoft programmers: this class has the internal modifier.

Rules and use practice

To fully understand the new type of data you need to play with it by writing two or three or better more methods that use it. However, it is possible to learn main rules right now:

If your method processes some input dataset without changing its size, you may try to stick to the Span type. If you are not going to modify buffer, choose the ReadOnlySpan type;
If your method handles strings calculating some statistics or parsing these strings, it must accept ReadOnlySpan<char>. Must is a new rule. Because when you accept a string, you make somebody create a substring for you;
If you need to create a short data array (no more than 10 kB) for a method, you can easily arrange that using Span<TType> buf = stackalloc TType[size]. Note that TType should be a value type as stackalloc works with value types only.

In other cases, you’d better look closer at Memory or use classic data types.

How does Span work?

I would like to say a few additional words on how Span functions and why it is that notable. And there is something to talk about. This type of data has two versions: one for .NET Core 2.0+ and the other for the rest.

File Span.Fast.cs, .NET Core 2.0 coreclr/.../System/Span.Fast.cs**

public readonly ref partial struct Span<T>
{
    /// A reference to a .NET object or a pure pointer
    internal readonly ByReference<T> _pointer;
    /// The length of the buffer based on the pointer
    private readonly int _length;
    // ...
}

File ??? [decompiled]

public ref readonly struct Span<T>
{
    private readonly System.Pinnable<T> _pinnable;
    private readonly IntPtr _byteOffset;
    private readonly int _length;
    // ...
}

The thing is that huge .NET Framework and .NET Core 1.* don’t have a garbage collector updated in a special way (unlike .NET Core 2.0+) and they have to use an additional pointer to the beginning of a buffer in use. That means, that internally Span handles managed .NET objects as though they are unmanaged. Just look into the second variant of the structure: it has three fields. The first one is a reference to a manged object. The second one is the offset in bytes from the beginning of this object, used to define the beginning of the data buffer (in strings this buffer contains char characters while in arrays it contains the data of an array). Finally, the third field contains the quantity of elements in the buffer laid in a row.

Let’s see how Span handles strings, for example:

File MemoryExtensions.Fast.cs
coreclr/../MemoryExtensions.Fast.cs

public static ReadOnlySpan<char> AsSpan(this string text)
{
    if (text == null)
        return default;

    return new ReadOnlySpan<char>(ref text.GetRawStringData(), text.Length);
}

Where string.GetRawStringData() looks the following way:

A file with the definition of fields coreclr/../System/String.CoreCLR.cs

A file with the definition of GetRawStringData coreclr/../System/String.cs

public sealed partial class String :
    IComparable, IEnumerable, IConvertible, IEnumerable<char>,
    IComparable<string>, IEquatable<string>, ICloneable
{

    //
    // These fields map directly onto the fields in an EE StringObject.  See object.h for the layout.
    //
    [NonSerialized] private int _stringLength;

    // For empty strings, this will be '\0' since
    // strings are both null-terminated and length prefixed
    [NonSerialized] private char _firstChar;

    internal ref char GetRawStringData() => ref _firstChar;
}

It turns out the method directly accesses the inside of the string, while the ref char specification allows GC to track an unmanaged reference to that inside of the string by moving it together with the string when GC is active.

The same thing is with arrays: when Span is created, some internal JIT code calculates the offset for the beginning of the data array and initializes Span with this offset. The way you can calculate the offset for strings and arrays was discussed in the chapter about the structure of objects in memory (.\ObjectsStructure.md).

Span<T> as a returned value

Despite all the harmony, Span has some logical but unexpected constraints on its return from a method. If we look at the following code:

unsafe void Main()
{
    var x = GetSpan();
}

public Span<byte> GetSpan()
{
    Span<byte> reff = new byte[100];
    return reff;
}

we can see it is logical and good. However, if we replace one instruction with another:

unsafe void Main()
{
    var x = GetSpan();
}

public Span<byte> GetSpan()
{
    Span<byte> reff = stackalloc byte[100];
    return reff;
}

a compiler will prohibit it. Before I say why, I would like you to guess which problems this construct brings.

Well, I hope you thought, guessed and maybe even understood the reason. If yes, my efforts to writing a detailed chapter about a [thread stack] (./ThreadStack.md) paid off. Because when you return a reference to local variables from a method that finishes its work, you can call another method, wait until it finishes its work too, and then read values of those local variables using x[0.99].

Fortunately, when we attempt to write such code a compiler slaps on our wrists by warning: CS8352 Cannot use local 'reff' in this context because it may expose referenced variables outside of their declaration scope. The compiler is right because if you bypass this error, there will be a chance, while in a plug-in, to steal the passwords of others or to elevate privileges for running our plug-in.

This chapter was translated from Russian jointly by author and by professional translators. You can help us with translation from Russian or English into any other language, primarily into Chinese or German.

Also, if you want thank us, the best way you can do that is to give us a star on github or to fork repository github/sidristij/dotnetbook.

Memory and Span pt.2