My last column discussed a flawed benchmark that purported to show a speed difference between C# and VB.NET when in reality it showed a difference between a library some VB programmers might choose and another library that everyone should actually use. I’m still thinking along those lines, about how there are different ways to tackle any particular problem and the speed differences these can trigger.
The classic example that comes up in any .NET performance example is string concatenation. Because the System::String object is immutable, any code that appears to change a String actually makes another one, leaving the old one for garbage collection. Code that wastefully makes and discards many String objects is slow and inefficient. The StringBuilder object is designed specifically to overcome this problem. But, I started to wonder whether StringBuilder is as fast as what I could do myself with char* and a little pointer manipulation. And what about the STL? It has a string class; how does that stack up for performance?
I adapted my test harness from the previous column to call one of four functions that do the same thing: concatenate one string onto the end of another over and over again. Each test runs the same number of loops, and I only run one of the tests per run to keep things as stable as possible.
String::Concat
Here’s the slowest way of all, using the static Concat method of the String class:
void StringConcat::build(int loops) { String* block = "123456789012345678901234567890"; String* result = String::Empty; for (int i=0; i<loops;i++) result = String::Concat(result, block); Console::WriteLine(result->Length.ToString()); return; }
You have to remind yourself that Concat is static. I always want to call it like this:
result = result->Concat(block);
That won’t lengthen the string at all. It will take block, concatenate a null string onto it (because the default value for the second parameter is a null string), and put the output string into result. The fact that you used result to call the method is irrelevant. Think of Concat as a replacement for strcat, and you’ll be more comfortable calling it correctly.
This code is easy to write but it’s pig-slow. The more loops you do, the worse it gets, shedding longer and longer temporary strings and thus triggering more and more garbage collection. Moving away from Concat() is a no-brainer. How slow is it? On my machine, to get the other solutions to take long enough that their times exceeded the 10 ms accuracy level of my timing technique, I had to crank the loops variable up to 5000. That made the Concat technique take as long as TEN SECONDS—one thousand times as long as the other techniques.
StringBuilder
Any “tips and tricks” presentation on the .NET Base Class Libraries will tell you that StringBuilder is better than String::Concat. Here’s how that looks:
void StringBuild::build(int loops) { String* block = "123456789012345678901234567890"; StringBuilder* result = new StringBuilder(); for (int i=0; i<loops;i++) result->Append(block); String* realresult = result->ToString(); Console::WriteLine(realresult->Length.ToString()); return; }
The only hassle is remembering to call ToString() on the StringBuilder when you’ve finished building it. The code is simple to write and to read, and it’s much much faster than the String::Concat() case. But it’s not the fastest, at least not always.
Hand-allocating a buffer
StringBuilder works by allocating more memory than you need, and by tacking the new strings into that buffer. Every time you need the buffer to enlarge, it doubles in size. That approach was chosen as a trade-off between allocating too much memory and wasting a lot of time allocating little extra bits over and over again. The starting size is implementation-specific, but in most cases it’s 16 characters. You can pass an integer to the StringBuilder constructor to bump up the initial allocation if you know what you’ll need: That will save you the extra allocations but it won’t save you all the testing to see whether you’ve exceeded your capacity or not.
So, because this is C++ after all, let’s do something they can’t do in VB and play with pointers a little. Look at this code:
void StringBuffer::build(int loops) { char* block = "123456789012345678901234567890"; int delta = strlen(block); char* buffer = new char[loops*strlen(block)+1]; char* p = buffer; for (int i=0; i<loops;i++) { strcpy(p,block); p += delta; } String* result = buffer; Console::WriteLine(result->Length.ToString()); return; }
Whenever you work with char* strings, you have to remember when to add an extra character for the or when to move past it or before it or whatever. In this code, the delta, how much we move forward each time, is deliberately set to exactly the strlen of block—normally you would add 1 to allow room for the , but I want the first character of the next append to overwrite the so we have one long, contiguous string at the end.
This code works, and it is faster than StringBuilder. That’s not surprising, because I don’t have to test to see whether I am exceeding my capacity, and I don’t have to allocate more memory. Because I’m steering clear of the managed heap except for the final string, I’m probably not exercising the garbage collector either. So what is surprising is that’s it’s not very much faster than StringBuilder: about 10-20% less time for the same number of loops. And this is for a special case where I knew the exact length of the buffer in the end. For the general case where you’re gluing together an unknown number of strings, each of an unknown length, you’re not going to beat StringBuilder with something you write yourself. That’s worth knowing, isn’t it?
STL string
Finally, I turned my attentions to the Standard Template Library. It has a string class, and that class has an append() method that presumably takes the same kind of care to avoid wasteful repetitive allocations. Working with the STL is sometimes intimidating, but not with the string class. Here’s the same loop using the STL:
void STL::build(int loops) { char* block = "123456789012345678901234567890"; string result; for (int i=0; i<loops;i++) { result.append(block); } String* realresult = result.c_str(); Console::WriteLine(realresult->Length.ToString()); return; }
How does this perform? Slower than my hand-tailored buffer, and also slower than StringBuilder, by quite a bit more than the difference between those two. I’d say that puts it out of contention if you’re writing managed code: Use the easier StringBuilder class and leave STL strings out of it.
What Should You Do?
The most important thing to do is stay away from String::Concat as much as you possibly can. In most cases, just automatically use a StringBuilder. It’s not such finicky work as pointer manipulation, and makes it possible to create a verifiable assembly if you’re willing to jump through the other hoops involved in becoming verifiable. But in the back of your mind, remember that you are still writing C++. If profiling or a performance-critical application or component ever reveals that your code is spending a lot of time in string manipulation, you can always rewrite the slow parts to use pointer manipulation.
About the Author
Kate Gregory is a founding partner of Gregory Consulting Limited (www.gregcons.com). In January 2002, she was appointed MSDN Regional Director for Toronto, Canada. Her experience with C++ stretches back to before Visual C++ existed. She is a well-known speaker and lecturer at colleges and Microsoft events on subjects such as .NET, Visual Studio, XML, UML, C++, Java, and the Internet. Kate and her colleagues at Gregory Consulting specialize in combining software develoment with Web site development to create active sites. They build quality custom and off-the-shelf software components for Web pages and other applications. Kate is the author of numerous books for Que and Sams, including Microsoft Visual C++ .NET 2003 Kick Start.