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?

[Donovan Rebbechi]

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

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

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

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

[Jon Bell]

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

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

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

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 <jt*******@pres by.edu> Presbyterian College
Dept. of Physics and Computer Science Clinton, South Carolina USA

[Nick Hounsome]

"Donovan Rebbechi" <ab***@aol.co m> wrote in message
news:sl******** **********@pani x2.panix.com...

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

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

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.

[Karl Heinz Buchegger]

Przemo Drochomirecki wrote:

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?

--
Karl Heinz Buchegger
kb******@gascad .at

[tom_usenet]

On Fri, 9 Jan 2004 04:07:02 -0800, "Przemo Drochomirecki"
<pe******@gazet a.pl> wrote:

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

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

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

void read_names(vect or<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()(cons t wordstruct& a, const wordstruct& b) {
return a.word<b.word;
}
The above should be:

bool operator()(cons t 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(fals e);
since buffering will be disabled on cin and cout on some
implementations if you don't.
vector<wordstru ct> 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]

"Przemo Drochomirecki" <pe******@gazet a.pl> skrev i en meddelelse
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?

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]

Peter Koch Larsen wrote:

"Przemo Drochomirecki" <pe******@gazet a.pl> skrev i en meddelelse
news:bt******** **@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.

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]

"David White" <[e-mail] ded> wrote in message
news:wx******** **********@nasa l.pacific.net.a u...

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.

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]

"Peter Koch Larsen" <pk*@mailme.d k> wrote in message
news:3f******** **************@ dread14.news.te le.dk...

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

[Donovan Rebbechi]

In article <ru************ ****@news-binary.blueyond er.co.uk>, Nick Hounsome wrote:

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

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