• Advertisement
Sign in to follow this  

std::vector slow

This topic is 3735 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have to calculate some geometry dynamically (about 6000 vertices and 18000 indices) every frame. As I calculated the geometry, I was using push_back to store the computed vertices and indices. Note: I called vector::reserve at initialization time with a large enough max, so no memory allocation should be needed at runtime. I narrowed it down that filling the vectors was the slow part. I replaced them with C-arrays, and got about a 20 ms performance increase per frame. I went from 20 ms per frame to 2 ms per frame. Any ideas why it was slow? The code looked like this:
WORD baseIndex = (WORD)m_vertices.size();

	for(int i = 0; i < numVertices; ++i)
		m_vertices.push_back(v);

	m_vertices.push_back(centroid);

	for(int i = 0; i < numVertices; ++i)
	{
		m_indices.push_back( baseIndex+i ); 
		m_indices.push_back( baseIndex + ((i+1)%numVertices) );
		m_indices.push_back( baseIndex + numVertices ); // centroid
	}

Share this post


Link to post
Share on other sites
Advertisement
Was this in Debug or Release mode?

If in Debug mode then std::vector::push_back might be performing some error checking (memory verification stuff) that in large unoptimized quantities would be much slower than just an array index (which assembles to an offset even when Debugging I think?). This is the first thing that comes to mind, but if this is a Release build push_back probably would optimize to the array code anyway (besides the function call). Check the assembly output if possible or step through the assembly in your debugger. Thats as much as I can think of, as long as you're positive the vector isn't being cleared/reallocated every frame.

Share this post


Link to post
Share on other sites
Its probably having to reallocate and copy memory around, try calling .reserve with the amount of pushes you are expecting before you start pushing them:


WORD baseIndex = (WORD)m_vertices.size();

m_vertices.reserve(numVertices+1);
for(int i = 0; i < numVertices; ++i)

m_vertices.push_back(v);



m_vertices.push_back(centroid);


m_indices.reserve(numVertices*3);
for(int i = 0; i < numVertices; ++i)

{

m_indices.push_back( baseIndex+i );

m_indices.push_back( baseIndex + ((i+1)%numVertices) );

m_indices.push_back( baseIndex + numVertices ); // centroid

}




Edit: Also, don't clear and fill the vector each frame, modify its contents instead.

Share this post


Link to post
Share on other sites
If you really need to "clear" the vector, use resize(0) instead, since clear() might (depending on your compiler) actually also free the memory.

Share this post


Link to post
Share on other sites
// Bad:
for(int i = 0; i < numVertices; ++i)
m_vertices.push_back(v);

// Good:
m_vertices.insert(m_vertices.end(), v, v+numVertices);

Share this post


Link to post
Share on other sites
If you're using VS2k5, it performs quite a bit of error-checking by default, even in release builds. You have to make a couple of #define's to disable it.

Share this post


Link to post
Share on other sites
Quote:

If you're using VS2k5, it performs quite a bit of error-checking by default, even in release builds. You have to make a couple of #define's to disable it.


I am using VS2005. Do you know what the defines are?

Share this post


Link to post
Share on other sites
#define _SCL_SECURE 0


Also, Kwizatz is showing off the perfect way to get your .reserve()s wrong, you want:
m_vertices.reserve( baseIndex + numVertices + 1 );
m_indices.reserve( m_indicies.size() + numVertices*3 );


VS2k5's implementation of .reserve, at least, also fails to grow exponentially if .reserve(n), n > .capacity() -- this could actually end up slowing things down as a result.

Share this post


Link to post
Share on other sites
Thanks for the replies so far.

One thing I recently tried was to stop using push_back. Instead, I just used vector::operator[], and kept my own size counter. This is now comparable to the array performance.

I noticed push_back has a conditional statement (in case it needs to resize). Do you think that is the extra overhead? I read hardware does not like branching statements.

Share this post


Link to post
Share on other sites
Quote:
Original post by Quat
Thanks for the replies so far.

One thing I recently tried was to stop using push_back. Instead, I just used vector::operator[], and kept my own size counter. This is now comparable to the array performance.


Quote:
Original post by ToohrVyk
// Bad:
for(int i = 0; i < numVertices; ++i)
m_vertices.push_back(v);

// Good:
m_vertices.insert(m_vertices.end(), v, v+numVertices);


FFS.

Quote:
I noticed push_back has a conditional statement (in case it needs to resize). Do you think that is the extra overhead? I read hardware does not like branching statements.


This one should be quite well predicted, though.

Also, what is 'v'? And why do you need to recalculate this much geometry (is everything moving)? How much flexibility is needed?

(And what kind of geometry is that? A triangle between the centroid and every line segment on the outside?)

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
#define _SCL_SECURE 0


I had a similar issue in my code not so long ago. During my game-update phase, 80% (!) of the time was spent iterating std::vector's due to the checks it was making. I didn't know about _SCL_SECURE at the time, so I changed them all to do a C-style loop, which lowered the time to do an update from about 10ms to 2ms. I assume defining _SCL_SECURE to 0 would have the same effect though I haven't verified.

Good luck,
Geoff

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
Also, Kwizatz is showing off the perfect way to get your .reserve()s wrong, you want:


Yeah, I though about the case when there are already elements in the vertex after I posted, but I did not point it out, thank you for doing so MM, and sorry about that Quat. [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by gdunbar I didn't know about _SCL_SECURE at the time, so I changed them all to do a C-style loop

Hooray, and that's why I don't like Microsoft adding these macros. The lowered performance (in the normal case, when you don't actively define/undefine the correct sequence of macros) just makes people drop the C++ standard lib entirely, and fall back to C-style code... Just how much security did that buy anyone?

Share this post


Link to post
Share on other sites
I'm not a big fan of proprietary stuff like that either, but the first time I ran my program in 2005 upgraded from 2003 it caught several instances where I was doing bad things with iterators, so in that sense it was useful. IMO it should be disabled by default in release builds though.

Share this post


Link to post
Share on other sites
Quote:
Original post by Spoonbender
Quote:
Original post by gdunbar I didn't know about _SCL_SECURE at the time, so I changed them all to do a C-style loop

Hooray, and that's why I don't like Microsoft adding these macros. The lowered performance (in the normal case, when you don't actively define/undefine the correct sequence of macros) just makes people drop the C++ standard lib entirely, and fall back to C-style code... Just how much security did that buy anyone?


Negative amounts.

Share this post


Link to post
Share on other sites
One thing to watch out for is if you change the _SCL_SECURE and _HAS_ITERATOR_DEBUGGING defines and you're building a library, anything that uses the library should probably use the same settings too. I had a nightmare with my engine crashing randomly in release builds because I'd forgotten to add these defines into the release configuration for my test bed. To be honest, I ended up just switching to my own custom array class instead because I couldn't be bothered with all these special defines to make Microsoft's STL work quickly.

Share this post


Link to post
Share on other sites
Quote:
Original post by f8k8
To be honest, I ended up just switching to my own custom array class instead because I couldn't be bothered with all these special defines to make Microsoft's STL work quickly.


I personally would rather just change my compiler ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
Quote:
Original post by Spoonbender
Quote:
Original post by gdunbar I didn't know about _SCL_SECURE at the time, so I changed them all to do a C-style loop

Hooray, and that's why I don't like Microsoft adding these macros. The lowered performance (in the normal case, when you don't actively define/undefine the correct sequence of macros) just makes people drop the C++ standard lib entirely, and fall back to C-style code... Just how much security did that buy anyone?


Negative amounts.


I actually worked at Microsoft for 10 years (not in the developer tools division), so I understand why they made things the way they are. They believed that security was on the verge of becoming _the_ reason that people would stop using Microsoft software. So they took some pretty heavy-handed actions to fix the problem. It certainly is a pain-in-the-ass in this case though, to the point where it is legitimate to question their decision, as you guys are. I'm not sure where I stand; in my code I currently leave _SCL_SECURE on for checked builds but turn it off for release builds.

Geoff

Share this post


Link to post
Share on other sites
Quote:
Original post by gdunbar
I actually worked at Microsoft for 10 years (not in the developer tools division), so I understand why they made things the way they are. They believed that security was on the verge of becoming _the_ reason that people would stop using Microsoft software. So they took some pretty heavy-handed actions to fix the problem. It certainly is a pain-in-the-ass in this case though, to the point where it is legitimate to question their decision, as you guys are.

I understand why they added these "features". I'm just saying that in the end, I believe they're achieving the exact opposite.
Instead of making people write more secure code (by adding bounds-checking and other fluff to the STL), people are going to write *less* secure code because they see the STL performing too badly, and then assuming that the problem must be the STL itself, or C++ idioms, and then they retreat to C array, C strings, C everything. Buffer overflows, here we come.

I'm all for adding security checks like these in debug builds (and optionally in release builds=, but I believe they're shooting themselves in the foot security-wise by adding it to release builds by default. The performance hit is too noticeable, and people react by not using it. Not by "going back to regular vectors with _SCL_SECURE=0, but back to no vectors at all, back to C arrays and char*'s.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
// Bad:
for(int i = 0; i < numVertices; ++i)
m_vertices.push_back(v);

// Good:
m_vertices.insert(m_vertices.end(), v, v+numVertices);


Can you explain this more please? Or someone else. I'm currently using pushback for all my stl's in my game.

Share this post


Link to post
Share on other sites
Quote:
Original post by ViperG
Quote:
Original post by ToohrVyk
// Bad:
for(int i = 0; i < numVertices; ++i)
m_vertices.push_back(v);

// Good:
m_vertices.insert(m_vertices.end(), v, v+numVertices);


Can you explain this more please? Or someone else. I'm currently using pushback for all my stl's in my game.


The code does pretty much exactly what you'd expect it to, provided you have numVerts vertices laid out contiguously in memory starting at v. It will copy numVerts vertices starting from v onto the end of m_vertices, and is more efficient than adding each vert one at a time.

Share this post


Link to post
Share on other sites
Quote:
Original post by ViperG
Quote:
Original post by ToohrVyk
// Bad:
for(int i = 0; i < numVertices; ++i)
m_vertices.push_back(v);

// Good:
m_vertices.insert(m_vertices.end(), v, v+numVertices);


Can you explain this more please? Or someone else. I'm currently using pushback for all my stl's in my game.


In terms of the implementation, the first is a loop, and the second is equivalent to a single copy, as long as v is a POD type. If instead v is a non-POD type, copy constructors and destructors must be invoked for each instance, so you wont gain much in this case.

Share this post


Link to post
Share on other sites
Quote:
Original post by Spoonbender
Quote:
Original post by gdunbar
I actually worked at Microsoft for 10 years (not in the developer tools division), so I understand why they made things the way they are. They believed that security was on the verge of becoming _the_ reason that people would stop using Microsoft software. So they took some pretty heavy-handed actions to fix the problem. It certainly is a pain-in-the-ass in this case though, to the point where it is legitimate to question their decision, as you guys are.

I understand why they added these "features". I'm just saying that in the end, I believe they're achieving the exact opposite.

Ditto. The concept of "Don't pay for what you don't use" is integral to C++. It's the very reason every other sentence of the C++ standard screams "undefined behavior". It's hard enough to coax people into realizing the standard library is OK to use when this premise is followed -- and enabling these kind of checks by default in release mode is definitely not following this premise.

OTOH, those who actually care about security enough to use such features will have selected a saner language with better defined semantics -- because while these kind of checks are great and all in theory, they're still only covering some 1-2% of the whole nine yards of security holes. And since the writers of the SC++L re implementations won't care about security, this results in a net drop.

Not that Microsoft's worries aren't legitimate. IE7 came way too late for me to actually continue using IE. Hell, the only reason I'm still using windows is a legacy of piss-poor gaming support from WINE and the like. The only place they've gained traction with me is with their wonderful IDEs.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement