Performance Improvement with the StringBuilder for C++ (codeproject.com)

wouldn't it be more in C++11 manner to use move semantics to solve the problem of generating new strings on concatenation?

That's the most C++ I've looked at in years. Great tip on adding memory allocation into the list of resource thieves.

I'm actually wondering if we can get a speed boost for javascript in a similar way. I find myself concating strings together often in the code.

Just last night I improved the startup of one of my apps in C++ which had a previously unexplainable 1 second delay by precomputing some string joins and splits at build time. I nearly cried. Thanks to the Instruments app on OSX which is seriously awesome!

Startup is now instantaneous. It was also making queries slower. Queries are now also instantaneous.

How does this compare to std::stringstream? I don't see any mention of that class in this article.

    Accurate performance test:
      ostringstream took 0.0120331 seconds, and ToString() took 0.0221947 seconds.
      The relative speed improvement was -45.784%
      Join took 0.0176613 seconds.

     Accumulate   took 0.00195327 seconds
     ToString()   took 0.00283577 seconds.
     Join         took 0.00462704 seconds.
     stringstream took 0.00084927 seconds.
    The relative speed improvement was -71.1482%

You have to give credit to languages like java or C# which provide the programming interface wich does the right thing. Those who use lower level languages because they want better performance should reconsider unless they have the required know-how. It baffles me that someone would write C++, and mindlessly concatenate string.

    String s = "foo" + "bar";

    String s = new StringBuilder()
        .append("foo")
        .append("bar")
        .toString();

I write enough performance-sensitive code that I've gotten into the habit of calling .reserve() with a generous final size estimate immediately after constructing a string or vector (assuming I'm not using a constructor that sizes it appropriately to begin with). It's hard to overestimate just how expensive repeated calls to malloc()/free() are.

In the innermost of inner loops, I've been known to use a static string or vector to avoid repeated allocation entirely. Only in single-threaded code of course!

Why concatenate the strings at all instead of printing them piece by piece? Don't flush in between and it'll land in the same buffer. (Even if you flushed after every string, if output is "lightning fast", that shouldn't matter either.)

This isn't just a C++ issue, in nearly every language strings will be immutable, that is if you add strings together it needs to create a new string somewhere with the new length of the string. So if you adding multiple strings together it does this each time. The better way (and how stringbuilder and it's elk do it) is to put the strings into an array and then concat (or even better output/send that to the thing that is needing the concatted string).

  s += "..."

  s = s + "..."

The article doesn't go in to much detail about why that class is really necessary. Couldn't you just loop the vector of strings, work out the total memory, then `reserve()` exactly the right amount? Then all the concatenations should be fast.

Alternatively `std::ostringstream` is specially designed for this type of task as well... how does it compare? Is it better/worse? Looks like reinventing the wheel to me.

Qt has had a compile-time string builder since about 4.6 or so, for those wanting to take advantage in real-life code.

Just grep the QString API docs for "QStringBuilder".

The performance test is comparing apples to oranges, since the StringBuilder is filled only once and the timing is taken only on the .Join() method.

If you replace the code

    start = clock();
    for (int i = 0; i < loops; ++i) {
        std::wstring result2 = tested.ToString();
    }
    double secsBuilder = (double) (clock() - start) / cps;

with

    start = clock();
    for (int i = 0; i < loops; ++i) {
        StringBuilder<wchar_t> wide;
        wide.Add(tested2.begin(), tested2.end()).AppendLine();
        std::wstring result2 = wide.ToString();
    }
    double secsBuilder = (double) (clock() - start) / cps;

the results go from

    Accumulate took 0.134847 seconds, and ToString() took 0.014123 seconds.
    The relative speed improvement was 854.804%

to

    Accumulate took 0.146171 seconds, and ToString() took 0.099802 seconds.
    The relative speed improvement was 46.461%

Much less impressive.

Furthermore, the author is not using any of the standard techniques to avoid memory allocations in C++ (such as reusing the same container with .clear() instead of creating a new one each time), that would improve even more the performance.

Besides, despite what the author says, std::list is an awful container (one allocation per element, terrible locality, ...). You should never use it, unless you really know what you are doing (for example, see Stroustrup's recent talks).

This is just a side note, but a problem with accumulate in this context is that is defined as doing `acc = op(acc, element)` for each element. This means that whatever allocation the accumulator had is going to be thrown away on each iteration of the loop. Had it been defined as `acc += element`, then allocation schemes such as doubling the allocated memory would have been more effective and greatly reduces the number of allocations (and copies).

This is reinventing the wheel. There are string streams fro that.

I had a similar problem with a gawk (yes, gawk!) program I was writing. I had to accumulate 10,000,000 32-character strings to produce a 320,000,000 (three hundred and twenty million!) character string.

It was taking forever.

I eventually realized that this string reallocation that was being done 10,000,000 times was the problem.

To solve this, I did a two-level accumulation (perhaps three levels would have been better, but two was enough). I first accumulated 3,000 of the 32-character strings (3,000 because that was about the square root of 10,000,000).

I then accumulated the (about) 3,000 of these (about) 100,000 character strings.

The result took about 30 seconds, which was good enough for what I needed to do.

If you really want performance, declare a fixed size char array (so no heap use) optimized for the best write size for your disk, mem copy the strings sequentially until you fill the array and write. Go back to beginning of array and repeat. Runs back to cave

    string s = accumulate(vec.begin(), vec.end(), s);

Is that legal C++? I would think that passes s to 'accumulate' before constructing it (http://www.gotw.ca/gotw/001.htm). IMO, a correct way to do this would be:

    string s; // calls string::string()
    s = accumulate(vec.begin(), vec.end(), s);

or string s = accumulate(vec.begin(), vec.end(), "");

While it was dealing with C strings, some years back I was curious about Firefox's poor Sunspider showing, so I dove into both the benchmark and the code, determining that-

a) SunSpider was overwhelmingly a benchmark measuring string concatenation performance. b) Firefox had slow string concatenation.

The solution to b) was trivial -- whenever Firefox saw that you were doing str = str + something, it would realloc str to the new length of len(str)+len(something)+1 and then strcpy something to the tail of str. By changing the code slightly to trade a relatively small amount of memory (in most situations), making every realloc size to the next power-of-two greater than the new combined length, this improved SunSpider performance 20x+ because the vast majority of concatenations could be done in place.