Friday Links 0.0.22 - StringBuilder Updates

This is based on an email I send my .NET team at work

Happy Friday,

Let’s take a deep dive into one of the most beloved portions of the .NET base class library: the venerable StringBuilder.

StringBuilder: the Past and the Future

http://codingsight.com/stringbuilder-the-past-and-the-future/

Timur Guev has a neat article looking into the internals of System.Text.StringBuilder.

When .NET was first released, the implementation was mostly the same as List: whenever it ran out of space, it would double its capacity, copy the existing text, and start working on the new, bigger buffer.

In .NET 4, they changed the internals to instead be a Linked List of buffers. This is sometimes called a Rope. As you Append() text to the builder, eventually its current buffer runs out of space, so a new one is allocated, and a pointer is kept in the internal book-keeping. In this algorithm, there is no need for copying strings around during the Append operation. However, when it becomes time to create a real string object, StringBuilder has to allocate a big enough block of memory, then walk the linked list copying each buffer to the output.

They did this because the most common use-case for StringBuilder is some kind of tight loop that calls Append() a bunch of times, before finally grabbing the resulting string with ToString(). The new algorithm is much better designed for this scenario. There is a lot less copying of character bytes, and no extra allocations of arrays for strings. This reduces CPU time and garbage collection pressure.

However, other methods of StringBuilder suffer: Insert(), Remove() etc incur extra bookkeeping and copying operations compared to the previous implementation that just kept the entire data in an array. Also, the final ToString() call is slower, because it has to allocate a new string for the result and copy the data into it. Prior to .NET 4, the StringBuilder could just return a pointer to its internal buffer.

This is a really good example of encapsulation. The external interface of StringBuilder did not change at all in .NET 4, though its internals were completely reworked to target a different performance profile.

It’s also a good example of the tradeoffs involved in performance work. The framework designers decided it was better overall to improve the most common use case, even if some other scenarios would suffer.

Check out the link for a deeper look and some performance timings the author did to demonstrate the tradeoffs.

Comments