libstdc++/5380: Severe run-time performance regression adding to strings

[520065607613-0001@t-online.de]

>Number:         5380
>Category:       libstdc++
>Synopsis:       Severe run-time performance regression adding to strings
>Confidential:   no
>Severity:       non-critical
>Priority:       low
>Responsible:    unassigned
>State:          open
>Class:          change-request
>Submitter-Id:   net
>Arrival-Date:   Mon Jan 14 11:56:01 PST 2002
>Closed-Date:
>Last-Modified:
>Originator:     Frank Pilhofer
>Release:        3.1 20011126 (experimental)
>Organization:
>Environment:
System: Linux rose 2.2.13 #1 Mon Nov 8 15:08:22 CET 1999 i586 unknown
Architecture: i586

	
host: i586-pc-linux-gnu
build: i586-pc-linux-gnu
target: i586-pc-linux-gnu
configured with: ../configure --prefix=/local/pkg/gcc/20011126
>Description:
I'm experiencing a severe slowdown in one of my programs which seems to
be due to loops that add characters to a string one at a time. Consider
the attached test program, which adds 100000 characters to an empty
string. Using gcc 2.95.2, this finishes almost immediately (time reports
about 100 msec). Using the CVS version (tested: Nov 26, 2001) with the
new libstdc++, the same program takes 70 seconds (!) here.

Experimenting with the number of iterations indicate that performance
of the operator+= (char) operation is in fact worse than O(n^2).
>How-To-Repeat:
#include <string>

using namespace std;

int main ()
{
  string foo;

  for (int i=0; i<100000; i++) {
        foo += 's';
  }

  return 0;
}
>Fix:
	
>Release-Note:
>Audit-Trail:
>Unformatted: