STL speed

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 IntrospectiveSort 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?

re: STL speed

"Przemo Drochomirecki" <pedrosch@gazeta.pl> wrote in message
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 IntrospectiveSort 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]

I doubt that it's inherently slow. It depends on the implementation. I
remember tracing through the stream output on an MS compiler and discovered
that it fabricated a format string and called sprintf! Fifty billion dollars
in the bank, but they chose the cheapest, nastiest implementation possible.

DW

re: STL speed

"Przemo Drochomirecki" <pedrosch@gazeta.pl> wrote in
news:btkn1f$d4h$1@nemesis.news.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 IntrospectiveSort 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]

You didn't post your "clear-C-code", nor your Standard C++ code, thus there
is no way for us to even guess at what you've done inefficiently.

Gazing into my crystal ball says that you haven't expressed the same
program in C and C++.

re: STL speed

> Is STL really so slow?

That's hard to say without the source and it depends on quite a few other
things, like the STL implementation and the Compiler.


I'd write the programm as following:

#include <algorithm>
#include <iterator>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

int main()
{
ifstream file("input.txt");
vector<string> words(istream_iterator<string>(file),
(istream_iterator<string>()));
sort(words.begin(), words.end());
ofstream outfile("output.txt");
copy(words.begin(), words.end(), ostream_iterator<string>(outfile, "\n"));
}

Regards
Ignaz

re: STL speed

In article <btkn1f$d4h$1@nemesis.news.tpi.pl>, Przemo Drochomirecki wrote:[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?[/color]

(1) Depends on the compiler, and how the compiler is invoked, and possibly
on the STL implementation. Abstraction penalty is almost nil for a good
optimising compiler with optimisation turned on.

(2) As others pointed out, or hinted at, there are numerous ways the programs
could actually be fundamentally different. Possible performance issues here
depend on what functions are getting called, but both the input and output
could differ (on several implementations, C++ style streams are slower,
especially if you don't pay careful attention to how you do the IO)
[color=blue]
> p.s. i know that STL uses IntrospectiveSort which seems to be good choice, i
> suppose that INPUT (cin) is extremaly slow,[/color]

Well why not actually check this ?
[color=blue]
> and <vector> as a dynamic structure also isn't to fast... any ideas?[/color]

You can allocate space for it upfront. See reserve()

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

re: STL speed

Przemo Drochomirecki wrote:
[color=blue]
> 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?[/color]

No. You just screwed up.
Post both your C and C++ code
so that we can see what you did wrong.

re: STL speed

"E. Robert Tisdale" <E.Robert.Tisdale@jpl.nasa.gov> wrote in message
news:3FFE07DC.804@jpl.nasa.gov...[color=blue]
> Przemo Drochomirecki wrote:
>[color=green]
> > 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?[/color]
>
> 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; };

void read_names(vector<wordstruct>& x)
{
wordstruct q;
while (true) {
cin >> q.word;
if (q.word == string("0"))
break;
x.push_back(q);
}
}
struct wordCompare
{
bool operator()(const wordstruct& a, const wordstruct& b) {
return a.word<b.word;
}
};

wordCompare wordc;

int main()
{
vector<wordstruct> x;
read_names(x);
sort(x.begin(), x.end(), wordc);
// vector x is sorted
return 0;
}

compiled under VC++6.0

--- C ---

simple loop reading words with fgets, each word is seperately allocated with
memalloc and
than qsort.

compiled under gcc 3.0

thx for help:) (all five STL-masters)

re: STL speed

#include <algorithm>
#include <iterator>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

int main()
{
ifstream file("input.txt");
vector<string> words(istream_iterator<string>(file),
14 (istream_iterator<string>()));
15 sort(words.begin(), words.end());
16 ofstream outfile("output.txt");
17 copy(words.begin(), words.end(), ostream_iterator<string>(outfile,
"\n"));
}


i used well know copy&paste technique and here is what i got.
and frankly speaking and don't understand it at all (i'm not too familiar
with STL syntax...)
(no extra compiling setting -> simply gcc.exe ignez.cpp )

---------- gcc ----------
stl.cpp: In function `int main()':
stl.cpp:14: parse error before `)' token
stl.cpp:15: request for member `begin' in `words(...)', which is of
non-aggregate type `std::vector<std::string, std::allocator<std::string>[color=blue]
>[/color]
()(...)'
stl.cpp:15: request for member `end' in `words(...)', which is of
non-aggregate
type `std::vector<std::string, std::allocator<std::string> > ()(...)'
stl.cpp:17: request for member `begin' in `words(...)', which is of
non-aggregate type `std::vector<std::string, std::allocator<std::string>[color=blue]
>[/color]
()(...)'
stl.cpp:17: request for member `end' in `words(...)', which is of
non-aggregate
type `std::vector<std::string, std::allocator<std::string> > ()(...)'

Output completed (2 sec consumed) - Normal Termination

thx for extremely brief code, maybe STL isn't as bad as thought:)
Przemo

re: STL speed

In article <btl6t8$49t$1@nemesis.news.tpi.pl>, Przemo Drochomirecki wrote:[color=blue]
> #include <algorithm>
> #include <iterator>
> #include <iostream>
> #include <fstream>
> #include <string>
> #include <vector>
>
> using namespace std;
>
> int main()
> {
> ifstream file("input.txt");
> vector<string> words(istream_iterator<string>(file),
> 14 (istream_iterator<string>()));
> 15 sort(words.begin(), words.end());
> 16 ofstream outfile("output.txt");
> 17 copy(words.begin(), words.end(), ostream_iterator<string>(outfile,
> "\n"));
> }
>
>
> i used well know copy&paste technique and here is what i got.
> and frankly speaking and don't understand it at all (i'm not too familiar
> with STL syntax...)
> (no extra compiling setting -> simply gcc.exe ignez.cpp )[/color]

The compiler is getting confused because it thinks that you're declaring a
function when you declare the vector words. The ugly workaround is to use
this:

istream_iterator<string> in1(file), in2;
vector<string> words (in1,in2);

The pretty way (but may not work with older compilers):

vector<string> words( (istream_iterator<string>(file)),
istream_iterator<string>());

Note that the extra parens go around the *first* argument, not the second
one.

Scott Meyers discusses this in Effective STL in some depth.

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

re: STL speed

Przemo Drochomirecki wrote:[color=blue]
> "E. Robert Tisdale" <E.Robert.Tisdale@jpl.nasa.gov> wrote in message
> news:3FFE07DC.804@jpl.nasa.gov...
>[color=green]
>>Przemo Drochomirecki wrote:
>>
>>[color=darkred]
>>>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?[/color]
>>
>>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; };
>
> void read_names(vector<wordstruct>& x)
> {
> wordstruct q;
> while (true) {
> cin >> q.word;
> if (q.word == string("0"))
> break;
> x.push_back(q);
> }
> }[/color]

You'll find most of the time is spent in the routine above.

This can be quite time consuming because you will allocate and
deallocate string("0") for every iteration.

if (q.word == string("0"))

You might do this:

if (q.word.length()==1 && q.word == '0')

Still, this is probably ony a 10-15% improvement if the compiler could
not optimize it.

Also, "cin >>" is really quite expensive as well and probably where
you're spending most of the time.

Also, instead of using a vector, you might be better of using a "deque"
container to limit the re-allocation required when growing the vector.

Probably the fastest implementation is to map the file into memory
(off-topic here) and parse the file in memory and then use std::sort.

re: STL speed

In article <btl605$163$1@nemesis.news.tpi.pl>, Przemo Drochomirecki wrote:[color=blue]
>
> int main()
> {
> vector<wordstruct> x;
> read_names(x);
> sort(x.begin(), x.end(), wordc);
> // vector x is sorted
> return 0;
> }
>
> compiled under VC++6.0
>
> --- C ---
>
> simple loop reading words with fgets, each word is seperately allocated with
> memalloc and
> than qsort.
>
> compiled under gcc 3.0[/color]

Oh boy. Did you run them on different computers too ?

Cheers,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

re: STL speed

In article <btl605$163$1@nemesis.news.tpi.pl>,
Przemo Drochomirecki <pedrosch@gazeta.pl> wrote:[color=blue]
>
>"E. Robert Tisdale" <E.Robert.Tisdale@jpl.nasa.gov> wrote in message
>news:3FFE07DC.804@jpl.nasa.gov...[color=green]
>> Przemo Drochomirecki wrote:
>>[color=darkred]
>> > 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?[/color]
>>
>> 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; };
>
>void read_names(vector<wordstruct>& x)
>{
> wordstruct q;
> while (true) {
> cin >> q.word;
> if (q.word == string("0"))
> break;
> x.push_back(q);
> }
>}[/color]

Is there some specific reason why you're using the word "0"
as a terminator? It would be more efficient simply to test for
end of file:

while (cin >> q.word)
{
x.push_back(q);
}

It will also speed things up if you estimate the number of words in
advance and reserve space in the vector before starting to read:

x.reserve (desired_size);

In most implementations, when a vector reaches its capacity on
push_back(), it allocates a new buffer twice as big as the old one, and
copies all the current data from the old buffer to the new one.

How do you handle the capacity issue in the C version?

--
Jon Bell <jtbellm4h@presby.edu> Presbyterian College
Dept. of Physics and Computer Science Clinton, South Carolina USA

re: STL speed

"Donovan Rebbechi" <abuse@aol.com> wrote in message
news:slrnbvs91i.r0b.abuse@panix2.panix.com...[color=blue]
> In article <btl605$163$1@nemesis.news.tpi.pl>, Przemo Drochomirecki wrote:[color=green]
> >
> > int main()
> > {
> > vector<wordstruct> x;
> > read_names(x);
> > sort(x.begin(), x.end(), wordc);
> > // vector x is sorted
> > return 0;
> > }
> >
> > compiled under VC++6.0
> >
> > --- C ---
> >
> > simple loop reading words with fgets, each word is seperately allocated[/color][/color]
with[color=blue][color=green]
> > memalloc and
> > than qsort.
> >
> > compiled under gcc 3.0[/color]
>
> Oh boy. Did you run them on different computers too ?
>
> Cheers,[/color]

It may be simpler than that. If the compiler does not inline the hundreds of
small calls that this makes the performance WILL
be slow on any platform. On several platforms that I have used inlining is
not performed when building a debug version and on
some it is not done unless optimization is turned on.

re: STL speed

Przemo Drochomirecki wrote:[color=blue]
>
>
> compiled under VC++6.0
>
> --- C ---
>
> simple loop reading words with fgets, each word is seperately allocated with
> memalloc and
> than qsort.[/color]

How did you grow the array when words are added?
[color=blue]
>
> compiled under gcc 3.0
>
> thx for help:) (all five STL-masters)[/color]

Also: Did you ever consider a std::map for doing things like that?

--
Karl Heinz Buchegger
kbuchegg@gascad.at

re: STL speed

On Fri, 9 Jan 2004 04:07:02 -0800, "Przemo Drochomirecki"
<pedrosch@gazeta.pl> wrote:
[color=blue]
>
>"E. Robert Tisdale" <E.Robert.Tisdale@jpl.nasa.gov> wrote in message
>news:3FFE07DC.804@jpl.nasa.gov...[color=green]
>> Przemo Drochomirecki wrote:
>>[color=darkred]
>> > 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?[/color]
>>
>> 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=blue]
>
>void read_names(vector<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=blue]
> x.push_back(q);
> }
>}
>struct wordCompare
>{
> bool operator()(const wordstruct& a, const wordstruct& b) {
> return a.word<b.word;
> }[/color]

The above should be:

bool operator()(const wordstruct& a, const wordstruct& b) const {
return a.word<b.word;
}

(not that that will improve performance)
[color=blue]
>};
>
>wordCompare wordc;
>
>int main()
>{[/color]

Here you should add:
std::ios::sync_with_stdio(false);
since buffering will be disabled on cin and cout on some
implementations if you don't.
[color=blue]
> vector<wordstruct> x;[/color]

Here you might want to reserve some space in the vector:
x.reserve(1000); //or more
[color=blue]
> read_names(x);
> sort(x.begin(), x.end(), wordc);
> // vector x is sorted
> return 0;
>}
>
>compiled under VC++6.0
>
>--- C ---
>
>simple loop reading words with fgets, each word is seperately allocated with
>memalloc and
>than qsort.
>
>compiled under gcc 3.0
>
>thx for help:) (all five STL-masters)[/color]

Why did you compile the two using different compilers!? Also make sure
you use maximum optimization settings - C++ code relies heavily on
optimization to inline all of the small functions.

Tom

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

re: STL speed

"Przemo Drochomirecki" <pedrosch@gazeta.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 IntrospectiveSort 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

re: STL speed

Peter Koch Larsen wrote:[color=blue]
> "Przemo Drochomirecki" <pedrosch@gazeta.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

re: STL speed

"David White" <no@email.provided> wrote in message
news:wxlLb.6832$xm.321720@nasal.pacific.net.au...
[color=blue][color=green]
> > p.s. i know that STL uses IntrospectiveSort 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

re: STL speed

"Peter Koch Larsen" <pkl@mailme.dk> wrote in message
news:3ffe79c9$0$9827$edfadb0f@dread14.news.tele.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

re: STL speed

In article <rurLb.3349$qM1.992@news-binary.blueyonder.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/

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.

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@gazeta.pl> wrote in message news:<btkn1f$d4h$1@nemesis.news.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 IntrospectiveSort 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]

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@gazeta.pl> wrote in message news:<btkn1f$d4h$1@nemesis.news.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 IntrospectiveSort 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]

re: STL speed

tom_usenet wrote:
[color=blue]
> On Fri, 9 Jan 2004 04:07:02 -0800, "Przemo Drochomirecki"
> <pedrosch@gazeta.pl> wrote:
>[color=green]
>>
>>"E. Robert Tisdale" <E.Robert.Tisdale@jpl.nasa.gov> wrote in message
>>news:3FFE07DC.804@jpl.nasa.gov...[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(vector<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<wordstruct>& x)
};

HowIWouldDoIt::_testString = "0";

void read_names(vector<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(false);
> 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<wordstruct> 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 !!

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

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

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

re: STL speed

On Fri, 09 Jan 2004 14:47:31 +0000, Sean Clarke
<sean.clarke@no-spam.sec-consulting.co.uk> 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==(const basic_string<charT,traits,Allocator>& 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<wordstruct>& x)
>};
>
>HowIWouldDoIt::_testString = "0";
>
>void read_names(vector<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<wordstruct> 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

re: STL speed

"P.J. Plauger" <pjp@dinkumware.com> wrote in message
news:0%wLb.1087$Mt4.283@nwrddc03.gnilink.net...[color=blue]
> "David White" <no@email.provided> wrote in message
> news:wxlLb.6832$xm.321720@nasal.pacific.net.au...
>[color=green][color=darkred]
> > > p.s. i know that STL uses IntrospectiveSort 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?

re: STL speed

"David White" <no@email.provided> wrote in message
news:gCELb.6882$xm.325296@nasal.pacific.net.au...
[color=blue]
> "P.J. Plauger" <pjp@dinkumware.com> wrote in message
> news:0%wLb.1087$Mt4.283@nwrddc03.gnilink.net...[color=green]
> > "David White" <no@email.provided> wrote in message
> > news:wxlLb.6832$xm.321720@nasal.pacific.net.au...
> >[color=darkred]
> > > > p.s. i know that STL uses IntrospectiveSort 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

re: STL speed

Przemo Drochomirecki wrote:
[code redacted][color=blue]
> compiled under VC++6.0[/color]

There's your problem. VC5 and VC6 had a known buffering issue with ifstreams.
PJ has commented on it, and there is a fix somewhere on the DinkumWare website.

red floyd