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?

[Tõnu Aas]

> The task was indeed simple. Read 2.000.000 words (average length = 9),
sort

them and write it to new file.

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]

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" <pe******@gazet a.pl> wrote in message news:<bt******* ***@nemesis.new s.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?

[Jeff Schwab]

Please don't top-post.

EnTn wrote:

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... (?)
That's the idea.
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.. ..?
Yes, that's the whole purpose of the "reserve" method.
MHTWEOTSH...
I give up. Is that a common greeting in some language I don't speak, or
does it stand for something?

"Przemo Drochomirecki" <pe******@gazet a.pl> wrote in message news:<bt******* ***@nemesis.new s.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?

[Sean Clarke]

tom_usenet wrote:

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.g ov...

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.

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>
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.
Interesting... I've not used this before.

vector<wordstru ct> x;

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

I think this will probably be the crux of the problem, the other stuff I'd
consider "fine tuning", but worthwhile none the less.

read_names(x);
sort(x.begin(), x.end(), wordc);
// vector x is sorted
return 0;
}

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]

EnTn wrote:

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

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
kb******@gascad .at

[Martijn Lievaart]

On Fri, 09 Jan 2004 05:30:01 -0800, EnTn wrote:

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

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]

On Fri, 09 Jan 2004 15:10:30 +0200, Tõnu Aas wrote:

The task was indeed simple. Read 2.000.000 words (average length = 9),

sort

them and write it to new file.

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.

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]

On Fri, 09 Jan 2004 14:47:31 +0000, Sean Clarke
<se*********@ no-spam.sec-consulting.co.u k> wrote:

The above would be much more efficient as:

if (q.word == "0")

since that saves an extra memory allocation per iteration.
Are you sure here that the compiler would not just create a string("0") ?

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.
Personally I would use a either a const static or pre constructed const
string, is this overkill?
A pre-constructed one is a better solution - in theory the comparison
can be slightly faster.
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;
How about just:

wordstruct q;
std::string const testString("0") ;
while (true) {
cin >> q.word;
if (q.word == testString)
break;

vector<wordstru ct> x;

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

I think this will probably be the crux of the problem, the other stuff I'd
consider "fine tuning", but worthwhile none the less.

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.

read_names(x);
sort(x.begin(), x.end(), wordc);
// vector x is sorted
return 0;
}

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

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]

"P.J. Plauger" <pj*@dinkumware .com> wrote in message
news:0%******** ********@nwrddc 03.gnilink.net. ..

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

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.
FWIW, Microsoft's stash has roughly doubled since the day they chose to
adopt our cheap and nasty approach. Coincidence? (Probably.)

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]

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

"P.J. Plauger" <pj*@dinkumware .com> wrote in message
news:0%******** ********@nwrddc 03.gnilink.net. ..

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

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.
That's the trouble with software. What *seems* inefficient can only be
verified by measurement. Ones intuition is so often wrong.
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.
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.

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

No, I think you deserve a cut :-)

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

No.

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