Sign in to follow this  
Thomas M

Optimizing STL code

Recommended Posts

I basically have a std::vector of pointers to classes, and I want to retrieve the pointer by the member-variables of the classes. Currently I just iterate through the vector and compare every element, but this is pretty slow. :/ Is there a way to optimize this? Would a std::map be faster? For example, I'm using code like this pretty often in my game:
class EntityManager : public Singleton<EntityManager> {
...

public:
  Entity* getEntity(u32 net_id) {
	Entity *ret = 0;

	EntityIterator iter;
	for(iter = m_entities.begin(); iter != m_entities.end(); ++iter) {
		if((*iter)->m_network_id == net_id) {
			ret = (*iter);
			break;
		}
	}

	return ret;
  }
}
Also, when using Debug-Mode STL seems to be very slow. Is there a Compiler-Flag in Vc2005 to make STL in Debug-Mode faster? Because in Release-Mode im pretty satisfied with the performance.

Share this post


Link to post
Share on other sites
If all you do is lookup by net_id, a std::map with the net_id as a key would probably be faster.

Also, MSVC 2005 has a lot of debug checking for iterator code in debug mode. You can disable this by #defining _HAS_ITERATOR_DEBUGGING as 0.

Share this post


Link to post
Share on other sites
I believe a std::map is exactly what you want:


std::map< u32, Entity* > mEntities;

Entity* getEntity( u32 net_id )
{
if ( !mEntitied.empty() )
{
std::map< u32, Entity* >::iterator it = mEntities.find( u32 );
if ( it != mEntites.end() )
{
return it.second();
}
}

return NULL;
}




think the syntax is correct.... it's at least close =)

Share this post


Link to post
Share on other sites
Quote:
Is there a way to optimize this?


Not really.

Quote:
Would a std::map be faster?


Yes. O(logn) vs. O(n).

For 100 elements, that's 7 vs. 100.
For 1,000 elements, that's 10 vs. 1,000.
For 10,000 elements, it's 13 vs. 10,000.

Actual numbers may vary obviously, but hopefully the difference is obvious.

Quote:
Is there a Compiler-Flag in Vc2005 to make STL in Debug-Mode faster?


I never understood why on earth people would care about debug mode performance. It's called debug for a reason - it's used for debugging, which means you'll spend most of time with application paused, stepping through the code.

Quote:
Because in Release-Mode im pretty satisfied with the performance.


It may run fast enough, but it's still taking more than a factor of 100x more resources than it could. And the change to map would result in reduction of the above code to 2 lines.


typedef std::map<u32, Entity*> EntityMap;

...

Entity * getEntity( u32 net_id )
{
EntityMap::const_iterator i = m_entities.find(net_id);
return (i == mEntities.end()) ? NULL : m_entities->second;
};

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Quote:
Is there a way to optimize this?

I never understood why on earth people would care about debug mode performance.

The first time you spend eighteen minutes waiting for your application to fully load, then trudge around for awhile at four frames per second, all so that you can reproduce a segfault that only seems to happen under very specific conditions, you will.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Quote:
Original post by Antheus
Quote:
Is there a way to optimize this?

I never understood why on earth people would care about debug mode performance.

The first time you spend eighteen minutes waiting for your application to fully load, then trudge around for awhile at four frames per second, all so that you can reproduce a segfault that only seems to happen under very specific conditions, you will.


Under MVS I enable stack frames and include debug symbols in release build. Line numbers are sometimes off, but otherwise the overhead is next to none, definitely not the same as with full debug build.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this