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

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

[520065607613-0001]

>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:

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

[paolo]

Synopsis: Severe run-time performance regression adding to strings

Responsible-Changed-From-To: unassigned->paolo
Responsible-Changed-By: paolo
Responsible-Changed-When: Mon Jan 14 12:16:49 2002
Responsible-Changed-Why:
    Analyzed.
State-Changed-From-To: open->closed
State-Changed-By: paolo
State-Changed-When: Mon Jan 14 12:16:49 2002
State-Changed-Why:
    Together with Nathan Myers and Loren Rittle we fixed
    this some weeks ago. Now in this kind of test 3.1 is as
    fast (or faster :) than 2.95.x! See, f.i.:
    http://gcc.gnu.org/ml/libstdc++/2001-12/msg00144.html

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=5380