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?

Mooing Duck
  • 64,318
  • 19
  • 100
  • 158
user788171
  • 16,753
  • 40
  • 98
  • 125
  • 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 '12 at 01:07
  • 1
    duplicate http://stackoverflow.com/questions/611263/efficient-string-concatenation-in-c – goji Dec 13 '12 at 01:07
  • 1
    not a duplicate, he's using a stringstream and the streaming operator, which is actually causing his problem – Peter Dec 13 '12 at 01:08
  • 1
    You're passing data by value instead of by `const &`, for one. – Yuushi Dec 13 '12 at 01:10
  • 1
    Start by avoiding unnecessary temp objects by turning `string data` parameter into a const reference. Then change the additions for addition assignments `+=` – imreal Dec 13 '12 at 01:10
  • Just to clarify, obviously the loop is taking up almost all of the time for the program to run. But what I mean is that the time it takes for that loop to run is longer than I would like, and I would like to make it faster somehow. – user788171 Dec 13 '12 at 01:12
  • @Nick, shouldn't the compiler optimisation flags handle most of this for me? I'm using -03 – user788171 Dec 13 '12 at 01:13
  • @Veger, care to elaborate? if i move the stringstream outside, i have to clear it before reusing it, that's not a cheap call either. – user788171 Dec 13 '12 at 01:14
  • 1
    @user788171: it might , but concatenating 14 characters to a string 1000 times one at a time is going to be slow. – Mooing Duck Dec 13 '12 at 01:15
  • 1
    @user788171: luckily, you aren't reusing it, you're using it to build the same 14 character string 1000 times, which is also slow. – Mooing Duck Dec 13 '12 at 01:16
  • 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 '12 at 01:17
  • @MooingDuck, yea, my example is simplified, obviously in actual usage, the some_string, some_int will be changing. – user788171 Dec 13 '12 at 01:17
  • 3
    @user788171: I think it'd be best if the sample reflected that. – Mooing Duck Dec 13 '12 at 01:21
  • 1
    @user788171: The optimizer can only do so much. Your code tells it to keep destroying and making new stringstreams over and over, it does that. You tell it to make copies of strings all over, it does that too. You tell it to concatenate one bit at a time, and it obliges. – Mooing Duck Dec 13 '12 at 01:28
  • Can somebody comment on Peter's suggestion below to use sprintf and avoid sstream altogether? Is that significantly more efficient than sstream? – user788171 Dec 13 '12 at 01:36
  • 2
    @user788171: it's been debated a thousand times. `sprintf` is faster, but `sstream` won't erase your harddrive if you make a typo. – Mooing Duck Dec 13 '12 at 01:44
  • You should also note that the `inline` keyword does not guarantee that the function will be inlined - it is a decision that is left to the compiler. – Carl Dec 13 '12 at 01:59
  • @MooingDuck Now I really want to know how to erase my hard drive using just sprintf. It sounds like a stretch. Are we exploiting for shell access? – Steven Lu Jan 05 '14 at 01:23
  • @StevenLu: You allocate a fixed sized buffer on the stack, you call the sprintf routine for that buffer and a format containing %s, with a user alterable string. Hacker injects a DLL into the process (far easier than you'd think). Hacker makes the string too long, so that it fills the buffer, and then overwrites other information on the stack, including the function to return to when sprintf is done. Sprintf attempts to return, but "returns" to the code the Hacker has placed in his DLL. The DLL does whatever it wants, including launching other processes. To be fair, modern OS's will stop it. – Mooing Duck Jan 05 '14 at 04:59
  • I guess that's more or less how such things go down on Windows, I guess. I was thinking it might be doable without injecting code into the process but it probably depends on the capabilities of the process in question. – Steven Lu Jan 05 '14 at 08:26

7 Answers7

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;

Peter
  • 5,608
  • 1
  • 24
  • 43
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();
Veger
  • 37,240
  • 11
  • 105
  • 116
  • 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 '12 at 01: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. – Mooing Duck Dec 13 '12 at 01: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 '12 at 01: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 '12 at 01: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! – Mooing Duck Dec 13 '12 at 01:20
  • @Veger: I figured it would clarify the question to _not_ have to make that assumption. I then figured it would clarify the answers to reflect the code in the question. I apologize for overstepping my bounds. It's hard to figure out exactly where the lines are on a forum such as this. – Mooing Duck Dec 13 '12 at 01:34
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.

didierc
  • 14,572
  • 3
  • 32
  • 52
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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 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 '12 at 01:27
  • 1
    @user788171: It would do the exact same resizing that you're making `added_data` do, but it would do it more efficiently. – Mooing Duck Dec 13 '12 at 01: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](http://stackoverflow.com/a/1941127/335858)). – Sergey Kalinichenko Dec 13 '12 at 01:31
  • Ok, if that preallocation of sstream trick works, then this will certainly be quicker – user788171 Dec 13 '12 at 01: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.

Lei Mou
  • 2,562
  • 1
  • 21
  • 29
0

How about this approach?

This is a DevPartner for MSVC 2010 report.

enter image description here

EvilTeach
  • 28,120
  • 21
  • 85
  • 141
-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.

user613326
  • 2,140
  • 9
  • 34
  • 63