std::string::operator+=() slow

• Key: STDCXX-492
• Type: Bug
• Status: Resolved
• Resolution: Fixed
• Priority: Major
• Assignee: Travis Vitek
• Reporter: Mark Brown
• Component/s: 21. Strings
• Affects Version/s: 4.1.3
• Fix Version/s: 4.2.0

Description

Comparing overloads of string::operator+=() in stdcxx with the same functions in gcc 4.1.2, stdcxx is up to twice slower than gcc:

$ time ./op_plus_equal-stdcxx 100000000 0

real 0m2.241s
user 0m1.932s
sys 0m0.204s
$ time ./op_plus_equal-stdcxx 100000000 1

real 0m2.540s
user 0m2.344s
sys 0m0.196s
$ time ./op_plus_equal-stdcxx 100000000 2

real 0m1.492s
user 0m1.308s
sys 0m0.184s
$ time ./op_plus_equal-gcc 100000000 0

real 0m0.883s
user 0m0.728s
sys 0m0.156s
$ time ./op_plus_equal-gcc 100000000 1

real 0m1.589s
user 0m1.424s
sys 0m0.168s
$ time ./op_plus_equal-gcc 100000000 2

real 0m1.131s
user 0m0.976s
sys 0m0.156s

#include <cassert>
#include <cstdlib>
#include <string>

int main (int argc, char *argv[])
{
const int N = argc < 2 ? 1 : std::atoi (argv [1]);
const int op = argc < 3 ? 0 : std::atoi (argv [2]);

std::string str;

const std::string x ("x");

if (op == 0) { for (int i = 0; i < N; ++i) str += 'x'; } else if (op == 1) { for (int i = 0; i < N; ++i) str += "x"; } else { for (int i = 0; i < N; ++i) str += x; }

assert (str.size () == std::size_t (N));
}

Comments

[Martin Sebor]

Should be simple enough for 4.2. Might be able to use the same approach as in STDCXX-491.

Possibly related to STDCXX-491.

[Travis Vitek]

Patch improves times of both basic_string<>::append() and basic_string<>::op+=().

I've looked at the gnu changelog format description, and it doesn't mention what to do when you are changing multiple overloads of the same functions. I'm guessing, here, but if that is wrong, please correct me.

2007-09-24 Travis Vitek <[e-mail]>

STDCXX-492

• string (operator+=): replace call to append with push_back
  for performance.
  (append): avoid calling replace() from append if there is
  sufficient buffer space available for performance.
  (append): simplify append overload, move it to header and then
  inline it.
  (append): use _RWSTD_SIZE_T to avoid integer overflow problems
  that could lead to heap corruption.
  (push_back): call replace() instead of append when buffer
  reallocation required. cleanup. avoid integer overflow problem.
• string.cc (append): moved append overload to header and make
  it inline.

[Travis Vitek]

I created a little more comprehensive test to verify the timing of all of the append related functions. It just displays the system time, because I couldn't find an immediate way to get the user time on windows. Source code attached...

before [win32]
4.484000 [string::append(string, size_type, size_type)]
1.484000 [string::append(string)]
1.235000 [string::append(const_pointer, size_type)]
1.594000 [string::append(const_pointer)]
2.765000 [string::append(iterator, iterator)]
2.516000 [string::append(size_type, value_type)]
1.453000 [string::operator+=(string)]
1.578000 [string::operator+=(const_pointer)]
2.407000 [string::operator+=(value_type)]
0.546000 [string::push_back(value_type)]

after [win32]
1.718000 [string::append(string, size_type, size_type)]
1.469000 [string::append(string)]
1.234000 [string::append(const_pointer, size_type)]
1.578000 [string::append(const_pointer)]
2.766000 [string::append(iterator, iterator)]
1.093000 [string::append(size_type, value_type)]
1.469000 [string::operator+=(string)]
1.578000 [string::operator+=(const_pointer)]
0.547000 [string::operator+=(value_type)]
0.547000 [string::push_back(value_type)]

before [linux]
[vitek@fornax] 656 % ./21.string.append.perf
14.216000 [string::append(string, size_type, size_type)]
1.968000 [string::append(string)]
1.838000 [string::append(const_pointer, size_type)]
3.934000 [string::append(const_pointer)]
2.986000 [string::append(iterator, iterator)]
7.053000 [string::append(size_type, value_type)]
1.950000 [string::operator+=(string)]
4.069000 [string::operator+=(const_pointer)]
7.056000 [string::operator+=(value_type)]
0.338000 [string::push_back(value_type)]

after [linux]
[vitek@fornax] 565 % ./21.string.append.perf
2.854000 [string::append(string, size_type, size_type)]
1.985000 [string::append(string)]
1.856000 [string::append(const_pointer, size_type)]
3.938000 [string::append(const_pointer)]
3.040000 [string::append(iterator, iterator)]
1.106000 [string::append(size_type, value_type)]
1.969000 [string::operator+=(string)]
4.209000 [string::operator+=(const_pointer)]
0.325000 [string::operator+=(value_type)]
0.328000 [string::push_back(value_type)]

[Martin Sebor]

Woohoo! The numbers look awesome!

As for how to enter different overloads into a ChangeLog, I don't have a good answer for you. I have had the occasional need to distinguish between two or more overloads of the same function in the past but so far I've always decided to ignore this detail. It might be worthwhile to look into it some more and look at some other C++ projects' ChangeLogs to see how they deal with it.

The one change I did make to the format of your ChangeLog is capitalize the first letter of every sentence for consistency with the most of the rest of our ChangeLogs.

[Martin Sebor]

Resolved by the committed patch: http://svn.apache.org/viewvc?rev=579001&view=rev