STL speed

[Peter Koch Larsen]

Re: STL speed


"Przemo Drochomirecki" <pedrosch@gazet a.pl> skrev i en meddelelse
news:btkn1f$d4h $1@nemesis.news .tpi.pl...[color=blue]
> Hi,
> The task was indeed simple. Read 2.000.000 words (average length = 9),[/color]
sort[color=blue]
> them and write it to new file.
> I've made this in STL, and it was almost 17 times slower than my previous
> "clear-C-code".
> I used <vector>, <algorithm>, <iostream> and <algorithm>. Is STL really so
> slow?
>
> Thx in adv.
> Przemo
>
> p.s. i know that STL uses IntrospectiveSo rt which seems to be good choice,[/color]
i[color=blue]
> suppose that INPUT (cin) is extremaly slow,
> and <vector> as a dynamic structure also isn't to fast... any ideas?
>
>[/color]

Hi Przemo

Some general comments. First it seems that the Microsoft
stream-implementation is not very good. The penalty of using streams
compared to C file I/O is significant in your example - giving (if i
remember correctly) a factor of four in performance. For GCC streams should
have the same performance as C file I/O.
Secondly, when compiling C++ optimization is far more important than in C.
So if you do not optimize your program you can be quite certain it will be
slow - a factor of say 5 or 17 should not be surprising at all.
Thirdly, your implementation is sub-optimal as pointed out by others.
With VC++ 6.0 (which from an optimization point of view isnt that bad), the
performance of <vector> should be comparable to the C-way of doing things -
and your sort should be much faster.

Kind regards
Peter

[Christoph Rabel]

Re: STL speed

Peter Koch Larsen wrote:[color=blue]
> "Przemo Drochomirecki" <pedrosch@gazet a.pl> skrev i en meddelelse
> news:btkn1f$d4h $1@nemesis.news .tpi.pl...
>
> Some general comments. First it seems that the Microsoft
> stream-implementation is not very good. The penalty of using streams
> compared to C file I/O is significant in your example - giving (if i
> remember correctly) a factor of four in performance. For GCC streams should
> have the same performance as C file I/O.[/color]

They are very slow too :-( At least a year ago it was so.

I did a profiling for write operations with gcc 3.2 and was
surprised that it was 8:1 but I cant remember the exact
value. But it was high!

c u

Christoph

[P.J. Plauger]

Re: STL speed

"David White" <no@email.provi ded> wrote in message
news:wxlLb.6832 $xm.321720@nasa l.pacific.net.a u...
[color=blue][color=green]
> > p.s. i know that STL uses IntrospectiveSo rt which seems to be good[/color][/color]
choice,[color=blue]
> i[color=green]
> > suppose that INPUT (cin) is extremaly slow,
> > and <vector> as a dynamic structure also isn't to fast... any ideas?[/color]
>
> I doubt that it's inherently slow. It depends on the implementation. I
> remember tracing through the stream output on an MS compiler and[/color]
discovered[color=blue]
> that it fabricated a format string and called sprintf! Fifty billion[/color]
dollars[color=blue]
> in the bank, but they chose the cheapest, nastiest implementation[/color]
possible.

Well, I didn't have access to any of that $50B when I wrote that code
in 1993, but I did write significant chunks of the C and C++ Standards
in those areas. I knew that printf gets right all sorts of subtle
corner cases that practically every iostreams implementation botched
one way or the other. I also had mineral rights to all the code I needed
to do the job other than `cheap and nasty,' and I was unable to get any
significant improvement over fabricating a format string and calling
sprintf.

FWIW, Microsoft's stash has roughly doubled since the day they chose to
adopt our cheap and nasty approach. Coincidence? (Probably.)

P.J. Plauger
Dinkumware, Ltd.

http://www.dinkumware.com

[P.J. Plauger]

Re: STL speed

"Peter Koch Larsen" <pkl@mailme.d k> wrote in message
news:3ffe79c9$0 $9827$edfadb0f@ dread14.news.te le.dk...
[color=blue]
> Some general comments. First it seems that the Microsoft
> stream-implementation is not very good. The penalty of using streams
> compared to C file I/O is significant in your example - giving (if i
> remember correctly) a factor of four in performance. For GCC streams[/color]
should[color=blue]
> have the same performance as C file I/O.[/color]

Uh, there was a recent thread that showed neither of these factoids
to be all that true.
[color=blue]
> Secondly, when compiling C++ optimization is far more important than in C.
> So if you do not optimize your program you can be quite certain it will be
> slow - a factor of say 5 or 17 should not be surprising at all.[/color]

That I agree with.
[color=blue]
> Thirdly, your implementation is sub-optimal as pointed out by others.
> With VC++ 6.0 (which from an optimization point of view isnt that bad),[/color]
the[color=blue]
> performance of <vector> should be comparable to the C-way of doing[/color]
things -[color=blue]
> and your sort should be much faster.[/color]

Also agree.

P.J. Plauger
Dinkumware, Ltd.

http://www.dinkumware.com

[Donovan Rebbechi]

Re: STL speed

In article <rurLb.3349$qM1 .992@news-binary.blueyond er.co.uk>, Nick Hounsome wrote:
[color=blue][color=green]
>> Oh boy. Did you run them on different computers too ?
>>
>> Cheers,[/color]
>
> It may be simpler than that.[/color]

Yes, I'm almost certain it is. What I meant was that he's manipulated several
variables, including the ones he's interested in.
[color=blue]
> If the compiler does not inline the hundreds of
> small calls that this makes the performance WILL
> be slow on any platform.[/color]

Yes, as I said in my other post.

Cheers,
--
Donovan Rebbechi

http://pegasus.rutgers.edu/~elflord/

[Tõnu Aas]

Re: STL speed

> The task was indeed simple. Read 2.000.000 words (average length = 9),
sort[color=blue]
> them and write it to new file.[/color]

So, STL can reserve some space for each string.
+ string object overhead + vector object and you can have 512 bytes for each
word.
That is ~ 1GB for all you data !!! + program itselt & OS.
So you OS uses virtual memory, which is SLOOOOW.
STL is nice toy, but not for this kind of things.

Tõnu.

[EnTn]

Re: STL speed

I'm quite new to STL too...

but one thought was about the dynamic resizing of the vector as you
fill it.
AFAIK the vector will extend itself dynamically until it can no longer
remain a continuous allocation in memory, upon which is reallocates
itself in a new area of memory... (?)

Anyway, Can expensive allocations / deallocations / copies be avoided
by by using the reserve() member function to *try to* ensure that
there is enough contiginous space around your vector to avoid
reallocations.. ..?

MHTWEOTSH...



"Przemo Drochomirecki" <pedrosch@gazet a.pl> wrote in message news:<btkn1f$d4 h$1@nemesis.new s.tpi.pl>...[color=blue]
> Hi,
> The task was indeed simple. Read 2.000.000 words (average length = 9), sort
> them and write it to new file.
> I've made this in STL, and it was almost 17 times slower than my previous
> "clear-C-code".
> I used <vector>, <algorithm>, <iostream> and <algorithm>. Is STL really so
> slow?
>
> Thx in adv.
> Przemo
>
> p.s. i know that STL uses IntrospectiveSo rt which seems to be good choice, i
> suppose that INPUT (cin) is extremaly slow,
> and <vector> as a dynamic structure also isn't to fast... any ideas?[/color]

[Jeff Schwab]

Re: STL speed

Please don't top-post.

EnTn wrote:[color=blue]
> I'm quite new to STL too...
>
> but one thought was about the dynamic resizing of the vector as you
> fill it.
> AFAIK the vector will extend itself dynamically until it can no longer
> remain a continuous allocation in memory, upon which is reallocates
> itself in a new area of memory... (?)[/color]

That's the idea.
[color=blue]
> Anyway, Can expensive allocations / deallocations / copies be avoided
> by by using the reserve() member function to *try to* ensure that
> there is enough contiginous space around your vector to avoid
> reallocations.. ..?[/color]

Yes, that's the whole purpose of the "reserve" method.
[color=blue]
> MHTWEOTSH...[/color]

I give up. Is that a common greeting in some language I don't speak, or
does it stand for something?

[color=blue]
> "Przemo Drochomirecki" <pedrosch@gazet a.pl> wrote in message news:<btkn1f$d4 h$1@nemesis.new s.tpi.pl>...
>[color=green]
>>Hi,
>>The task was indeed simple. Read 2.000.000 words (average length = 9), sort
>>them and write it to new file.
>>I've made this in STL, and it was almost 17 times slower than my previous
>>"clear-C-code".
>>I used <vector>, <algorithm>, <iostream> and <algorithm>. Is STL really so
>>slow?
>>
>>Thx in adv.
>>Przemo
>>
>>p.s. i know that STL uses IntrospectiveSo rt which seems to be good choice, i
>>suppose that INPUT (cin) is extremaly slow,
>>and <vector> as a dynamic structure also isn't to fast... any ideas?[/color][/color]

[Sean Clarke]

Re: STL speed

tom_usenet wrote:
[color=blue]
> On Fri, 9 Jan 2004 04:07:02 -0800, "Przemo Drochomirecki"
> <pedrosch@gazet a.pl> wrote:
>[color=green]
>>
>>"E. Robert Tisdale" <E.Robert.Tisda le@jpl.nasa.gov > wrote in message
>>news:3FFE07DC .804@jpl.nasa.g ov...[color=darkred]
>>> Przemo Drochomirecki wrote:
>>>
>>> > The task was indeed simple.
>>> > Read 2.000.000 words (average length = 9),
>>> > sort them and write it to new file.
>>> > I've made this in STL,
>>> > and it was almost 17 times slower than my previous "clear-C-code".
>>> > I used <vector>, <algorithm>, <iostream> and <algorithm>.
>>> > Is STL really so slow?
>>>
>>> No. You just screwed up.
>>> Post both your C and C++ code
>>> so that we can see what you did wrong.
>>>[/color]
>>
>>---STL CODE---
>>
>>#include <string>
>>#include <conio.h>
>>#include <iostream>
>>#include <algorithm>
>>#include <vector>
>>
>>using namespace std;
>>struct wordstruct { string word; };[/color]
>
> Why have wordstruct? What's wrong with using string directly?
>[color=green]
>>
>>void read_names(vect or<wordstruct>& x)
>>{
>> wordstruct q;
>> while (true) {
>> cin >> q.word;
>> if (q.word == string("0"))
>> break;[/color]
>
> The above would be much more efficient as:
>
> if (q.word == "0")
>
> since that saves an extra memory allocation per iteration.[/color]

Are you sure here that the compiler would not just create a string("0") ?

Personally I would use a either a const static or pre constructed const
string, is this overkill?

class HowIWouldDoIt
{
private:
const static String _testString;
public:
read_names(std: :vector<wordstr uct>& x)
};

HowIWouldDoIt:: _testString = "0";

void read_names(vect or<wordstruct>& x)
{
wordstruct q;
while (true) {
cin >> q.word;
if (q.word == _testString )
break;

cont...


<snip>
[color=blue]
> Here you should add:
> std::ios::sync_ with_stdio(fals e);
> since buffering will be disabled on cin and cout on some
> implementations if you don't.[/color]

Interesting... I've not used this before.[color=blue]
>[color=green]
>> vector<wordstru ct> x;[/color]
>
> Here you might want to reserve some space in the vector:
> x.reserve(1000) ; //or more[/color]

I think this will probably be the crux of the problem, the other stuff I'd
consider "fine tuning", but worthwhile none the less.
[color=blue][color=green]
>> read_names(x);
>> sort(x.begin(), x.end(), wordc);
>> // vector x is sorted
>> return 0;
>>}[/color][/color]

Out of intestest, I wonder how this would perform using a set<> ? ie sorted
(operator<) on insert......

:-)

--
Regards

Sean Clarke
-------------------------------------------------
Linux.... for those whose IQ is greater than 98 !!

[Karl Heinz Buchegger]

Re: STL speed

EnTn wrote:[color=blue]
>
> Anyway, Can expensive allocations / deallocations / copies be avoided
> by by using the reserve() member function to *try to* ensure that
> there is enough contiginous space around your vector to avoid
> reallocations.. ..?[/color]

That's the whole idea of reserve.

Another possibility for the OP would be to change strategie. He could
try to use a std::map instead of the vector. I did this once when
toying around (counting and sorting the words of the bible) and achieved
a noticable speedup.

--
Karl Heinz Buchegger
kbuchegg@gascad .at

[Martijn Lievaart]

Re: STL speed

On Fri, 09 Jan 2004 05:30:01 -0800, EnTn wrote:
[color=blue]
> Anyway, Can expensive allocations / deallocations / copies be avoided
> by by using the reserve() member function to *try to* ensure that
> there is enough contiginous space around your vector to avoid
> reallocations.. ..?[/color]

As long as you interpret *try to* as *throws an exception when out of
memory*, yes. A vectors contents is always contiginous.

HTH,
M4

[Martijn Lievaart]

Re: STL speed

On Fri, 09 Jan 2004 15:10:30 +0200, Tõnu Aas wrote:
[color=blue][color=green]
>> The task was indeed simple. Read 2.000.000 words (average length = 9),[/color]
> sort[color=green]
>> them and write it to new file.[/color]
>
> So, STL can reserve some space for each string.
> + string object overhead + vector object and you can have 512 bytes for each
> word.
> That is ~ 1GB for all you data !!! + program itselt & OS.
> So you OS uses virtual memory, which is SLOOOOW.
> STL is nice toy, but not for this kind of things.[/color]

No. This is an algorithmic issue. You can do the same in C which will be
equally slow, or you can choose another algortihm.

This case is one where the overhead of the STL (if any) completely
disapears.

HTH,
M4

[tom_usenet]

Re: STL speed

On Fri, 09 Jan 2004 14:47:31 +0000, Sean Clarke
<sean.clarke@ no-spam.sec-consulting.co.u k> wrote:
[color=blue][color=green]
>> The above would be much more efficient as:
>>
>> if (q.word == "0")
>>
>> since that saves an extra memory allocation per iteration.[/color]
>
>Are you sure here that the compiler would not just create a string("0") ?[/color]

Well, its a QOI issue (operator== can make as many allocations as it
likes), but there is a
template<class charT, class traits, class Allocator>
bool operator==(cons t basic_string<ch arT,traits,Allo cator>& lhs, const
charT* rhs);

An implementation would have to be amazingly stupid to just forward
the call to the 2 string version, triggering an unnecessary string
construction.
[color=blue]
>Personally I would use a either a const static or pre constructed const
>string, is this overkill?[/color]

A pre-constructed one is a better solution - in theory the comparison
can be slightly faster.[color=blue]
>
>class HowIWouldDoIt
>{
>private:
> const static String _testString;
>public:
> read_names(std: :vector<wordstr uct>& x)
>};
>
>HowIWouldDoIt: :_testString = "0";
>
>void read_names(vect or<wordstruct>& x)
>{
> wordstruct q;
> while (true) {
> cin >> q.word;
> if (q.word == _testString )
> break;[/color]

How about just:

wordstruct q;
std::string const testString("0") ;
while (true) {
cin >> q.word;
if (q.word == testString)
break;
[color=blue][color=green][color=darkred]
>>> vector<wordstru ct> x;[/color]
>>
>> Here you might want to reserve some space in the vector:
>> x.reserve(1000) ; //or more[/color]
>
>I think this will probably be the crux of the problem, the other stuff I'd
>consider "fine tuning", but worthwhile none the less.[/color]

vector::reserve is useful, but because of the exponential growth
behaviour of vector, it only tends to make a small difference. If you
don't pre-allocate, you typically only construct twice as many
objects. With a reference counted string (rare these days) the gain
will be even smaller.
[color=blue]
>[color=green][color=darkred]
>>> read_names(x);
>>> sort(x.begin(), x.end(), wordc);
>>> // vector x is sorted
>>> return 0;
>>>}[/color][/color]
>
>Out of intestest, I wonder how this would perform using a set<> ? ie sorted
>(operator<) on insert......[/color]

Probably quite a bit worse. The O complexity will be the same, but the
constant is likely to be bigger.

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html

[David White]

Re: STL speed

"P.J. Plauger" <pjp@dinkumware .com> wrote in message
news:0%wLb.1087 $Mt4.283@nwrddc 03.gnilink.net. ..[color=blue]
> "David White" <no@email.provi ded> wrote in message
> news:wxlLb.6832 $xm.321720@nasa l.pacific.net.a u...
>[color=green][color=darkred]
> > > p.s. i know that STL uses IntrospectiveSo rt which seems to be good[/color][/color]
> choice,[color=green]
> > i[color=darkred]
> > > suppose that INPUT (cin) is extremaly slow,
> > > and <vector> as a dynamic structure also isn't to fast... any ideas?[/color]
> >
> > I doubt that it's inherently slow. It depends on the implementation. I
> > remember tracing through the stream output on an MS compiler and[/color]
> discovered[color=green]
> > that it fabricated a format string and called sprintf! Fifty billion[/color]
> dollars[color=green]
> > in the bank, but they chose the cheapest, nastiest implementation[/color]
> possible.
>
> Well, I didn't have access to any of that $50B when I wrote that code
> in 1993, but I did write significant chunks of the C and C++ Standards
> in those areas. I knew that printf gets right all sorts of subtle
> corner cases that practically every iostreams implementation botched
> one way or the other. I also had mineral rights to all the code I needed
> to do the job other than `cheap and nasty,' and I was unable to get any
> significant improvement over fabricating a format string and calling
> sprintf.[/color]

That certainly sounds remarkable. In the case of string output with a given
field width there doesn't _seem_ to be a lot to do if it is done directly
(speaking from zero experience in implementing such things). To create a
format string and then have sprintf interpret it and then do the output
sounds like a lot of added overhead for a short string.

What about input? I remember reading a large text file full of numbers in
VC++ 5 or 6 and having to rewrite the code the C way because the C++
ifstream was many, many times slower. Maybe this is a clue to why sprintf
didn't make much difference to the output speed: there's already so much
overhead in C++ streams that using the C library didn't matter. If so,
programmers used to C won't exactly by encouraged to switch to streams.
[color=blue]
> FWIW, Microsoft's stash has roughly doubled since the day they chose to
> adopt our cheap and nasty approach. Coincidence? (Probably.)[/color]

No, I think you deserve a cut :-)

DW

P.S. Something I couldn't remember was whether you used sprintf to fabricate
the format string as well. Did you?

[P.J. Plauger]

Re: STL speed

"David White" <no@email.provi ded> wrote in message
news:gCELb.6882 $xm.325296@nasa l.pacific.net.a u...
[color=blue]
> "P.J. Plauger" <pjp@dinkumware .com> wrote in message
> news:0%wLb.1087 $Mt4.283@nwrddc 03.gnilink.net. ..[color=green]
> > "David White" <no@email.provi ded> wrote in message
> > news:wxlLb.6832 $xm.321720@nasa l.pacific.net.a u...
> >[color=darkred]
> > > > p.s. i know that STL uses IntrospectiveSo rt which seems to be good[/color]
> > choice,[color=darkred]
> > > i
> > > > suppose that INPUT (cin) is extremaly slow,
> > > > and <vector> as a dynamic structure also isn't to fast... any ideas?
> > >
> > > I doubt that it's inherently slow. It depends on the implementation. I
> > > remember tracing through the stream output on an MS compiler and[/color]
> > discovered[color=darkred]
> > > that it fabricated a format string and called sprintf! Fifty billion[/color]
> > dollars[color=darkred]
> > > in the bank, but they chose the cheapest, nastiest implementation[/color]
> > possible.
> >
> > Well, I didn't have access to any of that $50B when I wrote that code
> > in 1993, but I did write significant chunks of the C and C++ Standards
> > in those areas. I knew that printf gets right all sorts of subtle
> > corner cases that practically every iostreams implementation botched
> > one way or the other. I also had mineral rights to all the code I needed
> > to do the job other than `cheap and nasty,' and I was unable to get any
> > significant improvement over fabricating a format string and calling
> > sprintf.[/color]
>
> That certainly sounds remarkable. In the case of string output with a[/color]
given[color=blue]
> field width there doesn't _seem_ to be a lot to do if it is done directly
> (speaking from zero experience in implementing such things). To create a
> format string and then have sprintf interpret it and then do the output
> sounds like a lot of added overhead for a short string.[/color]

That's the trouble with software. What *seems* inefficient can only be
verified by measurement. Ones intuition is so often wrong.
[color=blue]
> What about input? I remember reading a large text file full of numbers in
> VC++ 5 or 6 and having to rewrite the code the C way because the C++
> ifstream was many, many times slower. Maybe this is a clue to why sprintf
> didn't make much difference to the output speed: there's already so much
> overhead in C++ streams that using the C library didn't matter. If so,
> programmers used to C won't exactly by encouraged to switch to streams.[/color]

Perhaps you ran afoul of the regrettable bug we had in that version.
See http://www.dinkumware.com/vc_fixes.html for the one-line fix.
If you opened a stream by filename, the bug defeated file buffering.
But absent this bug, the raw overhead of shoveling bytes through
iostreams isn't all that bad.

And to answer your leadoff question, we supply our own scanners for
integers and floating-point fields, since scanf has always been
klunkier than printf.
[color=blue][color=green]
> > FWIW, Microsoft's stash has roughly doubled since the day they chose to
> > adopt our cheap and nasty approach. Coincidence? (Probably.)[/color]
>
> No, I think you deserve a cut :-)[/color]

I keep trying...
[color=blue]
> P.S. Something I couldn't remember was whether you used sprintf to[/color]
fabricate[color=blue]
> the format string as well. Did you?[/color]

No.

P.J. Plauger
Dinkumware, Ltd.

http://www.dinkumware.com