--- title: "Create a low allocation and faster StringBuilder - Span in Action" description: ".NET ships a nice `StringBuilder` since the dawn of time or at least since the beginning of the framework itself. The intention is simple: If we need to concatenate a lot of strings we can't rely on the `+ operator` as we introduce a lot of unnecessary allocations plus it is slow!\nThat is where the `StringBuilder` jumps into the picture.\n\nWhy is that? Why is the `StringBuilder` better? And can we do better? Spoiler: **Yes!**" updated: 2022-04-03 tags: ["Span", "Performance", "String", "C#"] canonical: "https://steven-giesel.com/blogPost/4cada9a7-c462-4133-ad7f-e8b671987896/create-a-low-allocation-and-faster-stringbuilder-span-in-action" --- # Create a low allocation and faster StringBuilder - Span in Action The .NET framework is a general-purpose framework. It offers classes and structs for everyday use. One of those examples is the [`StringBuilder`](https://docs.microsoft.com/en-us/dotnet/api/system.text.stringbuilder?view=net-6.0). The idea behind is simple: Every time we need to concatenate a lot of strings, we can leverage the `StringBuilder`, which is faster than concatenating every string with each other. But we can do better. We can create a `StringBuilder` which can perform faster for smaller strings **and** does use fewer allocations! We will do so with the help of `Span` a type introduced with .NET Core 2.1. First let's answer: **Why** concatenating strings is slow and takes a lot of allocations. The sole reason is **immutability**. `string`s are **immutable**. That means if you want to change a string or append another string to our string you have to create a new one. This is a conscious design decision of the C# team. Other languages like **Swift** or **C/C++** have mutable strings! **Java** has immutable strings as well! Immutable strings or constraints in general have the advantage that you reduce the usage and can better predict what is going on. For strings we have [*string interning*](https://blog.jetbrains.com/dotnet/2015/02/12/string-interning-effective-memory-management-with-dotmemory/). Basically if two strings have the same value, generally they share the same memory address. ```csharp var text1 = "Hello"; var text2 = "Hello"; var sameAddress = text1.ReferenceEquals(text2); // is true ``` This is where we are coming from. Now quick excurse to the `StringBuilder`. The `StringBuilder` doesn't use `string`s internal. It uses an array and resizes it if we need more space. But exactly that resizing will allocate new memory. And here is where want to tackle the problem! We want to have a low allocation `StringBuilder` which should at least perform the same and all in `safe` context. And we can do so. We will do this with the help of `Span`. ## Span<T> to the rescue [`Span`](https://docs.microsoft.com/en-us/dotnet/api/system.span-1?view=net-6.0) was introduced in .net core 2.1 and the idea is very very simple: ![Span](https://linkdotnetblog.azureedge.net/blog/20220403_SpanStringBuilder/Span.png) `Span` represents a slice of contiguous memory. You can oversimplified think of `Span` as the following: ```csharp public readonly ref struct Span { private readonly ref T _pointer; private readonly int _length; ... } ``` There are a few key things we have to tackle to understand why this is helping us: 1. `Span` is a `readonly ref struct` that means it lives on the `Stack`, **always**. [Here](https://steven-giesel.com/blogPost/9a40d278-9a9f-49fe-bbfd-2d813a58e73e) my blog post about `Stack` and `Heap`. I would advise you to read that part if you need a refresher on that topic. As it always lives on the `Stack` we can't use it everywhere where we please. Basically, every time when we would have to put a **value type** on the `Heap` it will not work out! A simple example would be you can't have a `ref struct` as a field on your `class` as this would mean the `struct` has to have a reference on the heap. The compiler enforces that constraint, but we gain also performance benefits from that! As always a trade-off. 2. The `Span` object holds a pointer to our object plus its length. With that, we can model a memory slice where we can iterate over. 3. Also that means that our `ref T` is on the `Stack`. We see that is a very specialized `struct` meant for performance! If you want to know more about `Span`[ here is a link](https://docs.microsoft.com/en-us/archive/msdn-magazine/2018/january/csharp-all-about-span-exploring-a-new-net-mainstay#how-is-spant-implemented) to the official Microsoft documentation. ## `ValueStringBuilder` Now with this information, we want to build a `StringBuilder` that uses way fewer allocations and should at least perform the same or better and certain scenarios. Another requirement: **No unsafe code!**. I don't want to handle pointers myself, otherwise, I would have written that thing directly in C/C++. I know that there are implementations with `unsafe` out in the wild, but we can do better!better is very subjective here, but I hope you know what I mean ;) You can find the source code in the **Resources** section down below if you want to directly jump into the code. We will use the same principles as the `StringBuilder` which ships with .NET itself. But we will adopt it: 1. We will use an internal array for holding the characters which get appended 2. If the current internal buffer is too small we will double the size and copy the old content into the new buffer 3. `ToString()` will give us the whole string 4. We will offer an indexer which gives us the character at an arbitrary position ```csharp public ref struct ValueStringBuilder { private int _bufferPosition; private Span _buffer; private char[]? arrayFromPool; public ValueStringBuilder() { _bufferPosition = 0; _buffer = new char[32]; arrayFromPool = null; } public ref char this[int index] => ref _buffer[index]; ``` That is our general outline! **Huh?** we have a the `Span` as field eventhough I talked about that is not working. Well it is not working for a `class` but if your holding scope is a `ref struct` itself then it is fine. Of course this comes with trade-offs in usage I'll show you later. We basically have a small state consisting out of our internal buffer `_buffer` and the current position in our buffer `_bufferPosition`. This is important because our buffer is statically sized and might be bigger than the string it really represents. The **indexer** is also very easy to model: Just give back the `char` at the specific position. Done! The next easy thing is the `ToString()` method: ```csharp public override string ToString() => new(_buffer[.._bufferPosition]); ``` We are slicing our `_buffer` from the beginning until `_bufferPosition`. That is it. Now we only have to fill the internal buffer :D. Also here we can start with the easy one, appending a single char: ```csharp public void Append(char c) { if (_bufferPosition == _buffer.Length - 1) { Grow(); } _buffer[_bufferPosition++] = c; } ``` We have a basic check if our buffer still has enough space for another character, if not we have to `Grow` our array. How this happens we will show later. If the element (then) fits in we just set the new character at the end of the `_bufferPosition`. Before we come to the point of how `Grow` works, let's have a look at appending a whole string: ```csharp public void Append(ReadOnlySpan str) { var newSize = str.Length + _bufferPosition; if (newSize > _buffer.Length) Grow(newSize * 2); str.CopyTo(_buffer[_bufferPosition..]); _bufferPosition += str.Length; } public void AppendLine(ReadOnlySpan str) { Append(str); Append(Environment.NewLine); } ``` Now first: `ReadOnlySpan` has an implicit cast from `string` so the caller can just pass in "normal" strings. But `Span`s are faster to operate on. The difference between `Span` and `ReadOnlySpan` is, as the name suggests, does not allow mutating the memory slice represented by `ReadOnlySpan`. We could also use the `in` keyword, but I did not find any performance gains but sometimes it was even slower. Now the magic, besides `Grow()` here is this: ```csharp str.CopyTo(_buffer[_bufferPosition..]); // Copy the str into _buffer beginning from _bufferPosition _bufferPosition += str.Length; // Our internal buffer is now str.Length longer ``` Now the final bit: `Grow()` ```csharp private void Grow(int capacity = 0) { var currentSize = _buffer.Length; var newSize = capacity > 0 ? capacity : currentSize * 2; // This should be returned at some point (like a Dispose method) // This part will not be shown in the code. See resources for a real-world implementation var rented = ArrayPool.Shared.Rent(newSize); _buffer.CopyTo(rented); _buffer = arrayFromPool = rented; if (oldBuffer is not null) { ArrayPool.Shared.Return(oldBuffer); } } ``` If we don't specific the capacity we just double the current internal buffer size. I am currently playing around which growth-size would be good. We have to find a nice balance between not reserving too much space but also not resizing our array too often. For now `*2` is good enough. The next part is a bit tricky. We will use a shared [`ArrayPool`](https://docs.microsoft.com/en-us/dotnet/api/system.buffers.arraypool-1.shared?view=net-6.0). I will not go too much into detail. [Here](https://adamsitnik.com/Array-Pool/) is a very nice blog post that explains it better than I could do ;). The basic idea is that we pool the buffer. So we share that buffer with others if we don't need it anymore. Like car-pooling! The benefit is that we don't have to allocate new objects all the time, which a) costs time and b) allocates stuff that we don't want! So we take that array from the pool with the new size, copy and assign our old content into it and return the rented array. Especially for bigger arrays. I might build a library out of that which looks a bit more in detail about how to fine-tune that. Anyway, we are good for now! That's it. The usage is pretty trivial: ```csharp var stringBuilder = new StringBuilder(); stringBuilder.AppendLine("Hello"); stringBuilder.AppendLine("World"); Console.Write(stringBuilder.ToString(); ``` prints: ```no-class Hello World ``` Two constraints we have in contrast to the "normal" `StringBuilder`: 1. We can't use it as a field on a class! That might be a no-go in your use case. 2. We don't have the fluent notation as the `StringBuilder` has. With the .net version you can do that: `new StringBuilder().AppendLine("").AppendLine("").ToString();` that does not work with our version. The reason is that we have a `struct`. Sure we can make it fluent, but that means we have a lot of allocation going on and potential bugs depending on which version you take. Therefore I decided not to do that. ## Performance and allocations The following setup: ```csharp [MemoryDiagnoser] public class Benchi { [Benchmark(Baseline = true)] public string DotNet() { var reference = new StringBuilder(); return reference .AppendLine("Hello World") .AppendLine("Here some other text") .AppendLine("And again some other text as well for good measure") .AppendLine("You are still here?") .AppendLine("Hmmm.") .AppendLine("I wish you a very nice day and all the best.") .AppendLine("Sincerly Steven") .ToString(); } [Benchmark] public string Fast() { var fast = new ValueStringBuilder(); fast.AppendLine("Hello World"); fast.AppendLine("Here some other text"); fast.AppendLine("And again some other text as well for good measure"); fast.AppendLine("You are still here?"); fast.AppendLine("Hmmm."); fast.AppendLine("I wish you a very nice day and all the best."); fast.AppendLine("Sincerly Steven"); return fast.ToString(); } } ``` Now finally, how well did our new cool implementation? ```no-class BenchmarkDotNet=v0.13.1, OS=Windows 10.0.19043.1586 (21H1/May2021Update) Intel Core i7-7820HQ CPU 2.90GHz (Kaby Lake), 1 CPU, 8 logical and 4 physical cores .NET SDK=6.0.201 [Host] : .NET 6.0.3 (6.0.322.12309), X64 RyuJIT DefaultJob : .NET 6.0.3 (6.0.322.12309), X64 RyuJIT | Method | Mean | Error | StdDev | Ratio | RatioSD | Gen 0 | Allocated | |------- |---------:|--------:|---------:|------:|--------:|-------:|----------:| | DotNet | 474.1 ns | 9.49 ns | 25.67 ns | 1.00 | 0.00 | 0.3076 | 1,288 B | | Fast | 265.3 ns | 8.30 ns | 23.80 ns | 0.56 | 0.06 | 0.1090 | 456 B | ``` **Wow** almost 50% faster by only 33% of the allocations! That is massive! Now we can see why the .NET team is using those types more often inside the framework itself to boost the performance. ## Conclusion That was very nice. We used some nice advanced C# features to build our own `StringBuilder`. This version is very simplistic and could need a lot of polishing. So: **Let me know if I should make a library out of it on nuget.** That means further optimization and a bit more convenient functions added, plus, of course, tests! Hit me with a message here, give a like or hit me up on LinkedIn for that. ## Resources * The code for this blog post on [GitHub](https://github.com/linkdotnet/BlogExamples/tree/main/ValueStringBuilder) * All my examples for this blog found [here](https://github.com/linkdotnet/BlogExamples) * Full fledge `ValueStringBuilder` can be found [here](https://github.com/linkdotnet/StringBuilder).