 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Stefan Rupp
Guest
|
 Posted: Sun Feb 01, 2004 8:07 pm Post subject: string::operator+ vs. string::operator+= vs. ostringstream:: |
 |
|
Konichiwa!
Quite a while ago I was porting code form g++ 2.95 to gcc 3.x and
encountered some problems with expressions like
string s = string("a") + string("b") + string("c") + ...
which appeared to be very slow not only when executed but also during
the compile. I found this was due to template instantiation and
temporary creations. I replaced most of the above expressions by the
better performing form:
string s = string("a");
s += string("b");
s += string("c");
....
This was quite an improvement in both compile and runtime performance.
Now, more than a year later, I need to do something similar in another
piece of code and tried something else:
ostringstream oss;
oss << "a" << "b" << "c" << ...
s = oss.str();
But to my surprise this code performs even worse during runtime than the
original code with operator+ and all the temporaries.
I did some benchmarking and the result was the following:
With the 26 variable a, b, c, ... z defined as strings "a", "b", etc.
and a (non-inline) function foo, which simply returns its argument, I
did a loop with 1 million iterations of each one of the following three
functions:
std::string
foobar1()
{
std::ostringstream oss;
oss << a << b << c << d << e << f << g << h << i
<< j << k << l << m << n << o << p << q << r
<< s << t << u << v << w << x << y << z;
return foo( oss.str() );
}
std::string
foobar2()
{
std::string s( a );
s += b;
s += c;
s += d;
s += e;
s += f;
s += g;
s += h;
s += i;
s += j;
s += k;
s += l;
s += m;
s += n;
s += o;
s += p;
s += q;
s += r;
s += s;
s += t;
s += u;
s += v;
s += w;
s += x;
s += y;
s += z;
return foo( s );
}
std::string
foobar3()
{
return foo( a + b + c + d + e + f + g +
h + i + j + k + l + m + n +
o + p + q + r + s + t + u +
v + v + x + y + z );
}
Function foobar1 using ostringstream::operator<< took 10 seconds to run,
function foobar2 using string::operator+= only 2 seconds, but even
function foobar3 using string::operator+= took with 9 seconds. This
test was done with g++ 2.95.4 from Debian GNU/Linux on a i386 box (2 x
2.8 GHz Intel XEON).
To see how the same code behaves when compiled with a different compiler
version, I did the test with g++ 3.3 and got the following times:
foobar1: 14 seconds, foobar2: 24 seconds, foobar3: 21 seconds.
Now the stream based solution performed best, but all three variants
were ways slower than the ones compiler with g++ 2.95.
I assume it's only the stringstream implementation of gcc 2.95 which is
very poor, so the 2.95 results are not very representative, and I also
assume that I need to use some more nifty compiler optimisations to
reduce the runtime of the gcc 3.3 binaries (I compiled all files with
-O2), otherwise the poor results of the g++ 3.3 compiler would be
unacceptable.
But I still do not understand why foobar3 performs better than foobar2
when compiled with gcc 3.3. Both use strings, but foobar3 produces many
temporaries, whereas foobar2 doesn't.
Regards,
Stefan
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Alf P. Steinbach
Guest
|
| Posted: Mon Feb 02, 2004 8:24 am Post subject: Re: string::operator+ vs. string::operator+= vs. ostringstre |
|
|
On 1 Feb 2004 15:07:18 -0500, Stefan Rupp <st.rupp (AT) t-online (DOT) de> wrote:
Bånnski!
| Quote: | I did some benchmarking and the result was the following:
With the 26 variable a, b, c, ... z defined as strings "a", "b", etc.
and a (non-inline) function foo, which simply returns its argument, I
did a loop with 1 million iterations of each one of the following three
functions:
...
std::string
foobar2()
{
std::string s( a );
....
s += q;
s += r;
s += s;
|
Oops.
Thanks to Thore Karlsen for noticing that bug, I didn't...
I added a foobar4 to have some basis for comparing the overhead.
Here are my results for 100.000 calls (note the anomalous result for
VC debug, where std::stringstream, in foobar2(), is _fastest_), code
follows after the results:
===================================================================
Debug (VC 7.1, 1.8 GHz single processor Dell PC)
abcdefghijklmnopqrstuvwxyz
foobar1: 14.937 seconds elapsed
abcdefghijklmnopqrstuvwxyz
foobar2: 5.516 seconds elapsed
abcdefghijklmnopqrstuvvxyz
foobar3: 24.672 seconds elapsed
abcdefghijklmnopqrstuvwxyz
foobar4: 9.703 seconds elapsed
Release (VC 7.1, 1.8 GHz single processor Dell PC)
abcdefghijklmnopqrstuvwxyz
foobar1: 0.531 seconds elapsed
abcdefghijklmnopqrstuvwxyz
foobar2: 0.359 seconds elapsed
abcdefghijklmnopqrstuvvxyz
foobar3: 1.688 seconds elapsed
abcdefghijklmnopqrstuvwxyz
foobar4: 0.219 seconds elapsed
Release (MingW g++ 3.2.3, 1.8 GHz single processor Dell PC)
abcdefghijklmnopqrstuvwxyz
foobar1: 0.875 seconds elapsed
abcdefghijklmnopqrstuvwxyz
foobar2: 1.375 seconds elapsed
abcdefghijklmnopqrstuvvxyz
foobar3: 2.171 seconds elapsed
abcdefghijklmnopqrstuvwxyz
foobar4: 0.532 seconds elapsed
===================================================================
And here's the test code:
===================================================================
#include <ctime>
#include <iomanip> // std::setw
#include <iostream> // std::cout
#include <sstream> // std::ostringstream
#include <string> // std::string
#include <vector> // std::vector
std::string const a = "a";
std::string const b = "b";
std::string const c = "c";
std::string const d = "d";
std::string const e = "e";
std::string const f = "f";
std::string const g = "g";
std::string const h = "h";
std::string const i = "i";
std::string const j = "j";
std::string const k = "k";
std::string const l = "l";
std::string const m = "m";
std::string const n = "n";
std::string const o = "o";
std::string const p = "p";
std::string const q = "q";
std::string const r = "r";
std::string const s = "s";
std::string const t = "t";
std::string const u = "u";
std::string const v = "v";
std::string const w = "w";
std::string const x = "x";
std::string const y = "y";
std::string const z = "z";
std::string foo( std::string const& s )
{
return s;
}
std::string foobar1()
{
std::ostringstream oss;
oss << a << b << c << d << e << f << g << h << i
<< j << k << l << m << n << o << p << q << r
<< s << t << u << v << w << x << y << z;
return foo( oss.str() );
}
std::string foobar2()
{
std::string result( a );
result += b;
result += c;
result += d;
result += e;
result += f;
result += g;
result += h;
result += i;
result += j;
result += k;
result += l;
result += m;
result += n;
result += o;
result += p;
result += q;
result += r;
result += s;
result += t;
result += u;
result += v;
result += w;
result += x;
result += y;
result += z;
return foo( result );
}
std::string foobar3()
{
return foo( a + b + c + d + e + f + g +
h + i + j + k + l + m + n +
o + p + q + r + s + t + u +
v + v + x + y + z );
}
static std::string const * const ps[] =
{
&a, &b, &c, &d, &e, &f, &g, &h, &i, &j, &k, &l, &m, &n, &o, &p, &q,
&r, &s, &t, &u, &v, &w, &x, &y, &z
};
template< typename T, std::size_t N > std::size_t size( T(&)[N] ){ return N; }
std::string foobar4()
{
std::size_t bufferSize = 0;
for( std::size_t i = 0; i < size( ps ); ++i )
{
bufferSize += ps[i]->length();
}
std::vector<char> buffer( bufferSize );
std::size_t endIndex = 0;
for( std::size_t i = 0; i < size( ps ); ++i )
{
std::copy( ps[i]->begin(), ps[i]->end(), &buffer[endIndex] );
endIndex += ps[i]->length();
}
return foo( std::string( &buffer[0], bufferSize ) );
}
template< std::string (*foobar)(), unsigned long N >
void call()
{
for( unsigned long i = 0; i < N; ++i )
{
std::string const s = foobar();
}
}
template< std::string (*foobar)() >
void test( std::string const& functionName )
{
static unsigned long const nCalls = 100000;
std::clock_t const clockStart = std::clock();
call<foobar, nCalls>();
std::clock_t const clockFinish = std::clock();
double const secondsElapsed =
static_cast<double>( clockFinish - clockStart )/CLOCKS_PER_SEC;
std::cout << std::endl;
std::cout << foobar() << std::endl;
std::cout
<< std::setw( 20 ) << functionName << ": "
<< secondsElapsed << " seconds elapsed"
<< std::endl;
}
int main()
{
test
test<foobar2>( "foobar2" );
test<foobar3>( "foobar3" );
test<foobar4>( "foobar4" );
}
===================================================================
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Stefan Rupp
Guest
|
| Posted: Tue Feb 03, 2004 11:16 am Post subject: Re: string::operator+ vs. string::operator+= vs. ostringstre |
|
|
Good evening,
Alf P. Steinbach schrieb:
That sounds Norwegian? What does it mean?
| Quote: | std::string s( a );
...
s += q;
s += r;
s += s;
Oops.
Thanks to Thore Karlsen for noticing that bug, I didn't...
|
Ouch! Neither did I (apparently). That's the cost of minimising a
problem description.
Anyway, the basic outcome does not change when correcting that bug. The
times stay the same (more or less).
| Quote: | I added a foobar4 to have some basis for comparing the overhead.
|
Well, ... see below!
| Quote: | Here are my results for 100.000 calls
[...]
Release (VC 7.1, 1.8 GHz single processor Dell PC)
abcdefghijklmnopqrstuvwxyz
foobar1: 0.531 seconds elapsed
abcdefghijklmnopqrstuvwxyz
foobar2: 0.359 seconds elapsed
abcdefghijklmnopqrstuvvxyz
foobar3: 1.688 seconds elapsed
abcdefghijklmnopqrstuvwxyz
foobar4: 0.219 seconds elapsed
|
Here as well, the string::operator+= variant is quicker than the
stringstream variant. But is seems to be quite clear that in your
example the string::operator+ is outperformed by both of the other
variants (which is what anybody would expect).
| Quote: | static std::string const * const ps[] =
{
&a, &b, &c, &d, &e, &f, &g, &h, &i, &j, &k, &l, &m, &n, &o, &p, &q,
&r, &s, &t, &u, &v, &w, &x, &y, &z
};
template< typename T, std::size_t N > std::size_t size( T(&)[N] ){ return N; }
std::string foobar4()
{
std::size_t bufferSize = 0;
for( std::size_t i = 0; i < size( ps ); ++i )
{
bufferSize += ps[i]->length();
}
std::vector<char> buffer( bufferSize );
std::size_t endIndex = 0;
for( std::size_t i = 0; i < size( ps ); ++i )
{
std::copy( ps[i]->begin(), ps[i]->end(), &buffer[endIndex] );
endIndex += ps[i]->length();
}
return foo( std::string( &buffer[0], bufferSize ) );
}
|
Here, you are doing quite a lot of the work I'd expect of a compiler by
your own. This has certainly advantages. It may be something like a
lower bound to what we may expect by a more generalised form of string
processing, but it is not an approach which will be used in a real world
application (and even in this case your Degug example showed that it may
be outperformed by different implementations under certain circumstances).
By the way, you've mentioned earlier
| Quote: | note the anomalous result for
VC debug, where std::stringstream, in foobar2(), is _fastest_
|
But foobar2 is the string::operator+= variant, not the one with the
stringstream.
So, after all, the stringstream variant may be a nice solution for
textbooks and an example for type safety when terms of different
datatypes are involved, but when concatenating strings, nothing performs
better than operator::string+=, if I don't want to do the work by myself
(like shown in your foobar4), right?
Regards,
Stefan
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Samuel Krempp
Guest
|
| Posted: Thu Feb 05, 2004 11:29 am Post subject: Re: string::operator+ vs. string::operator+= vs. ostringstre |
|
|
le Tuesday 03 February 2004 12:16, [email]st.rupp (AT) t-online (DOT) de[/email] écrivit :
| Quote: | Anyway, the basic outcome does not change when correcting that bug. The
times stay the same (more or less).
|
I have the same result with g++-3.3, even in release :
marvin% ./bench_appends.exe
abcdefghijklmnopqrstuvwxyz
foobar1: 0.75 seconds elapsed
abcdefghijklmnopqrstuvwxyz
foobar2: 1.54 seconds elapsed
abcdefghijklmnopqrstuvvxyz
foobar3: 2.04 seconds elapsed
abcdefghijklmnopqrstuvwxyz
foobar4: 0.34 seconds elapsed
It seems the dynamic growth in the string's operator+= is not tuned for
speeding small additions.
add result.reserve(30); before the appendings, and the time becomes :
abcdefghijklmnopqrstuvwxyz
foobar2: 0.57 seconds elapsed
(and 0.61s in debug, which is then the fastest).
So it's only an issue with the dynamic growth scheme. Usual implementations
allocate a minimum of several hundred bytes or so at the first occasion,
and g++-3.3 apparently chose not to.
that may just be a desired behaviour, in order to avoid wasting 500% or more
space in the case of handling millions of small strings..
As long as you can reserve an initial estimate majoration of the final size
it does give more polyvalence to the user, but to call reserve in the case
where speed on small strings is the matter, she'd need to be aware of
that..
Anyway, I suppose this growth scheme is at most 2x slower than 1 allocation,
in the worst case, so I think this design makes sense.
--
Samuel.Krempp
cout << "@" << "crans." << (is_spam ? "trucs.en.trop." : "" )
<< "ens-cachan.fr" << endl;
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Stefan Rupp
Guest
|
| Posted: Tue Feb 24, 2004 7:32 pm Post subject: Re: string::operator+ vs. string::operator+= vs. ostringstre |
|
|
Good afternoon,
I'm picking up this discussion from the beginning of the month to follow
up a question.
Samuel Krempp schrieb:
| Quote: | As long as you can reserve an initial estimate majoration of the final size
it does give more polyvalence to the user, but to call reserve in the case
where speed on small strings is the matter, she'd need to be aware of
that..
|
The call to string::reserve here certainly does the trick to reduce the
number of system calls and speed things up. Unfortunately this isn't
possible for the stringstream solution, since stringbuf, the
stringstream's streambuf, does not provide such a reserve facility.
std::ostringstream oss;
oss.rdbuf().reserve( 10000 ); // no such thing
There is, however a stringstream c'tor with a string argument. Is it
possible to use this as a way to initially reserve a certain amount of
memory for the stringstream's streambuf?
std::string str;
str.reserve( 10000 );
std::ostringstream oss( str );
Is that possible? Will the size of oss.rdbuf() automatically grow once
the initially reserved 10000 characters are exceeded?
Regards,
Stefan
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carl Barron
Guest
|
| Posted: Wed Feb 25, 2004 3:14 pm Post subject: Re: string::operator+ vs. string::operator+= vs. ostringstre |
|
|
In article <c1g2nr$fao$06$1 (AT) news (DOT) t-online.com>, Stefan Rupp
<st.rupp (AT) t-online (DOT) de> wrote:
| Quote: | There is, however a stringstream c'tor with a string argument. Is it
possible to use this as a way to initially reserve a certain amount of
memory for the stringstream's streambuf?
std::string str;
str.reserve( 10000 );
std::ostringstream oss( str );
Is that possible? Will the size of oss.rdbuf() automatically grow once
the initially reserved 10000 characters are exceeded?
The string might not be changed but the buffer area willl grow as |
needed. [minor point but the buffer area of a stringbuf is not
necessarily a string. In fact std::string is not required to be
contiguous as the buffer area is....
The bottom line is the buffer will ezpand of needed and possible...
I would iss.seekg(0) to be sure I started writing at the beginning of
the buffer.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze@gabi-soft.fr
Guest
|
| Posted: Fri Feb 27, 2004 2:34 pm Post subject: Re: string::operator+ vs. string::operator+= vs. ostringstre |
|
|
Stefan Rupp <st.rupp (AT) t-online (DOT) de> wrote
| Quote: | Samuel Krempp schrieb:
As long as you can reserve an initial estimate majoration of the
final size it does give more polyvalence to the user, but to call
reserve in the case where speed on small strings is the matter,
she'd need to be aware of that..
The call to string::reserve here certainly does the trick to reduce
the number of system calls and speed things up. Unfortunately this
isn't possible for the stringstream solution, since stringbuf, the
stringstream's streambuf, does not provide such a reserve facility.
std::ostringstream oss;
oss.rdbuf().reserve( 10000 ); // no such thing
There is, however a stringstream c'tor with a string argument. Is it
possible to use this as a way to initially reserve a certain amount of
memory for the stringstream's streambuf?
|
No.
| Quote: | std::string str;
str.reserve( 10000 );
std::ostringstream oss( str );
Is that possible?
|
Sure. But it (probably) won't have any effect on oss. For obvious
reasons, oss uses a copy of the string passed into it, and copying
doesn't necessarily copy capacity. (Some trials with the older
compilers at my disposition -- and a recent version of g++, gave some
really strange results. I suspect that this is a side effect of all of
the implementations using the now discredited COW algorithm.)
| Quote: | Will the size of oss.rdbuf() automatically grow once the initially
reserved 10000 characters are exceeded?
|
I have no idea; it's not something I've ever needed. But in general, if
you want some very specific behavior from a streambuf, the easiest and
surest solution is to write your own (although I'll admit that adding a
capacity function to stringbuf and the streams that use it sounds like a
good idea.)
--
James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
