Optimizing string concatenation and integer to string conversion

[darlingm]

I am making this post to discuss: (a) fast string concatenation; and (b) fast conversion of integers to strings.

I am re-writing sections of an existing program. The program repeatedly concatenates strings and converts integers to strings, so I am focusing at the moment on optimizing these processes.

The simplified program below (using 10 million iterations) runs in:
* 17.97sec (with functionA) -- The previously written function
* 10.26sec (with functionB) -- Not thread safe, but otherwise the fastest & cleanest
* 10.05sec (with functionC) -- The fastest thread safe
* 6.23sec (with functionD) -- The fastest using snprintf, but I would prefer not to use snprintf

I don't want to use snprintf because I don't want to build in a limitation of a buffer size. Although a buffer size of 1024 should do the job, there could be cases in the future where it wouldn't be enough. Creating a larger buffer size would help delay that, but I still don't want that in the code here.

I think I've largely optimized the integer to string conversion almost as much as possible. The original function, functionA, without concatenating strings runs in 9.9 seconds. The new function, functionC, without concatenating strings runs in 2.61 seconds.

However, I haven't done anything to optimize concatenating strings, with the exception of functionD which uses snprintf, which I would prefer not to use. I am hoping to find a string concatenation method closer to the speed of functionD which uses snprintf.

Can anyone make this program run even faster? I think there has to be some room in speeding things up with the concatenation phase. I've often read that concatenating strings in a chain like this is creating unused instances of the string class inbetween, but I'm not sure how to get around it.

I have tried using the "Fast, non-intrusive string concatenation" method as described in "Imperfect C++" by Matthew Wilson and in Wilson's article on ddj.com dated June 1, 2004, and actually got a slight performance decrease by using his method.

In case it matters, I'm using g++ 4.1.2, and I don't care about compatability with other compilers or previous g++ versions.

#include <stdlib.h>
#include <string>
#include <sstream>

using namespace std;

void foo(const string& str) {
}

string int2string(int num) { // This was previously written
   ostringstream oss;
   oss << num;
   return oss.str();
}

void functionA(const unsigned int num) { // Runs in 17.97sec, this was previously written
   foo("Beginning part of string " + int2string(num) + " Ending part of string");
}

string itoaANotThreadSafe(unsigned int num) {
   static char buffer[32] = {0};
   int i = 30;
   for( ; num && i ; --i, num /= 10) {
      buffer[i] = "0123456789"[num % 10];
   }
   return (string) &buffer[i+1];
}

void functionB(const unsigned int num) { // Runs in 10.26sec
   foo("Beginning part of string " + itoaANotThreadSafe(num) + " Ending part of string");
}

char* itoaB(char* buffer, size_t bufferSize, unsigned int num) {
   char* ptr = buffer + bufferSize - 1;
   *ptr = 0;
   do {
      unsigned lsd = num % 10;
      num /= 10;
      --ptr;
      *ptr = "0123456789"[lsd];
   } while(num != 0);
   return ptr;
}

void functionC(const unsigned int num) { // Runs in 10.05sec
   char buffer[1024];
   foo("Beginning part of string " + (string) itoaB(buffer, 1024, num) + " Ending part of string");
}

void functionD(const unsigned int num) { // Runs in 6.23sec
   char buffer[1024];
   snprintf(buffer, 1024, "Beginning part of string %d Ending part of string", num);
   foo(buffer);
}

int main() {
   for(int i = 0 ; i < 10000000 ; ++i) {
      functionA(42109);
      functionB(42109);
      functionC(42109);
      functionD(42109);
   }
}

[Paul McKenzie]

I am making this post to discuss: (a) fast string concatenation; and (b) fast conversion of integers to strings.

I am re-writing sections of an existing program. The program repeatedly concatenates strings and converts integers to strings, so I am focusing at the moment on optimizing these processes.

1) Please use code tags when posting code.

2) string concatenation is usually very slow, unless you can preallocate the memory using string::reserve. If you know that you will have more than a megabyte of string concatenations coming, then use std::string::reserve() up front before running the tests.

In a real program, the reserve() will take time, but that is much better waiting a second or two for reserve then 10 or 20 seconds for a slow concatenation without any reserve memory (this is the case with various versions of the Visual C++ compiler).

3) You didn't test passing a string by reference that will be concatenated onto.

Regards,

Paul McKenzie

[TheCPUWizard]

In addition to Pauls comments....

Why do you need "fast"?

This should ALWAYS be a "last concern" (Maintainability, Reliability, etc all take precidence), Unless you have actually measured a situation and have specifically identified that the change will make a meaningful impact on the actual application performance.

As an example, pretend that your application takes 10 minutes to run. Then your initial numbers reveal:

* FunctionA = BASELINE
* FunctionB = 1.28% savings.
* FunctionC = 1.32% savings.
* FunctionD = 1.96% savings.

These are not (typically) sufficient improvements to warrant sacrificing good design principles.

Of course if your entire real world program runs in in a total of 20 seconds (using FunctionA), then the numbers would be completely different.

[Lindley]

Why do you need "fast"?

This should ALWAYS be a "last concern" (Maintainability, Reliability, etc all take precidence)

Fast should be a first and last concern, but in different ways. Yes, "clever" optimizations which obfuscate the code are last-priority changes. However, the first thing to consider in any algorithm is the overall design, and speed can be a major consideration there.

For example, if an algorithm is massively parallel, it may be worth investigating whether it can be implemented on a GPU using CUDA or CTM or OpenGL. That's purely a speed consideration, but it still must be an initial one if it is to be considered at all. (Granted that's not a concern in this particular case.)

[darlingm]

1) Please use code tags when posting code.

2) string concatenation is usually very slow, unless you can preallocate the memory using string::reserve. If you know that you will have more than a megabyte of string concatenations coming, then use std::string::reserve() up front before running the tests.

In a real program, the reserve() will take time, but that is much better waiting a second or two for reserve then 10 or 20 seconds for a slow concatenation without any reserve memory (this is the case with various versions of the Visual C++ compiler).

3) You didn't test passing a string by reference that will be concatenated onto.

Regards,

Paul McKenzie

Thanks for pointing out the code tags, I edited my original post to use them.

I'm not sure exactly where you mean to try testing passing a string by reference to be concatenated onto. I always pass strings by reference when I can. I'm not aware of any times in the program I laid out that I could pass a string by reference where it doesn't already, or where passing a new string by reference would speed things up.

In addition to Pauls comments....

Why do you need "fast"?
. . .

I have measured an area in the application I'm working on as a bottleneck that should be able to be substantially improved to have a meaningful impact on the users' wait times.

I'm working on the more complicated parts of the re-design, but picked out the string concatenation and integer to string conversion to post about because they are relatively simple and because those processes are done many times over in the application, so I figured it would be an easy thing to change to create speedups in other areas as well. This change is going along with other changes that are adding up to significant time savings.

I definately agree with you that "fast" shouldn't be at the cost of code readability, maintainability, and reliability.

[TheCPUWizard]

Fast should be a first and last concern, but in different ways. Yes, "clever" optimizations which obfuscate the code are last-priority changes. However, the first thing to consider in any algorithm is the overall design, and speed can be a major consideration there.

For example, if an algorithm is massively parallel, it may be worth investigating whether it can be implemented on a GPU using CUDA or CTM or OpenGL. That's purely a speed consideration, but it still must be an initial one if it is to be considered at all. (Granted that's not a concern in this particular case.)

Lindley... I was going to send this in a PM...but you have them disabled...

If the system is a real-time system with specific performance REQUIREMENTS, then I agree with. Back when I used to do Weapon systems, we had a saying "Its no good to target where the plane WAS".

However, the majority of applications discussed here are either desktop or web applications, where the design does not impose strict timing requirements [eg You must receive a response so many milliseconds after clicking button X"].

Decisions such as implementing a specific functionallity on a dedicated processor (such as a GPU) really dshould have NO bearing on the initial design and implementation.

If the class structure of the application is well designed with minimal levels of coupling, it should be a trivial effort to completely swap out the algorithm in question. Deciding to implement something on a dedicated resource early in the game can often cause real problems at the system integration level.

Consider what would happen if two developers working on different parts of an appliication decided to do some heavy matrix math on the GPU. At integration time, it is discovered that these two algorithms must run at the same time (i.e. overlapped). The decision to use the GPU would then become a severe negative one (as most systems only have one GPU).

On the other hand, if both developers had simply coded their routines, then deployment to a target system with more cores would (potientially) provide the performance boost without ANY changes to the code.

So I stand by my original post...It has worked out very well for me over the last 30 years.

[Lindley]

PMs must be disabled by default, I never touched that setting. Rather silly board setting, but whatever.

The GPU thing was just one example of how speed can be a design concern early on. Perhaps a more relevant one is big-oh running time of the selected algorithms. And perhaps "design" isn't even the right word.....I'm not talking high-level conceptual stuff. I'm talking about the thought process prior to writing an implementation.

Oh, and for the record GPUs can handle running multiple programs at once, although there can be major slowdowns if you exceed the available memory (of course) or simply if there are frequent context switches.

[souldog]

I had a problem with speed in the past using strings as in-memory buffers. I fixed it
by simply changing to STLport for the standard library, instead of the dinkumware version shipped with VC++.

[Paul McKenzie]

I'm not sure exactly where you mean to try testing passing a string by reference to be concatenated onto. I always pass strings by reference when I can.

Something like this:

void foo(std::string& str)
{
   // now you concatenate onto str
}

void foo2()
{
   std::string s;
   s.reserve( 1000000 );
   foo( s );
}

Then you can easily test things such as reserve().

Regards,

Paul McKenzie

[TheCPUWizard]

PMs must be disabled by default, I never touched that setting. Rather silly board setting, but whatever..

It actually makes good sense, and is covered (indirectly) by the FAQs

The GPU thing was just one example of how speed can be a design concern early on. Perhaps a more relevant one is big-oh running time of the selected algorithms. And perhaps "design" isn't even the right word.....I'm not talking high-level conceptual stuff. I'm talking about the thought process prior to writing an implementation..

Of course there is no reason to deliberately write poor performance code, but even looking at "BIG-O" without knowledge of the data and performance requirements can lead you down the wrong path.

T1 = K1 * O(n)
T2 = K2 * O(nLogn)
T3 = K3 * O(n^2)

Naive people would think that the above are listed in order of increasing execution tiimes, but this is NOT true. Differing values of K1..K3 and "n" can cause ANY of the three to be eityher the fastest or slowest.

Oh, and for the record GPUs can handle running multiple programs at once, although there can be major slowdowns if you exceed the available memory (of course) or simply if there are frequent context switches.

Even here you are contraticting yourself. If there is a context switch, then they are NOT running at the same time. Their executions are being interleaved. The ONLY machines I have found with true simultanious processing at the GPU level is on some VERY high end CAD systems ($50K/machine+).

[Lindley]

Well, that's a semantic difference, really....CPU parallel processing is interleaved as well to the extent there aren't enough cores available. The point is that the program wouldn't break in that case. Probably. If NVIDIA/ATI drivers aren't awful (which you can't guarantee).

Besides, this is an academic discussion because one wouldn't introduce a dependency on a GPU unless the project were about that specifically, in which case usage would be coordinated with the other team members anyway. It was simply one example of how speed concerns can affect the early planning stages. I just had the first paper with my name on it accepted at a conference, and it's in the area of GPU acceleration, so it's a bit on the brain.

[TheCPUWizard]

Agreed it is academic, but one of the issues with open forum posts (see my previous note on PM's) is that this information may be read 10 years from now, and not necessiarily in context.

Congratulations on your paper.

btw: I would still pick "cores" as the way to go over a GPU. I just finised ordering the parts for my new development machine (alas with quite a bit of back-order). Quad Socket 8-Core (not yet available for general sale) with 64GB of memory. Should be sweet (for everything except Visual Studio which is still basically single threaded. )

[Mybowlcut]

Agreed it is academic, but one of the issues with open forum posts (see my previous note on PM's) is that this information may be read 10 years from now, and not necessiarily in context.

Congratulations on your paper.

btw: I would still pick "cores" as the way to go over a GPU. I just finised ordering the parts for my new development machine (alas with quite a bit of back-order). Quad Socket 8-Core (not yet available for general sale) with 64GB of memory. Should be sweet (for everything except Visual Studio which is still basically single threaded. )

I know I'm going off topic here, but I couldn't help noticing that 64g of memory... why do you need so much? Same goes for the 8-core!