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);
   }
}