StringBuilder is not always faster – Part 2 of 2

In a previous article (“StringBuilder is not always faster), I provided some quick benchmark data and gave “rules of thumb” for when to use StringBuilder and when to use traditional string concatenations. In this follow-up article, I will attempt to provide a more detailed analysis.

If you don’t want to bother with the details, jump directly to the conclusions here.

A Look at the Generated MSIL

A reader, Matt, suggested that it’s possible the compiler may have noticed that I never use the generated test objects in my benchmark code and not created them. That would definitely invalidated my test results!

Here’s the original benchmark code:

for (int i = 0; i <= 1000000; i++)
{
    // Concat strings 3 times using StringBuilder
    StringBuilder s = new StringBuilder();
    s.Append(i.ToString());
    s.Append(i.ToString());
    s.Append(i.ToString());
}

And this one, using traditional concatenation, took slightly less time (1344 milliseconds):

for (int i = 0; i <= 1000000; i++)
{
    // Concat strings 3 times using traditional concatenation
    string s = i.ToString();
    s = s + i.ToString();
    s = s + i.ToString();
}

According to Lutz Roeder’s .NET Reflector (great tool), the answer is no. Here’s the IL from Reflector:

.entrypoint
.maxstack 2
.locals init (
    [0] int32 i,
    [1] class [mscorlib]System.Text.StringBuilder s,
    [2] string V_2,
    [3] bool CS$4$0000)
L_0000: nop
L_0001: ldc.i4.0
L_0002: stloc.0
L_0003: br.s L_003b
L_0005: nop
L_0006: newobj instance void [mscorlib]System.Text.StringBuilder::.ctor()
L_000b: stloc.1
L_000c: ldloc.1
L_000d: ldloca.s i
L_000f: call instance string [mscorlib]System.Int32::ToString()
L_0014: callvirt instance class [mscorlib]System.Text.StringBuilder [mscorlib]System.Text.StringBuilder::Append(string)
L_0019: pop
L_001a: ldloc.1
L_001b: ldloca.s i
L_001d: call instance string [mscorlib]System.Int32::ToString()
L_0022: callvirt instance class [mscorlib]System.Text.StringBuilder [mscorlib]System.Text.StringBuilder::Append(string)
L_0027: pop
L_0028: ldloc.1
L_0029: ldloca.s i
L_002b: call instance string [mscorlib]System.Int32::ToString()
L_0030: callvirt instance class [mscorlib]System.Text.StringBuilder [mscorlib]System.Text.StringBuilder::Append(string)
L_0035: pop
L_0036: nop
L_0037: ldloc.0
L_0038: ldc.i4.1
L_0039: add
L_003a: stloc.0
L_003b: ldloc.0
L_003c: ldc.i4 0xf4240
L_0041: cgt
L_0043: ldc.i4.0
L_0044: ceq
L_0046: stloc.3
L_0047: ldloc.3
L_0048: brtrue.s L_0005
L_004a: ldc.i4.0
L_004b: stloc.0
L_004c: br.s L_0078
L_004e: nop
L_004f: ldloca.s i
L_0051: call instance string [mscorlib]System.Int32::ToString()
L_0056: stloc.2
L_0057: ldloc.2
L_0058: ldloca.s i
L_005a: call instance string [mscorlib]System.Int32::ToString()
L_005f: call string [mscorlib]System.String::Concat(string, string)
L_0064: stloc.2
L_0065: ldloc.2
L_0066: ldloca.s i
L_0068: call instance string [mscorlib]System.Int32::ToString()
L_006d: call string [mscorlib]System.String::Concat(string, string)
L_0072: stloc.2
L_0073: nop
L_0074: ldloc.0
L_0075: ldc.i4.1
L_0076: add
L_0077: stloc.0
L_0078: ldloc.0
L_0079: ldc.i4 0xf4240
L_007e: cgt
L_0080: ldc.i4.0
L_0081: ceq
L_0083: stloc.3
L_0084: ldloc.3
L_0085: brtrue.s L_004e
L_0087: ret

Size of Concatenated Values and StringBuilder with Initial Capacity

More questions from Matt: how does the performance curve change if the concatenated values are larger? And what if you seed the StringBuilder object with an initial capacity?

To answer the questions, I wrote some more benchmarks (complete source code at the bottom of this article) to compare three different methods of concatenation:

• “+” concatenation: This is the traditional a + b + c method.
• StringBuilder: Create a StringBuilder object using the default constructor and calling Append().
• StringBuilder/Pre-allocated: Create a StringBuilder object and preallocate the initial capacity so that it does not need to expand later.

String Size = 10

The chart below shows elapsed times (ms) of the three concatenation methods, with the concatenated string size equaled to 10 characters

As the chart illustrates, when the size of the concatenated value is small (10 characters in this test), “+” concatenation (blue line) performs faster than StringBuilder until the number of concatenations reaches 6. After 6, StringBuilder starts to work exponentially faster.

However, when compared with the StringBuilder/Pre-allocated method, StringBuilder starts to perform as fast as “+” concatenation much earlier: at 3 concatenations.

Note: The orange line for StringBuilder is not very linear. My guess is that it’s due to the need to allocate space as needed. The memory allocation itself will consume CPU cycles. The default StringBuilder constructor will allowcate 16 bytes initially. Thereafter, it will allocate two times the current capacity whenever needed.

String Size = 100

When the concatenated value is 100 characters, the all three methods perform very similarly up to three concatenations, then StringBuilder/Pre-allocated pulls ahead at 4 concatenations.

Concatenated String Size = 1000

At 1000 characters, things begine a little bit more interesting: StringBuilder/Pre-allocated is faster in all cases (although the difference is very small until about 6 concatenations). Since it may not be always possible or practical to know the final string size ahead of time, for this graph, I also added two more series to show what happens if you over-estimate or under-estimate the final capacity. As expected, there is a performance penalty for both. The more inaccurate your estimated capacity is, the higher of a performance penalty you will get.

What about String.Concat?

Lars Wilhelmsen asked “What about string.Concat?” According to my research, string.Concat is basically identical to “+” used on a single line.

This:

string s = "a" + 
                    class="str">"b" + "c";

Is the same (same generated IL) as this:

string s = string.Concat(
 class="str">"a", "b", "c");

But not this:

string s = "a";
s = s + "b";
s = s + "c";

Remember, the “+” must be on the same logical line, otherwise, the compiler will convert each line into a separate string.Concat operation, resulting in slower performance.

AJ has written a post detailing string.Concat here. Thanks, AJ, for pointing it out.

And String.Format?

Flyswat wanted to know about string.Format. I did some quick benchmark code again. The string.Format code below took 58 milliseconds to run 100,000 iterations:

string s = string.Format(
          class="str">"Value: {0}", strVal);

While this code, using “+” concatenation, only took 9 milliseconds (also 100,000 iterations):

string s = "Value: " + strVal;

According to the above numbers, string.Format is significantly slower than “+” concatenations. The difference in speed is similar between s.AppendFormat(“Value: {0}”, strVal) and s.Append(“Value: ” + strVal). I have used String.Format a lot in my code and I have not thought about this performance penalty. It does make sense. String.Format (or StringBuilder.AppendFormat) has to scan the string looking for format specifiers… that takes time. String.Format is very useful to make the code easier to read or when you actually need to format numbers. Even with this new data, I will not neccessarily shy away from using string.Format. I will however definitely be much more observant when using it, especially when used inside a loop or performance critical code path.

Conclusions

The new benchmarks do point to StringBuilder/Pre-allocated as the fastest method regardless of number of concatenations, when the concatenated string value is large (1000 characters).

With that in mind, here are my slightly modified rules of thumbs for string concatenation. Remember, “rules of thumb” are short statements to provide general princicles, and may not be accurate for every single situation. For performance criticial code, you should consider running some benchmarks/profiling yourself.

• For 1-4 dynamic concatenations, use traditional “+” concatenation.
• For 5 or more dynamic concatenations, use StringBuilder.
• When using StringBuilder, try to provide the starting capacity as close to the final string size as possible.
• When building a big string from several string literals, use either the @ string literal or the + operator.
• For performance critical code, consider running your own benchmarks

Additional Reading

• MSIL Tutorial

Notes

The benchmarks in this article were run on a Pentium 4 2.4 GHz CPU, with 2GB of RAM. With .NET framework: 2.0.

Source Code for Benchmarks

Source code here.