6

I'm finding standard string addition to be very slow so I'm looking for some tips/hacks that can speed up some code I have.

My code is basically structured as follows:

inline void add_to_string(string data, string &added_data) {
   if(added_data.length()<1) added_data = added_data + "{";
   added_data = added_data+data;
}

int main()
{
   int some_int = 100;
   float some_float = 100.0;
   string some_string = "test";

   string added_data;
   added_data.reserve(1000*64);

   for(int ii=0;ii<1000;ii++)
   {
      //variables manipulated here
      some_int = ii;  
      some_float += ii;
      some_string.assign(ii%20,'A');
      //then we concatenate the strings!
      stringstream fragment;
      fragment<<some_int <<","<<some_float<<","<<some_string;
      add_to_string(fragment.str(),added_data);
   }
   return;
}

Doing some basic profiling, I'm finding that a ton of time is being used in the for loop. Are there some things I can do that will significantly speed this up? Will it help to use c strings instead of c++ strings?

20
  • 15
    "Doing some basic profiling, I'm finding that a ton of time is being used in the for loop." Well, what would else would the time be used in,? It's the whole program!
    – Pubby
    Dec 13, 2012 at 1:07
  • 1
    duplicate stackoverflow.com/questions/611263/…
    – goji
    Dec 13, 2012 at 1:07
  • 3
    @user788171 I don't think so, regular addition operator on std::string explicitly creates a new object. The same with the parameter, specially since it is not const.
    – imreal
    Dec 13, 2012 at 1:17
  • 3
    @user788171: I think it'd be best if the sample reflected that. Dec 13, 2012 at 1:21
  • 2
    @user788171: it's been debated a thousand times. sprintf is faster, but sstream won't erase your harddrive if you make a typo. Dec 13, 2012 at 1:44

7 Answers 7

5

String addition is not the problem you are facing. std::stringstream is known to be slow due to it's design. On every iteration of your for-loop the stringstream is responsible for at least 2 allocations and 2 deletions. The cost of each of these 4 operations is likely more than that of the string addition.

Profile the following and measure the difference:

std::string stringBuffer;
for(int ii=0;ii<1000;ii++)
{
  //variables manipulated here
  some_int = ii;  
  some_float += ii;
  some_string.assign(ii%20,'A');
  //then we concatenate the strings!
  char buffer[128];
  sprintf(buffer, "%i,%f,%s",some_int,some_float,some_string.c_str());
  stringBuffer = buffer;
  add_to_string(stringBuffer ,added_data);
}

Ideally, replace sprintf with _snprintf or the equivalent supported by your compiler.

As a rule of thumb, use stringstream for formatting by default and switch to the faster and less safe functions like sprintf, itoa, etc. whenever performance matters.

Edit: that, and what didierc said: added_data += data;

0
4

You can save lots of string operations if you do not call add_to_string in your loop.

I believe this does the same (although I am not a C++ expert and do not know exactly what stringstream does):

stringstream fragment;
for(int ii=0;ii<1000;ii++)
{
  //variables manipulated here
  some_int = ii;  
  some_float += ii;
  some_string.assign(ii%20,'A');
  //then we concatenate the strings!
   fragment<<some_int<<","<<some_float<<","<<some_string;
}

// inlined add_to_string call without the if-statement ;)
added_data = "{" + fragment.str();
6
  • So the idea here was that I might gain speed since I can allocate memory for string with reserve(), but can't do something similar with the stringstream.
    – user788171
    Dec 13, 2012 at 1:15
  • @Veger: stringstream builds a string. In specific, that line is a very slow way to build the string "100,100.0,test" a thousand times. Dec 13, 2012 at 1:16
  • It saves you at least 999 stringstream.str() calls, 1000 string concatenations, 999 if-statement checks. Seems improvements to me! But, to know for sure you'd need to profile this!
    – Veger
    Dec 13, 2012 at 1:17
  • @MooingDuck it builds the string directly, or when you call the str() function? If it builds it directly you are right and I'll remove my answer! :)
    – Veger
    Dec 13, 2012 at 1:18
  • @Veger: Actually, it builds a string directly, and str returns a copy. However, since he says that some_int and such will be changing in teh loop, I'd actually consider yours the best answer. Please don't delete it! Dec 13, 2012 at 1:20
3

I see you used the reserve method on added_data, which should help by avoiding multiple reallocations of the string as it grows.

You should also use the += string operator where possible:

added_data += data;

I think that the above should save up some significant time by avoiding unecessary copies back and forth of added_data in a temporary string when doing the catenation.

This += operator is a simpler version of the string::append method, it just copies data directly at the end of added_data. Since you made the reserve, that operation alone should be very fast (almost equivalent to a strcpy).

But why going through all this, when you are already using a stringstream to handle input? Keep it all in there to begin with!

The stringstream class is indeed not very efficient.

You may have a look at the stringstream class for more information on how to use it, if necessary, but your solution of using a string as a buffer seems to avoid that class speed issue.

At any rate, stay away from any attempt at reimplementing the speed critical code in pure C unless you really know what you are doing. Some other SO posts support the idea of doing it,, but I think it's best (read safer) to rely as much as possible on the standard library, which will be enhanced over time, and take care of many corner cases you (or I) wouldn't think of. If your input data format is set in stone, then you might start thinking about taking that road, but otherwise it's premature optimization.

2

If you start added_data with a "{", you would be able to remove the if from your add_to_string method: the if gets executed exactly once, when the string is empty, so you might as well make it non-empty right away.

In addition, your add_to_string makes a copy of the data; this is not necessary, because it does not get modified. Accepting the data by const reference should speed things up for you.

Finally, changing your added_data from string to sstream should let you append to it in a loop, without the sstream intermediary that gets created, copied, and thrown away on each iteration of the loop.

4
  • Can you clarify what you mean in the last paragraph, added_data should be stringstream instead of string? Won't there be a lot of resizing of the added_data that would slow things down?
    – user788171
    Dec 13, 2012 at 1:27
  • 1
    @user788171: It would do the exact same resizing that you're making added_data do, but it would do it more efficiently. Dec 13, 2012 at 1:28
  • 1
    @user788171 Most certainly it's not going to be slower: you can always preallocate your sstream (here's a link showing how it can be done). Dec 13, 2012 at 1:31
  • Ok, if that preallocation of sstream trick works, then this will certainly be quicker
    – user788171
    Dec 13, 2012 at 1:33
2

Please have a look at Twine used in LLVM.

A Twine is a kind of rope, it represents a concatenated string using a binary-tree, where the string is the preorder of the nodes. Since the Twine can be efficiently rendered into a buffer when its result is used, it avoids the cost of generating temporary values for intermediate string results -- particularly in cases when the Twine result is never required. By explicitly tracking the type of leaf nodes, we can also avoid the creation of temporary strings for conversions operations (such as appending an integer to a string).

It may helpful in solving your problem.

0

How about this approach?

This is a DevPartner for MSVC 2010 report.

enter image description here

-4

string newstring = stringA & stringB;

i dont think strings are slow, its the conversions that can make it slow and maybe your compiler that might check variable types for mismatches.

3
  • 4
    I have no idea what you are talking about. Dec 13, 2012 at 1:16
  • I think user613326 has no idea what he is talking about.
    – user788171
    Dec 13, 2012 at 1:16
  • its the conversion that makes it slow, strings are not slow
    – user613326
    Dec 13, 2012 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.