FastString now beats all the other std::strings on all benchmarks
Peter Olcott
Followups that attack the assertions without data will be ruled off-
topic. Please stick to C++ content on followups. Thanks! -mod/hps}
FastString now Consistently Beats MSVC++ 6.0,
Borland C++ Builder 4.0, and STLport 4.51 on
Three Types of Benchmarks:
(1) Data Movement
(2) Construction from Data
(3) Memory Allocation
It is expected that FastString will beat every
other implementation of std::string, because
of numerous platforms the toughest one to beat
was STLport, and FastString now consistently
beats STLport on every benchmark, including
those that it lost before.
http://home.att.net/~olcott/fast.html
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Ernest Friedman-Hill
>
> It is expected that FastString will beat every
Mark Twain said "There are three kinds of falsehoods: lies,
damn lies, and statistics." That said, in the spirit of Peter's
benchmarks, I modified test 7 to create a new test 70, which also
tests performance on repeated "ASCIIZ" concatenation. The difference is
that this test tries different length ASCIIZ strings, not just the one-char
and 4-char ones Peter had tried. The test and results follow (I ran this
on stock gcc 2.95.2 on Linux.) What the results show is that for short
strings (less than 16 bytes) FastString is indeed faster. For longer ones,
gcc's old bastring (based on a draft standard) beats it by a factors
as much as three (and clearly for longer ASCIIZ's, by even more.)
What this demonstrates is that FastString does NOT "outperform all std::string
implementations." What it does is outperform many or most std::string
implementations on a very proscribed set of tasks, while underperforming on
others.
What I want Peter to realize and admit is that there simply isn't a single
best implementation of ANY library class for all purposes. Different
implementations make different tradeoffs. FastString is highly optimized for
concatenation of short strings, which is apparently important to Peter, and
that's fine. FastString will underperform on lots of other benchmarks,
including oncatenation of LONG strings.
-----------------------------------------------------------
void Test70() {
std::string data;
const char * asciiz;
std::string AA;
FastString A;
time_t BEGIN, END;
double Increase, stdstring_time, faststring_time;
int N, M;
for (int i=0; i<20; ++i) {
asciiz = data.c_str();
BEGIN = clock();
for (N = 1; N <= 8000; N++) {
AA = asciiz;
for (M = 1; M <= 100; M++)
AA += asciiz;
}
END = clock();
stdstring_time = (END - BEGIN) / 8;
printf("Repeated Concatenation of a %d byte long ASCIIZ string\n",
strlen(asciiz));
BEGIN = clock();
for (N = 1; N <= 8000; N++) {
A = asciiz;
for (M = 1; M <= 100; M++)
A += asciiz;
}
END = clock();
faststring_time = (END - BEGIN) / 8;
Increase = stdstring_time / faststring_time;
printf("FastString was %3.2f Fold Faster than std::string\n\n", Increase);
data += "data";
}
}
-------------------------------------------
Repeated Concatenation of a 0 byte long ASCIIZ string
FastString was 4.50 Fold Faster than std::string
Repeated Concatenation of a 4 byte long ASCIIZ string
FastString was 1.78 Fold Faster than std::string
Repeated Concatenation of a 8 byte long ASCIIZ string
FastString was 1.35 Fold Faster than std::string
Repeated Concatenation of a 12 byte long ASCIIZ string
FastString was 1.09 Fold Faster than std::string
Repeated Concatenation of a 16 byte long ASCIIZ string
FastString was 0.89 Fold Faster than std::string
Repeated Concatenation of a 20 byte long ASCIIZ string
FastString was 0.74 Fold Faster than std::string
Repeated Concatenation of a 24 byte long ASCIIZ string
FastString was 0.72 Fold Faster than std::string
Repeated Concatenation of a 28 byte long ASCIIZ string
FastString was 0.62 Fold Faster than std::string
Repeated Concatenation of a 32 byte long ASCIIZ string
FastString was 0.54 Fold Faster than std::string
Repeated Concatenation of a 36 byte long ASCIIZ string
FastString was 0.49 Fold Faster than std::string
Repeated Concatenation of a 40 byte long ASCIIZ string
FastString was 0.45 Fold Faster than std::string
Repeated Concatenation of a 44 byte long ASCIIZ string
FastString was 0.45 Fold Faster than std::string
Repeated Concatenation of a 48 byte long ASCIIZ string
FastString was 0.44 Fold Faster than std::string
Repeated Concatenation of a 52 byte long ASCIIZ string
FastString was 0.44 Fold Faster than std::string
Repeated Concatenation of a 56 byte long ASCIIZ string
FastString was 0.42 Fold Faster than std::string
Repeated Concatenation of a 60 byte long ASCIIZ string
FastString was 0.41 Fold Faster than std::string
Repeated Concatenation of a 64 byte long ASCIIZ string
FastString was 0.36 Fold Faster than std::string
Repeated Concatenation of a 68 byte long ASCIIZ string
FastString was 0.35 Fold Faster than std::string
Repeated Concatenation of a 72 byte long ASCIIZ string
FastString was 0.35 Fold Faster than std::string
Repeated Concatenation of a 76 byte long ASCIIZ string
FastString was 0.33 Fold Faster than std::string
---------------------------------------------------------
Ernest Friedman-Hill
Distributed Systems Research Phone: (925) 294-2154
Sandia National Labs FAX: (925) 294-2234
Org. 8920, MS 9012 ejf...@ca.sandia.gov
PO Box 969 http://herzberg.ca.sandia.gov
Livermore, CA 94550
Brian MacBride
"Peter Olcott" <olc...@worldnet.att.net> wrote in message
news:KR8%7.242783$WW.13100813@bgtnsc05-news.ops.worldnet.att.net...
> {Moderator's Note: This is on-topic, though potentially contentious.
> Followups that attack the assertions without data will be ruled off-
> topic. Please stick to C++ content on followups. Thanks! -mod/hps}
>
> FastString now Consistently Beats MSVC++ 6.0,
> Borland C++ Builder 4.0, and STLport 4.51 on
> Three Types of Benchmarks:
>
> (1) Data Movement
> (2) Construction from Data
> (3) Memory Allocation
>
> It is expected that FastString will beat every
> other implementation of std::string, because
> of numerous platforms the toughest one to beat
> was STLport, and FastString now consistently
> beats STLport on every benchmark, including
> those that it lost before.
>
> http://home.att.net/~olcott/fast.html
>
>
Consider...
// Bsically this is the provided
// faststring.cpp with the main
// 'int main () {}' removed.
// http://home.att.net/~olcott/FastString.cpp
// 2002-01-10 1:37 am
#include "faststring.hpp"
// FastString& assign(const FastString& Source, int pos, int n);
// basic_string& assign(const basic_string& s, size_type pos, size_type n)
template <class T>
void assign_test () {
T a ("12345");
T b ("ABCDE");
a.assign (b, 2, 2);
std::cout << a.c_str () << std::endl;
}
int main () {
std::cout << "std::string assign () test..." << std::endl;
assign_test <std::string> ();
std::cout << "FastString assign () test..." << std::endl;
assign_test <FastString> ();
return 0;
}
/*
std::string assign () test...
CD
FastString assign () test...
12345CD
*/
One of these implementations is clearly wrong. Which one??
Regards,
Brian
P.J. Plauger
news:KR8%7.242783$WW.13100813@bgtnsc05-news.ops.worldnet.att.net...
> FastString now Consistently Beats MSVC++ 6.0,
> Borland C++ Builder 4.0, and STLport 4.51 on
> Three Types of Benchmarks:
>
> (1) Data Movement
> (2) Construction from Data
> (3) Memory Allocation
>
> It is expected that FastString will beat every
> other implementation of std::string, because
> of numerous platforms the toughest one to beat
> was STLport, and FastString now consistently
> beats STLport on every benchmark, including
> those that it lost before.
Sigh. You just don't quit, do you? I've appended
below the results that I got for our latest library,
compiled with VC++ V6.0. Please note that it is
faster than ``FastString'' on two tests, even though
a) it does all required error checking
b) it deals with overlapped operands
c) it intentionally trades a certain amount of speed
for more economical use of memory
d) it is a complete, conforming implementation
etc. etc.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
----
Repeated Concatentation of a Single byte
FastString was 8.50 Fold Faster than std::string
Copy a 256 byte long string
FastString was 2.00 Fold Faster than std::string
Copy a 256 byte long string (alternative method)
FastString was 0.59 Fold Faster than std::string
Copy a 4 byte long string
FastString was 3.88 Fold Faster than std::string
Copy a 4 byte long string (alternative method)
FastString was 4.43 Fold Faster than std::string
Copy of a 64 byte long ASCIIZ string
FastString was 1.52 Fold Faster than std::string
Repeated Concatenation of a 4 byte long ASCIIZ string
FastString was 2.46 Fold Faster than std::string
Construction of a 4 Byte Long ASCIIZ String
FastString was 0.46 Fold Faster than std::string
Construction of a 32 Byte Long ASCIIZ String
FastString was 1.39 Fold Faster than std::string
Construction of a 64 Byte Long ASCIIZ String
FastString was 1.32 Fold Faster than std::string
Construction of a 256 Byte Long ASCIIZ String
FastString was 1.16 Fold Faster than std::string
Peter Olcott
"Ernest Friedman-Hill" <ejf...@alum.mit.edu> wrote in message
news:3C3DB4AF...@alum.mit.edu...
> Peter Olcott wrote:
> >
> > It is expected that FastString will beat every
> > other implementation of std::string...
>
> Mark Twain said "There are three kinds of falsehoods: lies,
> damn lies, and statistics." That said, in the spirit of Peter's
> benchmarks, I modified test 7 to create a new test 70, which also
> tests performance on repeated "ASCIIZ" concatenation. The difference is
> that this test tries different length ASCIIZ strings, not just the one-char
> and 4-char ones Peter had tried. The test and results follow (I ran this
> on stock gcc 2.95.2 on Linux.) What the results show is that for short
> strings (less than 16 bytes) FastString is indeed faster. For longer ones,
> gcc's old bastring (based on a draft standard) beats it by a factors
> as much as three (and clearly for longer ASCIIZ's, by even more.)
>
> What this demonstrates is that FastString does NOT "outperform all
std::string
> implementations." What it does is outperform many or most std::string
> implementations on a very proscribed set of tasks, while underperforming on
> others.
I just reposted another re-write this time there are
a total of 45 different benchmarks. I win on most
of them. On the ones where I lose, its only by a
small amount.
http://home.att.net/~olcott/fast.html
Peter Olcott
"Brian MacBride" <macb...@ix.netcom.com> wrote in message
news:a1kc8r$r6hr8$1...@ID-26770.news.dfncis.de...
>
> "Peter Olcott" <olc...@worldnet.att.net> wrote in message
> news:KR8%7.242783$WW.13100813@bgtnsc05-news.ops.worldnet.att.net...
> > {Moderator's Note: This is on-topic, though potentially contentious.
> > Followups that attack the assertions without data will be ruled off-
> > topic. Please stick to C++ content on followups. Thanks! -mod/hps}
> >
> > FastString now Consistently Beats MSVC++ 6.0,
> > Borland C++ Builder 4.0, and STLport 4.51 on
> > Three Types of Benchmarks:
> >
> > (1) Data Movement
> > (2) Construction from Data
> > (3) Memory Allocation
> >
> > It is expected that FastString will beat every
> > other implementation of std::string, because
> > of numerous platforms the toughest one to beat
> > was STLport, and FastString now consistently
> > beats STLport on every benchmark, including
> > those that it lost before.
> >
> > http://home.att.net/~olcott/fast.html
> >
> >
a total of 45 different benchmarks. I win on most
of them. On the ones where I lose, its only by a
small amount.
My attempt on assign() was to create substr().
The problem is that substr() is not really a
SubString.
Attila Feher
>
> Peter Olcott wrote:
> >
> > It is expected that FastString will beat every
> > other implementation of std::string...
>
> Mark Twain said "There are three kinds of falsehoods: lies,
> damn lies, and statistics." That said, in the spirit of Peter's
> benchmarks, I modified test 7 to create a new test 70, which also
This was the quote I was looking for, when I have answered this same
claim of Peter in comp.lang.c++
[SNIP]
> What I want Peter to realize and admit is that there simply isn't a single
> best implementation of ANY library class for all purposes.
I doubt that it will ever happen. I also have pointed out _several_
(for me) serious issues with this thing called FastString, even here. I
have never ever got an answer for those. Like the lack of standard
template parameters (allocator, traits), the class being premature
optimized for 32bit platforms, in the early versions I have found
serious exception safety problems... He does not seem to care much
about those comments.
> Different implementations make different tradeoffs.
And here it comes to mind, that someone else, namely Andrei Alexandrescu
has already created a policy based string implementation, which (with a
little work) could support this kind of narrow-sighted premature
optimization. Narrow-sigthed is not meant as an offense, but as a point
that something optimized for concatenating short strings efficiently and
_only_ on 32bit platforms (preferably real 32bit, not emulation on 64
bit, which would look _exaclty_ like 32bit for the C++ compiler, so even
ifdefs would not help), no support for traits and allocators is not to
be called a generic solution.
I have seen the first version of FastString and I decided for myself,
that it is not worth of my attention. (Probably because I have seen
Andrei's approach?). The only reason I "open my mouth" again and again,
because I feel that people _may_ get cheated into thinking that this
class is _the_best_ string implementation if they only see Peter's
"marketing" messages, but not the other side of the coin.
I believe that the idea of creating such a string may help few very much
in special cases, I doubt that showing up this kind of limited solution
with premature optimization for a very special use should be advertised,
treated or accepted as a generic "better than all other" strign
implementation.
Attila
Brian MacBride
"Attila Feher" <Attila...@lmf.ericsson.se> wrote in message
news:3C3EEBC4...@lmf.ericsson.se...
>
> [SNIP]
>
> I have seen the first version of FastString and I decided for myself,
> that it is not worth of my attention. (Probably because I have seen
> Andrei's approach?). The only reason I "open my mouth" again and again,
> because I feel that people _may_ get cheated into thinking that this
> class is _the_best_ string implementation if they only see Peter's
> "marketing" messages, but not the other side of the coin.
>
Let me help you there.
// Basically this is the provided
// faststring.cpp with the main
// 'int main () {}' removed.
// http://home.att.net/~olcott/FastString.cpp
// 2002-01-11 5:00 pm
#include "faststring.hpp"
// FastString& operator=(const FastString &Source);
// basic_string& operator=(const basic_string& s);
template <class T>
void assign_test () {
T a ("12345");
T b ("ABCDEFGHIJK");
a = b;
std::cout << a.c_str () << std::endl;
}
int main () {
std::cout << "std::string assign () test..." << std::endl;
assign_test <std::string> ();
std::cout << "FastString assign () test..." << std::endl;
assign_test <FastString> ();
return 0;
}
/*
std::string assign () test...
ABCDEFGHIJK
FastString assign () test...
=Ą345?ĄŚ
*/
No danger of anybody mistaking 'FastString' as a viable product.
Regards,
Brian
Sebastian Kapfer
news.ops.worldnet.att.net>, Peter Olcott writes...
|
| It is expected that FastString will beat every
| other implementation of std::string, because
Sorry, a bit long :)
The question is, who expects that. A whole bunch of C++ experts
disagrees with you. I've been reading this group for quite a while, and
most things they said turned out to be true. Obviously, learning new
things is not your main concern.
Your benchmarks seem to stress monster strings for some reason that
escapes me. I have looked through a toy application that I wrote a week
ago. It is not heavily dependent on string operations, and it contained
mostly two sorts of operations:
- calls to the copy constructor because strings were returned by value
(think of that what you want)
- the construction of "message strings" for the user interface, log
files, exception messages etc. via operator+
All involved strings were fairly short (most from 10-60 chars) and very
few op+ calls. This is exactly what I would have expected from a
"typical application". Any string-intensive application wouldn't use a
generic std::string/FastString class anyway.
Now I decided to cook up my own (incomplete) benchmark, built on the
results above. The results were
a) Your string is still missing an operator+. Well, this one could
probably be added quickly, but it is still inconvenient.
b) The operator=(const FastString &) is completely bogus. It does copy
string length and allocation size; but it fails to copy the string
data under some circumstances. Optimizing a function that does
nothing useful is fairly easy...
However, here is my benchmark:
const char *test_lit4 = "<-- STRING STRING STRING STRING -->";
const char *test_lit1 = "<-- STRING -->";
template<typename STRING>
class tests
{
public:
static void printname(const FastString &) {
printf("FastString\n"); }
static void printname(const std::string &) {
printf("std::string\n"); }
static void concat_bench()
{
printname(STRING());
clock_t t_begin, t_end;
t_begin = clock();
for(int i = 0; i != 1000; ++i)
for(int j = 0; j != 1000; ++j)
{
STRING tmp = test_lit1;
tmp += test_lit4;
tmp += test_lit1;
tmp.c_str();
}
t_end = clock();
int ms = (t_end - t_begin) * 1000 / CLOCKS_PER_SEC;
printf("%i ms\n", ms);
}
static void copyctor_bench()
{
STRING X = test_lit1;
printname(X);
clock_t t_begin, t_end;
t_begin = clock();
for(int i = 0; i != 1000; ++i)
for(int j = 0; j != 1000; ++j)
{
STRING tmp(X);
}
t_end = clock();
int ms = (t_end - t_begin) * 1000 / CLOCKS_PER_SEC;
printf("%i ms\n", ms);
}
static void assign_test()
{
STRING X;
printname(X);
X = STRING(test_lit1);
const char *Xcstr = X.c_str();
printf("%s\n", Xcstr);
if( strcmp(Xcstr, test_lit1) != 0 )
printf("assign failed.\n");
else
printf("assign succeeded.\n");
}
};
int main()
{
printf("\nassignment operator test\n");
tests<std::string>::assign_test();
tests<FastString>::assign_test();
printf("\nconcat benchmark\n");
tests<std::string>::concat_bench();
tests<FastString>::concat_bench();
printf("\ncopyctor benchmark\n");
tests<std::string>::copyctor_bench();
tests<FastString>::copyctor_bench();
return 0;
}
And finally, the results I got...
concat benchmark
std::string
1810 ms
FastString
2580 ms
copyctor benchmark
std::string
330 ms
FastString
500 ms
Peter Olcott
> (for me) serious issues with this thing called FastString, even here. I
> have never ever got an answer for those. Like the lack of standard
> template parameters (allocator, traits), the class being premature
> optimized for 32bit platforms, in the early versions I have found
> serious exception safety problems... He does not seem to care much
> about those comments.
It now meets the string guarantee of exception safety. It also provides
at least as strong a thread safety guarantee as SGI STL. The 32-bit
code was changed to sizeof(int) quite a while ago, and has since
been discarded. Although I might not seem to care about the
comments that I have been receiving, I have just incorporated
the last comment, thus every specific thing has now been added.
It a little hard to have template parameters without using a
template, but I will look into this.
> I have seen the first version of FastString and I decided for myself,
> that it is not worth of my attention. (Probably because I have seen
It has been dramatically updated with just about every single
suggestion that was provided. Its a whole different set of code
now, from when you first looked at it. Since this was the very
first class that I ever wrote in my entire life, it was not nearly
up to the current quality, when you last saw it.
> Andrei's approach?). The only reason I "open my mouth" again and again,
> because I feel that people _may_ get cheated into thinking that this
> class is _the_best_ string implementation if they only see Peter's
> "marketing" messages, but not the other side of the coin.
>
> I believe that the idea of creating such a string may help few very much
> in special cases, I doubt that showing up this kind of limited solution
> with premature optimization for a very special use should be advertised,
> treated or accepted as a generic "better than all other" strign
> implementation.
It has approached my goals as a project. I will look into
the template parameters, and I think I will be done
after this. The benchmarks have been updated to
include a much more comprehensive set. Its now
faster than the others, especially if it must do all the
memory allocation.
Ernest Friedman-Hill
>
> "Ernest Friedman-Hill" <ejf...@alum.mit.edu> wrote in message
> news:3C3DB4AF...@alum.mit.edu...
> >
> std::string
> > implementations." What it does is outperform many or most std::string
> > implementations on a very proscribed set of tasks, while underperforming
on
> > others.
>
> I just reposted another re-write this time there are
> a total of 45 different benchmarks. I win on most
> of them. On the ones where I lose, its only by a
> small amount.
>
Yes, Peter, but here I posted a simple benchmark, right in line with the
others you've posted, on which FastString can -lose- by a factor of 3,
and it's a string concatenation benchmark -- i.e, the task
FastString is supposed to be good at. I just don't see how coming up
with -more- benchmarks changes this.
---------------------------------------------------------
Ernest Friedman-Hill
Distributed Systems Research Phone: (925) 294-2154
Sandia National Labs FAX: (925) 294-2234
Org. 8920, MS 9012 ejf...@ca.sandia.gov
PO Box 969 http://herzberg.ca.sandia.gov
Livermore, CA 94550
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Peter Olcott
I am slow at. I specifically chose to be slow at this ill-formed
approach so that I could be faster on the proper way to
provide this same functionality.
Normally people would not use self reference via the c_str()
interface, they would use self-reference through the inherently
faster string interface, (by using the c_str() interface you
necessarily force a recalculation of the length, yet you already
have the length, so this way is the wrong way) thus this benchmark
is intentionally biased against my code specifically. If this
benchmark is re-written, providing the reasonable way to
achieve this same result, then I win again. Try this same test
with A += A;
Ernest Friedman-Hill
> Normally people would not use self reference via the c_str()
> interface, they would use self-reference through the inherently
> faster string interface, (by using the c_str() interface you
> necessarily force a recalculation of the length, yet you already
> have the length, so this way is the wrong way) thus this benchmark
> is intentionally biased against my code specifically. If this
> benchmark is re-written, providing the reasonable way to
> achieve this same result, then I win again. Try this same test
> with A += A;
>
No offense, but what on earth does this paragraph mean? There isn't a
single call to FastString.c_str() anywhere in this routine -- just
lots of calls to FastString += "zero-terminated char array." I
thought, in fact, contrary to the assertion above, that this was the
one thing you intended FastString to be fast at!
Anyway, calls to A += A, while they must be accounted for, are
generally fairly rare, wouldn't they be? As a result, what you
recommend wouldn't be a very interesting benchmark, in any case. Calls
to A += (something else) are far more interesting.
--
---------------------------------------------------------
Ernest Friedman-Hill
Distributed Systems Research Phone: (925) 294-2154
Sandia National Labs FAX: (925) 294-2234
Org. 8920, MS 9012 ejf...@ca.sandia.gov
PO Box 969 http://herzberg.ca.sandia.gov
Livermore, CA 94550
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]