STL speed

[David White]

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?

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

 

[Andre Kostur]

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?

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++.

 

[Ignaz Rutter]

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

 

[Donovan Rebbechi]

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?

(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)

p.s. i know that STL uses IntrospectiveSort which seems to be good choice, i
suppose that INPUT (cin) is extremaly slow,

Well why not actually check this ?

and <vector> as a dynamic structure also isn't to fast... any ideas?

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

Cheers,

 

[E. Robert Tisdale]

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.

 

[Donovan Rebbechi]

#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 )

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,

 

[Gianni Mariani]

---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);
}
}

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.

 

[Donovan Rebbechi]

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

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

Cheers,

 

[Jon Bell]

---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);
}
}

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?

 

[Nick Hounsome]

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

Cheers,

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.

 

[Przemo Drochomirecki]

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?

 

[Karl Heinz Buchegger]

compiled under VC++6.0

--- C ---

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

How did you grow the array when words are added?

compiled under gcc 3.0

thx for help (all five STL-masters)

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

 

[tom_usenet]

---STL CODE---

#include <string>
#include <conio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
struct wordstruct { string word; };

Why have wordstruct? What's wrong with using string directly?

void read_names(vector<wordstruct>& x)
{
wordstruct q;
while (true) {
cin >> q.word;
if (q.word == string("0"))
break;

The above would be much more efficient as:

if (q.word == "0")

since that saves an extra memory allocation per iteration.

x.push_back(q);
}
}
struct wordCompare
{
bool operator()(const wordstruct& a, const wordstruct& b) {
return a.word<b.word;
}

The above should be:

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

(not that that will improve performance)

};

wordCompare wordc;

int main()
{

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.

vector<wordstruct> x;

Here you might want to reserve some space in the vector:
x.reserve(1000); //or more

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)

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

 

[Peter Koch Larsen]

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?

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]

"Przemo Drochomirecki" <[email protected]> skrev i en meddelelse

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.

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

 

[Przemo Drochomirecki]

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

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

 

[P.J. Plauger]

choice,

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.

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]

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.

Uh, there was a recent thread that showed neither of these factoids
to be all that true.

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.

That I agree with.

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.

Also agree.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

 

[Przemo Drochomirecki]

#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
()(...)'
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
()(...)'
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

 

[Donovan Rebbechi]

It may be simpler than that.

Yes, I'm almost certain it is. What I meant was that he's manipulated several
variables, including the ones he's interested in.

If the compiler does not inline the hundreds of
small calls that this makes the performance WILL
be slow on any platform.

Yes, as I said in my other post.

Cheers,