STL speed

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

[David White]

"Przemo Drochomirecki" <pe******@gazet a.pl> wrote in message
news:bt******** **@nemesis.news .tpi.pl...

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?

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]

"Przemo Drochomirecki" <pe******@gazet a.pl> wrote in
news:bt******** **@nemesis.news .tpi.pl:

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?

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_i terator<string> (file),
(istream_iterat or<string>()));
sort(words.begi n(), words.end());
ofstream outfile("output .txt");
copy(words.begi n(), words.end(), ostream_iterato r<string>(outfi le, "\n"));
}

Regards
Ignaz

[Donovan Rebbechi]

In article <bt**********@n emesis.news.tpi .pl>, Przemo Drochomirecki wrote:

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 IntrospectiveSo rt 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,
--
Donovan Rebbechi
http://pegasus.rutgers.edu/~elflord/

[E. Robert Tisdale]

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.

[Przemo Drochomirecki]

"E. Robert Tisdale" <E.************ **@jpl.nasa.gov > wrote in message
news:3F******** **@jpl.nasa.gov ...

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.

---STL CODE---

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

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

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

wordCompare wordc;

int main()
{
vector<wordstru ct> 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)

[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_i terator<string> (file),
14 (istream_iterat or<string>()));
15 sort(words.begi n(), words.end());
16 ofstream outfile("output .txt");
17 copy(words.begi n(), words.end(), ostream_iterato r<string>(outfi le,
"\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<st d::string, std::allocator< std::string>

()(...)'
stl.cpp:15: request for member `end' in `words(...)', which is of
non-aggregate
type `std::vector<st d::string, std::allocator< std::string> > ()(...)'
stl.cpp:17: request for member `begin' in `words(...)', which is of
non-aggregate type `std::vector<st d::string, std::allocator< std::string>

()(...)'
stl.cpp:17: request for member `end' in `words(...)', which is of
non-aggregate
type `std::vector<st d::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]

In article <bt**********@n emesis.news.tpi .pl>, Przemo Drochomirecki wrote:

#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_i terator<string> (file),
14 (istream_iterat or<string>()));
15 sort(words.begi n(), words.end());
16 ofstream outfile("output .txt");
17 copy(words.begi n(), words.end(), ostream_iterato r<string>(outfi le,
"\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_iterato r<string> in1(file), in2;
vector<string> words (in1,in2);

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

vector<string> words( (istream_iterat or<string>(file )),
istream_iterato r<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/

[Gianni Mariani]

Przemo Drochomirecki wrote:

"E. Robert Tisdale" <E.************ **@jpl.nasa.gov > wrote in message
news:3F******** **@jpl.nasa.gov ...

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.

---STL CODE---

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

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

void read_names(vect or<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.