This series has focused on the common StringBuilder type and how it works internally to efficiently build strings. In my previous post I looked at the internal StringBuilderCache object that's used by .NET Framework and .NET Core to further reduce the allocations associated with building strings. In this post I look at another internal class that goes even further: ValueStringBuilder. Before we look at the type, I'll do a quick recap on the different types of memory allocation possible in .NET

Memory management: stack vs heap allocation

In .NET, memory can be allocated in one of two places: on the stack or on the heap. The exact rules of where objects are stored is somewhat complicated, but for the purposes of this article we can assume:

• Reference type instances (local variables/method arguments) are stored on the heap, but a pointer to the object is stored on the stack
• Value type instances (local variables/method arguments) are stored on the stack

In a typical .NET application, most of the objects you create will be reference types, and stored on the heap. Heap memory is garbage collected, so the more objects you create, the more pressure you put on the garbage collector. The good thing about allocating on the heap is that you don't have to worry too much about the size of your objects you're creating. Need to allocate 8MB to read an image into memory? No problem, there's plenty of space in the heap.

In contrast, stack memory is used to store the "control flow" of your application, so it contains pointers to each method currently being executed, as well as pointers to variables used by each of the methods. Each method call is called a "frame". When a method ends, the frame is discarded, so the memory used by the variables in a method is automatically discarded.

The automatic discarding of stack frames when a method ends, means that stack allocated memory has no impact on the garbage collector. When a method ends, any value-type objects allocated on the stack are automatically discarded, so there's nothing more to do. This is "optimal" from the point of view of reclaiming memory, but it has one significant downside: the stack is small.

The exact amount of stack memory available varies by system, but in all cases it's very small compared to the amount of RAM on a machine. For example 1MB is typical for Windows, with 8MB typical for Linux (though these are adjustable). If you allocate too much on the stack, you'll get a dreaded StackOverflowException. At this point, your application will crash, as there's no recovering. For that reason, you need to be very careful how much memory you allocate on the stack.

The more common example of a StackOverflowException is when using recursion to repeatedly execute a method. Each time you enter a method, you add another frame to the stack; add too many frames and you run out of stack memory.

A lot of effort goes on in the core .NET libraries to balance this trade-off. Modern .NET tries hard to reduce pressure on the garbage collector where possible by allocating on the stack. But you must always be aware that stack memory is limited, so you must only use stack allocation when it is reasonably safe.

The promise of ValueStringBuilder

As I've discussed previously in this series, strings are a common source of GC pressure in .NET applications, especially (historically) web applications. The "heap-based but immutable" nature of strings mean you typically create a lot of them, and they all need to be collected by the GC. This is especially true when creating strings from multiple other values and sources, for example formatting a DateTime into a string representation.

The introduction of Span<T> changed all that. Span<T> lets you take a "slice" of some memory (e.g. a string) in a way that doesn't generate a lot of garbage on the heap. Span<T> is a ref struct which means they are allocated on the stack (in a single stack frame). As already mentioned, that reduces the pressure on the garbage collector, and so can increase overall throughput in an app at scale.

So if Span<T> can reduce allocations, can we achieve similar benefits with other types?

Take StringBuilder for example. As you've already seen in this series, StringBuilder is designed to reduce the amount of allocation required to build a final string from separate strings and other objects, by using multiple buffers of chars, and writing intermediate values to the buffer. When you finally call ToString(), the buffers are assembled to create the final string.

Each StringBuilder chunk is a reference type that is allocated on the heap. Additionally, each StringBuilder has a char[] that is the chunk's "buffer", used to store the intermediate values. That's also allocated on the heap, and must be garbage collected. So while StringBuilder reduces the allocations compared to naïve string concatenation, it still has an allocation cost. ValueStringBuilder is intended to reduce that further.

Where can you find ValueStringBuilder, and how is it used?

Before we look at some of the implementation details, I thought it would be useful to see how ValueStringBuilder is used in practice. First off, ValueStringBuilder is not a public type, it's used internally in the .NET core libraries.

For example, UriBuilder uses a ValueStringBuilder to combine the various segments (e.g. Scheme, Host, Query etc) into a complete URI when you call ToString(). The following shows a (very stripped down) version of the original code, to highlight how ValueStringBuilder is used:

public override string ToString()
{
    var vsb = new ValueStringBuilder(stackalloc char[512]);

    if (Scheme.Length != 0)
    {
        vsb.Append(Scheme);
        vsb.Append(Uri.SchemeDelimiter);
    }

    if (Host.Length != 0)
    {
        vsb.Append(Host);
    }

    if (Path.Length != 0)
    {
        if (!Path.StartsWith('/') && Host.Length != 0)
        {
            vsb.Append('/');
        }

        vsb.Append(path);
    }

    vsb.Append(Query);

    vsb.Append(Fragment);

    return vsb.ToString();
}

At first glance, the usage of ValueStringBuilder looks very similar to StringBuilder, the big difference is in the creation:

var vsb = new ValueStringBuilder(stackalloc char[512]);

This line creates a new ValueStringBuilder, and passes in a stack allocated char[]. Stack allocation is what it sounds like - the memory is allocated on the stack, instead of on the heap. This is the buffer that ValueStringBuilder uses to "build" the string, and is one of the main ways it can reduce allocations overall. When the ToString() method exits, the stack allocated array is automatically discarded, so it doesn't create any garbage that needs collecting.

Notice, however, that you must specify the maximum size of the stack allocated buffer, and you can't make that too large, otherwise you might end up with a StackOverflowException.

Aside from that initial difference, usage is mostly the same. You can call Append passing in a string or char (as well as Span<char> and char*, not shown), and at the end of the build you call ToString() to build and allocate the final string.

But what happens if you add too many things to the ValueStringBuilder, and it grows beyond the original stackalloc buffer? To find out, we'll have to look under the hood a little at the implementation details, to see what's going on.

Under-the-hood of ValueStringBuilder

This post is already getting on a bit, so I'm not going to go into anything like as much depth on ValueStringBuilder as I have on StringBuilder. If you want to learn more, I suggest looking at the code directly.

Conceptually, ValueStringBuilder has a much simpler design than StringBuilder: there's no linked-list or "chunks" concept. ValueStringBuilder maintains a reference to a char[] buffer, and if we need more space, it uses a larger buffer from the heap and copies across the data. It's this mechanism that I look at primarily in this post.

This is the first "warning" associated with ValueStringBuilder. It works most efficiently when you have a small, well-defined, maximum size that the final string will be. Although you can exceed the initial buffer size, you will take a performance hit.

We start with the ValueStringBuilder definition and constructors:

internal ref struct ValueStringBuilder
{
    private char[]? _arrayToReturnToPool;
    private Span<char> _chars;
    private int _pos;

    public ValueStringBuilder(Span<char> initialBuffer)
    {
        _arrayToReturnToPool = null;
        _chars = initialBuffer;
        _pos = 0;
    }

    public ValueStringBuilder(int initialCapacity)
    {
        _arrayToReturnToPool = ArrayPool<char>.Shared.Rent(initialCapacity);
        _chars = _arrayToReturnToPool;
        _pos = 0;
    }
}

The first constructor shown is the one used by UriBuilder (shown previously), which allows you to pass in a stackalloc char[], which is automatically cast to a Span<char> in the constructor. However there is a second constructor, in which you specify the capacity required. When you use this constructor, you automatically rent a char[] from the ArrayPool, and assign it to _arrayToReturnToPool for disposal later.

ArrayPool can be used to reduce the overall allocations in your application where arrays are frequently created and destroyed. Renting a buffer supplies the caller with a char[] from the heap, but you must be sure to Return it later to avoid memory leaks.

In both constructors, _chars is the Span<char> that we will work with primarily, and _pos is how many letters have been added to the builder (0 initially).

Most of the Append methods work as you'd expect. For example, the following Append method is for adding a ReadOnlySpan<char>:

public void Append(ReadOnlySpan<char> value)
{
    int pos = _pos;
    if (pos > _chars.Length - value.Length)
    {
        Grow(value.Length);
    }

    value.CopyTo(_chars.Slice(_pos));
    _pos += value.Length;
}

This method first checks if the existing _chars buffer can accommodate the length of value. If it can, there's nothing to do; the Span<char> are copied to the _chars buffer, and the value of _pos is incremented. If there isn't enough space, then we need the Grow() method.

private void Grow(int additionalCapacityBeyondPos)
{
    // Make sure to let Rent throw an exception if the caller has a bug and the desired capacity is negative
    char[] poolArray = ArrayPool<char>.Shared.Rent((int)Math.Max((uint)(_pos + additionalCapacityBeyondPos), (uint)_chars.Length * 2));

    _chars.Slice(0, _pos).CopyTo(poolArray);

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

Grow increases the size of the Span<char> buffer by renting a char[] from the ArrayPool, which use a char[] from the heap. As I mentioned earlier, and unlike the stackalloc char[] passed to the constructor, this may allocate. However, using the shared ArrayPool means that generally this doesn't create garbage that must be cleaned up. The ArrayPool maintains a section of memory that is "shielded" from garbage collection, and hands out small amounts as required. The important thing, as we'll see shortly, is that this memory is returned when you're done with it.

So, back to the Grow() method. First we rent a buffer array that is either twice the size of our current _chars buffer, or big enough to fit the extra capacity we need (whichever is larger). We then copy the existing _char buffer into the new poolArray. Finally, if the _chars buffer was previously rented from the ArrayPool, we return that buffer. This step is very important to avoid memory leaks.

That's pretty much all there is to the ValueStringBuilder. Most of the append methods are similar to the previous one, and call Grow() if the buffer is not big enough. The final step is to call ToString():

 public override string ToString()
{
    string s = _chars.Slice(0, _pos).ToString();
    Dispose();
    return s;
}

Converting the Span<char> to a string is simple, but you might be surprised to see the Dispose in there:

public void Dispose()
{
    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);
    }
}

ValueStringBuilder doesn't implement IDisposable, but it's important that Dispose() is called on it when you're finished with it, so that a rented buffer from ArrayPool is returned to avoid memory leaks. ToString() automatically calls Dispose() for you, as does TryCopyTo(Span<char>), but if you don't call either of these methods, then you must call Dispose() once you're finished with the builder.

I'm going to leave it there with the code of ValueStringBuilder, but there are a couple of more interesting aspects if you feel the desire to look at the code. Of particular note is AppendSpan() which returns a Span<char> that you can (for example) use for zero-allocation formatting of primitives. Also of interest is AsSpan(bool terminate) which optionally appends a null character \0 to the returned span.

So, can I actually use ValueStringBuilder?

On the face of it, a low-allocation StringBuilder seems like a really useful type to be in the .NET BCL, and there's a corresponding proposal for some sort of ValueStringBuilder here. However, it's been 3 years since that proposal was created, and there's no public ValueStringBuilder yet, so why not?

Part of the problem is that the proposal (and the ValueStringBuilder used internally) is easy to use incorrectly. ValueStringBuilder is a ref struct, which means if you pass it as an argument to a method, a copy of the struct is made, which is passed to the method.

The problem with that may not be apparent, but you now have two copies of the struct, both of which have a reference to an ArrayPool buffer. If you then call Dispose or ToString() on both copies, then you have a potential security bug caused by "freeing" the same block of memory twice.

The correct way to pass a ValueStringBuilder to a method is by reference (as in this example, shown below). This ensures no copy is made:

public static string UserName
{
    get
    {
        var builder = new ValueStringBuilder(stackalloc char[40]);
        GetUserName(ref builder); // pass by reference

        builder.Dispose();
        return result;
    }
}

// pass by referemce
private static void GetUserName(ref ValueStringBuilder builder)
{
    // use builder
}

Unfortunately, there's currently no way in C# to enforce that a ref struct is only ever passed by reference. There's a proposal to add an analyzer to detect this situation, but until we have something like that, ValueStringBuilder won't make an appearance as it's too easy to misuse.

On top of that, depending on how you're using ValueStringBuilder, you may not actually find it provides you much benefit. Hot paths where you're formatting small, well defined strings are a good candidate, but outside of that you may find the complexity (or the potential risk of StackOverflowExceptions or double-free bugs when used incorrectly) are not worth the risk.

In many cases, if you know the final size of the string you're creating, you may find that string.Create(), which also allows zero-allocation string creation, is a better option (see Steve Gordon's excellent post for details).

Summary

In this post I discussed the difference between stack and heap allocation, and why stack allocation can be useful. I then described the idea behind the internal ValueStringBuilder type, a ref struct that can use a stack allocated char[] to build a string in a zero (or low) allocation way. I described how the Grow() method works, by using a shared buffer from ArrayPool, as well as the implications for this, namely that the buffer must be returned when you're finished with the builder. When used correctly, ValueStringBuilder can work in a completely zero allocation way, but you must be careful not to inadvertently create copies by passing the builder by reference, otherwise you can expose yourself to a bug where you double-return buffers to the ArrayPool.

That's the last post in this series on StringBuilder - I hope you've enjoyed it, and be sure to check out Steve Gordon's series that he (coincidentally) started at the same time as me!