std::vector performance

[Denis Remezov]

Hi,

I'm using a std::vector to store a list of user defined objects. The vector
may have well over 1000 elements, and I'm suffering a performance hit. If I
use push_back I get a much worse perfomance than if I first define the
vector of a given size, then write to the elements with myvec =

However, I'm currently thinking that it isn't feasible to obtain the vector
size, so really need to resize the vector dynamically as I go. Is push_back
the fastest function to add elements to the end of a vector, or is there a
faster way (a different container, maybe)?

Although it periodically causes reallocations, push_back() is still an amortised
constant time operation. reserve() can help to cut on the number of reallocations
if you can estimate the expected number of elements to be added.

How expensive is a copying of an element? If the objects are large enough or
if the copy constructor does a lot of work, it may be better to use a vector of
pointers to objects rather than a vector of objects themselves.

Another way to avoid copying is to use an std::list. You haven't mentioned if you
really needed random access to the elements. If not, a list could be the right
thing, especially if the objects are not too small or are expensive to copy.

I've also seen this with the std::string object. I have a function called
GetFloat, which extracts a space delimited float from a text string:

float GetFloat(const string& Str, const int& Spaces, bool& Valid)
{
int ColPosition = GetNewPosition(Str, Spaces); // convert spaces to
chars

if(ColPosition == -1) {
Valid = false;
return 0.0;
}

std::string s;
std::string::const_iterator p = Str.begin() + ColPosition;

while(*p != ' ' && p != Str.end()) {
if(*p == 'I') { Valid = false; return 0.0; }
if(*p != ' ') s.push_back(*p); <============
alternatives below
++p;
}

I think the above should be
while(p != Str.end() && *p != ' ') {
if(*p == 'I') { Valid = false; return 0.0; }
s.push_back(*p);
++p;
}

Valid = true;
return atof(s.c_str());
}

for s, if I make it a fixed length and use s = ... it runs rather faster
than the above. Also s+=(*p) runs slightly faster than above, but not as
fast as s = ...

This function may be called thousands of times during my program (loading a
data file) and perhaps this is why the difference is significant. Is this
what I should expect to see, I thought they should be similar?

Reuse the same object s for multiple invocations, increasing its size when
needed. A static variable is a simple solution. If it isn't adequate, define
a class instead of a function, make s a member. I'd use a vector for s instead
of a string.

Denis

 

[Steve]

Hi,

I'm using a std::vector to store a list of user defined objects. The vector
may have well over 1000 elements, and I'm suffering a performance hit. If I
use push_back I get a much worse perfomance than if I first define the
vector of a given size, then write to the elements with myvec =

However, I'm currently thinking that it isn't feasible to obtain the vector
size, so really need to resize the vector dynamically as I go. Is push_back
the fastest function to add elements to the end of a vector, or is there a
faster way (a different container, maybe)?

I've also seen this with the std::string object. I have a function called
GetFloat, which extracts a space delimited float from a text string:

float GetFloat(const string& Str, const int& Spaces, bool& Valid)
{
int ColPosition = GetNewPosition(Str, Spaces); // convert spaces to
chars

if(ColPosition == -1) {
Valid = false;
return 0.0;
}

std::string s;
std::string::const_iterator p = Str.begin() + ColPosition;

while(*p != ' ' && p != Str.end()) {
if(*p == 'I') { Valid = false; return 0.0; }
if(*p != ' ') s.push_back(*p); <============
alternatives below
++p;
}
Valid = true;
return atof(s.c_str());
}

for s, if I make it a fixed length and use s = ... it runs rather faster
than the above. Also s+=(*p) runs slightly faster than above, but not as
fast as s = ...

This function may be called thousands of times during my program (loading a
data file) and perhaps this is why the difference is significant. Is this
what I should expect to see, I thought they should be similar?


Thanks for your time,
Steve

 

[Derek]

I'm using a std::vector to store a list of user defined

objects. The vector may have well over 1000 elements,
and I'm suffering a performance hit. If I use push_back
I get a much worse perfomance than if I first define the
vector of a given size, then write to the elements with
myvec=

Not a surprise. A vector grows dynamically, so at some
point it has to allocate a bigger block of memory, copy
all existing elements to it, and free the original memory.
This probably happens several times and ctors/dtors are
involved if your elements are not built-in types. A vector
uses a pretty smart allocation policy, but that doesn't
change the fact that all this resizing business takes time.

You can tell a vector to allocate memory ahead of time
using vector::reserve() to avoid some allocations, but that
doesn't help if you really have no idea how big the vector
might have to be. Unless you are prepared to reserve() for
the worst case (or close to it).

Another possibility is to use a custom allocator, say one
based on a memory pool strategy. This can greatly improve
runtime performance when allocation is the bottleneck.
Check out the allocator from Boost:

http://www.boost.org/libs/pool/doc/

Though this might not help much if most of the time is
spend creating and destroying elements (ie, in ctors and
dtors), though this doesn't seem to be the case for you.

However, I'm currently thinking that it isn't feasible
to obtain the vector size, so really need to resize the
vector dynamically as I go. Is push_back the fastest
function to add elements to the end of a vector, or is
there a faster way (a different container, maybe)?

I'd stay try the custom pool allocator if you really have
no idea what size the vector might have to be. Another
option is to try a container that doesn't have to copy all
elements when it runs out of memory, like std::list.
Though it allocates memory for every new element, so a pool
allocator will probably help there too.

I've also seen this with the std::string object. I have
a function called GetFloat, which extracts a space
delimited float from a text string:

The situation with your string is exactly the same.
Though if your string is bounded in length, you could use
a vector<char> instead and reserve() enough memory for
the typical or worst case. Then just remember to null
terminate and return atof(&s[0]).

Derek

 

[Leor Zolman]

The situation with your string is exactly the same.
Though if your string is bounded in length, you could use
a vector<char> instead and reserve() enough memory for
the typical or worst case. Then just remember to null
terminate and return atof(&s[0]).

std::string supports reserve(), too.
-leor

 

[James Moughan]

Hi,

I'm using a std::vector to store a list of user defined objects. The vector
may have well over 1000 elements, and I'm suffering a performance hit. If I
use push_back I get a much worse perfomance than if I first define the
vector of a given size, then write to the elements with myvec =

However, I'm currently thinking that it isn't feasible to obtain the vector
size, so really need to resize the vector dynamically as I go. Is push_back
the fastest function to add elements to the end of a vector, or is there a
faster way (a different container, maybe)?

Yup, you will on any random-access container, since it has to copy
memory. Unfortunately it'll probably do it about as fast or faster
than anything else you could write. Though I've seen dequeue perform
significantly faster than vector on the g++ compiler, for no reason I
could fathom.

I've also seen this with the std::string object. I have a function called
GetFloat, which extracts a space delimited float from a text string:

float GetFloat(const string& Str, const int& Spaces, bool& Valid)
{
int ColPosition = GetNewPosition(Str, Spaces); // convert spaces to
chars

if(ColPosition == -1) {
Valid = false;
return 0.0;
}

std::string s;
std::string::const_iterator p = Str.begin() + ColPosition;

while(*p != ' ' && p != Str.end()) {
if(*p == 'I') { Valid = false; return 0.0; }
if(*p != ' ') s.push_back(*p); <============
alternatives below
++p;
}
Valid = true;
return atof(s.c_str());
}

for s, if I make it a fixed length and use s = ... it runs rather faster
than the above. Also s+=(*p) runs slightly faster than above, but not as
fast as s = ...

This function may be called thousands of times during my program (loading a
data file) and perhaps this is why the difference is significant. Is this
what I should expect to see, I thought they should be similar?

You realise the if(*p != ' ') statement is redundant, since you're
already in a while (*p != ' ' && ... loop?

Since in this case you know the max size of the new string is the size
of str less ColPosition, you can resize() it first then insert the
elements; the fastest way to do that on my compiler is to use an
iterator starting from s.begin() for assignment rather than s, but
YMMV.

You may also get a speed-up by defining an iterator rather than
calling Str.end() continuosly.

 

[John Harrison]

float GetFloat(const string& Str, const int& Spaces, bool& Valid)

{
int ColPosition = GetNewPosition(Str, Spaces); // convert spaces to
chars

if(ColPosition == -1) {
Valid = false;
return 0.0;
}

std::string s;
std::string::const_iterator p = Str.begin() + ColPosition;

while(*p != ' ' && p != Str.end()) {
if(*p == 'I') { Valid = false; return 0.0; }
if(*p != ' ') s.push_back(*p); <============
alternatives below
++p;
}
Valid = true;
return atof(s.c_str());
}

You are going to get the best performance improvement by realising that you
don't need s at all.

float GetFloat(const string& Str, const int& Spaces, bool& Valid)
{
int ColPosition = GetNewPosition(Str, Spaces); // convert spaces to
chars

if(ColPosition == -1) {
Valid = false;
return 0.0;
}
char* endptr;
float f = strtof(Str.c_str() + ColPosition, &endptr);
if (*endptr == 'I') {
Valid = false;
return 0.0;
}
Valid = true;
return f;
}

john

 

[Peter Koch Larsen]

Hi,

I'm using a std::vector to store a list of user defined objects. The vector
may have well over 1000 elements, and I'm suffering a performance hit. If I
use push_back I get a much worse perfomance than if I first define the
vector of a given size, then write to the elements with myvec =

However, I'm currently thinking that it isn't feasible to obtain the vector
size, so really need to resize the vector dynamically as I go. Is push_back
the fastest function to add elements to the end of a vector, or is there a
faster way (a different container, maybe)?

[snip]

Apart from what others have said, i could recommend that you experiment with
std::deque.

 

[Steve]

Hi Guys,

Many thanks for your input, although it appears I've mis-informed you,
sorry.

The row of data for Str might look like this:

D 36 1 F 0 134644058 28 0 10000000 279 0 I 1 I 1 I 1 I 1 I 1 I 1 I 1 I 1 I 1
5.50000E+01 1 -1.50000E+01 1 I 1 I 1 I 1 I 1 I 1 I 1 I 1

From elseswhere in the file, I know how many spaces there are to each float
(in this case there are only 2, each 'I' could potentially be a float
value.)

So in my code, I first use GetNewPosition to convert the number of spaces to
a 'number of characters' offset. Then I read each char until I find another
space, then I convert this to a float, then return it. Therefore, it's not
actually the length of Str - ColPosition to give me the string length.

Sorry for the confusion. I get the impression from answers that a deque, and
possibly smart pointers is the way to go....does this still hold?

John Harrison, thanks for your reply, but what's strtof? I haven't seen this
before, and can't find it in my C++ books (Stroustrup's CPL, STL Tutorial
and Reference, C++ The Complete Reference) I assume this won't stand anyway,
as I've explained my requirements, hopefully a bit clearer.

Many thanks again for your time,
Steve.

Hi,

I'm using a std::vector to store a list of user defined objects. The vector
may have well over 1000 elements, and I'm suffering a performance hit. If I
use push_back I get a much worse perfomance than if I first define the
vector of a given size, then write to the elements with myvec =

However, I'm currently thinking that it isn't feasible to obtain the vector
size, so really need to resize the vector dynamically as I go. Is push_back
the fastest function to add elements to the end of a vector, or is there a
faster way (a different container, maybe)?

I've also seen this with the std::string object. I have a function called
GetFloat, which extracts a space delimited float from a text string:

float GetFloat(const string& Str, const int& Spaces, bool& Valid)
{
int ColPosition = GetNewPosition(Str, Spaces); // convert spaces to
chars

if(ColPosition == -1) {
Valid = false;
return 0.0;
}

std::string s;
std::string::const_iterator p = Str.begin() + ColPosition;

while(*p != ' ' && p != Str.end()) {
if(*p == 'I') { Valid = false; return 0.0; }
if(*p != ' ') s.push_back(*p); <============
alternatives below
++p;
}
Valid = true;
return atof(s.c_str());
}

for s, if I make it a fixed length and use s = ... it runs rather faster
than the above. Also s+=(*p) runs slightly faster than above, but not as
fast as s = ...

This function may be called thousands of times during my program (loading a
data file) and perhaps this is why the difference is significant. Is this
what I should expect to see, I thought they should be similar?


Thanks for your time,
Steve

 

[John Harrison]

John Harrison, thanks for your reply, but what's strtof? I haven't seen this
before, and can't find it in my C++ books (Stroustrup's CPL, STL Tutorial
and Reference, C++ The Complete Reference) I assume this won't stand anyway,
as I've explained my requirements, hopefully a bit clearer.

strtof is part of the C library, just like atof. C++ inherits the C library
mostly unchanged. The point about strtof is that it converts a string to a
float but it also tells you what the first non-convertible char it found
was, in your case this might be an 'I'. Documented here for instance
http://www.hmug.org/man/3/strtof.html

I think I understood your requirements first time round so I think it does
stand and therefore you should use it.

john

 

[Steve]

strtof is part of the C library, just like atof. C++ inherits the C library
mostly unchanged. The point about strtof is that it converts a string to a
float but it also tells you what the first non-convertible char it found
was, in your case this might be an 'I'. Documented here for instance
http://www.hmug.org/man/3/strtof.html

I think I understood your requirements first time round so I think it does
stand and therefore you should use it.

Hi John,

Thanks again. I hope I'm not being a no-brainer, but I can't find strtof.
I'm using Borland C++Builder5 Compiler, and I've searched the include
folders for files containing strtof, the only hit being the VCL's version of
StringToFloat. (you're going to tell me to use a 'real' compiler now, aren't
you <g>)

Regards,
Steve.

 

[John Harrison]

Hi John,

Thanks again. I hope I'm not being a no-brainer, but I can't find strtof.
I'm using Borland C++Builder5 Compiler, and I've searched the include
folders for files containing strtof, the only hit being the VCL's version of
StringToFloat. (you're going to tell me to use a 'real' compiler now, aren't
you <g>)

strtof is in C99 standard, which I guess means many compilers won't support
it yet.

Use strtod and a cast from double to float instead (or just switch to double
throughout, normally double is to be preferred over float).

If you don't have strtod then I really would suggest getting a real
compiler.

john

 

[Steve]

Thanks John, found it!

Steve