StringBuilder Required Capacity Algorithm

.NET Strings are immutable.  StringBuilder should be used to better performance.  Blah… Blah… Blah…  You’ve heard it all before, but what you might not know is how StringBuilder dynamically allocates its capacity.  The simple answer is StringBuilder will double its capacity when its capacity is reached.  In other words, if you add 1 byte to a StringBuilder with 32 bytes of storage, the allocation will double to 64.  You might be wondering what happens if doubling isn’t enough?  Will storage just keep doubling until the required capacity is met?  Nope.  In this case, StringBuilder will only allocate exactly what is needed.  The algorithm is arguably dumb — double the allocation and, if that’s not enough, add as much as needed.  So, if you add 64 bytes to a StringBuilder with 16 bytes of storage, the allocation will double to 32 and then jump to 80 (16+64) bytes.  In other words, and this is the arguable dumb part, if you add even one more byte, reallocation is required with the next Append(). I personally think the algorithm should continue to double the storage until the required capacity is met or exceeded rather than merely meet the need.

Here’s the code (compliments of Reflector)…

private string GetNewString(string currentString, int requiredLength)
{
    int maxCapacity = this.m_MaxCapacity;
    if (requiredLength < 0)
    {
        throw new OutOfMemoryException();
    }
    if (requiredLength > maxCapacity)
    {
        throw new ArgumentOutOfRangeException("requiredLength",
            Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity"));
    }
    int capacity = currentString.Capacity * 2;
    if (capacity < requiredLength)
    {
        capacity = requiredLength;
    }
    if (capacity > maxCapacity)
    {
        capacity = maxCapacity;
    }
    if (capacity <= 0)
    {
        throw new ArgumentOutOfRangeException("newCapacity",
            Environment.GetResourceString("ArgumentOutOfRange_NegativeCapacity"));
    }
    return string.GetStringForStringBuilder(currentString, capacity);
}

You can read more here and here.