How does the StringBuilder decide how large its capacity should be?

Question

I know that the StringBuilder object allocates more memory when you use sb.Append(..) when the sb is already at capacity. But how much does that capacity increase?

    StringBuilder sb = new StringBuilder(5);
    sb.Append("0123456789");

Now what is the capacity of sb and why? What is the multiplier?

Just for clarity. I am asking about capacity and not length.

Thanks!

Answer 1

The capacity doubles each time apart from some special cases:

• If doubling is not enough then the capacity is further increased to the exact amount that is required.
• There is an upper limit - 0x7fffffff.

You can see the algorithm by using .NET Reflector or downloading the reference source.

I can't post the source code for the official .NET implementation but here's the code for the Mono implementation:

// Try double buffer, if that doesn't work, set the length as capacity
if (size > capacity) {

    // The first time a string is appended, we just set _cached_str
    // and _str to it. This allows us to do some optimizations.
    // Below, we take this into account.
    if ((object) _cached_str == (object) _str && capacity < constDefaultCapacity)
        capacity = constDefaultCapacity;

    capacity = capacity << 1;  // This means "capacity *= 2;"

    if (size > capacity)
        capacity = size;

    if (capacity >= Int32.MaxValue || capacity < 0)
        capacity = Int32.MaxValue;

    if (capacity > _maxCapacity && size <= _maxCapacity)
        capacity = _maxCapacity;
}

I would also recommend that you don't write code that relies on this specific algorithm as it is an implementation detail, and not something that is guaranteed by the interface.

Answer 2

It's exponential growth (specifically, doubling with each reallocation), in order to allow a series of appends to take O(N) time instead of O(N²) time.