Chinh Do

StringBuilder is not always faster – Part 2 of 2

29th September 2007

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

StringBuilder Benchmark - Elapsed time vs Concatenations - String Size 10

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

StringBuilder Benchmark - Elapsed time vs Concatenations - 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

StringBuilder Benchmark - Elapsed time vs Concatenations - 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

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.

kick it on DotNetKicks.com

This entry was posted on Saturday, September 29th, 2007 at 2:19 am and is filed under Dotnet/.NET - C#, Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

There are currently 9 responses to “StringBuilder is not always faster – Part 2 of 2”

  1. 1 On September 29th, 2007, StringBuilder is not always faster » Chinh Do said:

    [...] have posted a follow-up article to provide more detailed analysis and to answer some of the questions asked by [...]

  2. 2 On September 29th, 2007, 1kHz | anti-keseronokan » Blog Archive » String Concatenation dan Performance said:

    [...] Hari ini, aku terbaca beberapa artikel tentang string concatenation lagi: StringBuilder is not always faster StringBuilder is not always faster – Part 2 [...]

  3. 3 On November 1st, 2007, Armen Ayvazyan said:

    Well,
    StringBuilder with specified capacity is always faster. You measured only first phase of concatenation – memory allocation. Due to fact that strings are immutable each time we are using “+” operator or String.Concat() the new String object will be allocated in memory which in your case you will have 100000 String objects in memory where 99999 are not used at all.

    So as you can guess we are creating additional work for a Garbage Collector and using more memory than it actually could be used.

    In case of StringBuilder with specified capacity there will be only 1 object created in memory and *NO* additional work for Garbage Collector.

    “+” operator takes more CPU time, Memory size and creates extra time for a Garbage Collector to clear the mess it built. Unlike StringBuilder with specified parameter saves memory space and CPU time as object will be allocated only ones and GarbageCollector won’t have anything to clean up after.

    My Conclusion is: Use StringBuilder with specified capacity almost always.

    http://blog.dotnetstyling.com/archive/2007/10/27/How-fast-SringBuilder-is.aspx

  4. 4 On November 1st, 2007, Chinh Do said:

    Armen:

    I’ll have to disagree. The tests I did in this article precisely showed that under some circumstances, + concatenation is faster than StringBuilder, even when pre-allocated with the final capacity. Look at the first test where the concatenated string size is 10. + concatenations is faster up to 3 concatenations.

    I understand that the more memory you allocate, the more work you create for the garbage collector. However, the work that is done by the garbage collector is also taken into account in my tests, as I simply measured the total elapsed time. Whatever work that is done by the GC is reflected in that total elapsed time.

    Re the “for” loop, its purpose is to purely multiply the concatenation multiple times to get a more accurate measurement. It’s a typical practice in micro-benchmarks. The operation being measured is inside the loop.

  5. 5 On November 1st, 2007, Armen Ayvazyan said:

    Chinh:

    Tests you did are really good and very detail. They proof that nothing is so obvious and simple. It is nice to see that there is another person in this world who thinks about same kind of crazy things :)

    I would like to leave for developers the choice they will make whether to use different techniques based on number of concatenations + length of strings or just to use StringBuilder(capacity) everywhere.

  6. 6 On November 11th, 2008, CoDr said:

    Hi Chinh,
    What you’re testing isn’t showing apples to apples.

    In code, you don’t instantiate a million new StringBuilders. StringBuilders are a little expensive up front and the fact that you’re instantiating it inside the loop is where the time is lost.

    Instantiation is expensive. That’s why the stringbuilder is so much better than traditional “+” concatenation that spans multiple calls.

    In a coding project, you only create the StringBuilder once then you can use it to continually, efficiently concatenate your variable string, as needed. Please try pulling that line (“StringBuilder sb = new StringBuilder();”) out and check out the results… something like this:

    protected void Page_Load(object sender, EventArgs e)
    {
    int iLoopTo = 30000;

    DateTime dt = DateTime.Now;
    string string1 = “”;
    for(int i = 0;i <= iLoopTo;i++)
    {
    string1 = string.Concat(string1, i.ToString());
    }
    TimeSpan loopTS = DateTime.Now.Subtract(dt);
    lblTimestamps.Text += loopTS.TotalMilliseconds + ” milliseconds for string.Concat”;

    dt = DateTime.Now;
    StringBuilder sb = new StringBuilder();
    for(int i = 0;i <= iLoopTo;i++)
    {
    sb.Append(i.ToString());
    }
    loopTS = DateTime.Now.Subtract(dt);
    lblTimestamps.Text += loopTS.TotalMilliseconds + ” milliseconds for StringBuilder”;

    dt = DateTime.Now;
    string string2 = “”;
    for(int i = 0;i <= iLoopTo;i++)
    {
    string2 = string2 + i.ToString();
    }
    loopTS = DateTime.Now.Subtract(dt);
    lblTimestamps.Text += loopTS.TotalMilliseconds + ” milliseconds for string = string +”;
    }

    My results show a pretty impressive performance difference:

    13811.8812 milliseconds for string.Concat
    31.2486 milliseconds for StringBuilder
    23561.4444 milliseconds for string = string +

    Thanks :-)

  7. 7 On November 14th, 2008, Chinh Do said:

    CoDr: Thanks for the comment. I think you may have misunderstood the purpose of my “for loop”. The loop itself is not what is being tested… think of it as “testing framework” code. The code I am testing is inside the loop. In these kinds of benchmarks, where things can happen so fast, these loops are used to perform “the test” repeatedly so that we can get a better average result in the end.

    If you don’t have the for loop, results from one test to the next are likely to vary significantly. That is if your timer is even accurate enough to measure the few microseconds it would take to concatenate those strings.

  8. 8 On November 19th, 2008, Sean Finkel said:

    In my own testing, I noticed that placing all the concatenations on one line vastly affected performance. For my tests, I had each operation run x number of time inside a loop. I then had *that* execute x number of times inside another loop. The inner loop (function) did the actual time clocking, while the outer loop was mainly used to execute the specific benchmark x times, and set performance numbers for reporting.

    For a x value of 1000 (1000 function calls, with each function call looping 1000 times) I came up with the conclusion that the + operator (actually, I used “&” in vb.net) was faster than the StringBuilder method. This was with the both functions concatenation all on the same line. When I moved the concatenation to separate lines StringBuilder came out on top. Not by much mind you.

    I concatenated the string “Test: ” followed by the loop counter variable (integer) nine times, calling the ToString method on it.

    These are the averages I got:
    Concat with ‘&’ – Same Line: 3.703125ms
    Concat with ‘&’ – Separate Line: 4.28125ms
    Stringbuilder – Same Line: 4
    Stringbuilder – Separate Line: 4.078125

  9. 9 On March 12th, 2009, Nobody said:

    This is proof why you should always be skeptical of benchmarks and benchmarkers. :)

Leave a Comment