Sign in to follow this  

Vector Efficiency question

This topic is 1256 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

Hi Guys,
 
I am writhing a game where I have all of the game assets in an std::vector.
 
But, I am wondering if there is a faster way to do what I am doing.
 
Essentially, when ever I deal with a particular game asset I get the data from it similar to below
 

std::vector<ObjectInstance>::iterator it;
for(it=vObject.begin();it<vObject.end();it++)
{
	if(szName==it->szName.c_str())
		return it->x;
}

So, everything is handled this way, collisions, rendering, positioning, etc...

I am finding (in particular collisions) that this seems to be fairly expensive on the CPU as I am calling the above code (or similar to) possibly several hundred (maybe thousand) times per loop. Whilst it works perfectly in its current form, I am worried that when I get a lot of game assets in the scene (currently only four) that this will be too slow.

For example, I have a function that sorts out collisions and if the object is intersecting with another object the function calls a while loop to place the object back where it should have been before the collision.

So, I did a check. If the object is 256 pixels deep into the other object it takes 0.5 seconds for the loop to be exited.

Normally you wouldn't let an object collide that far into another object. But, the recovery time is quite long.

Some testing points the finger at the Vector routine (as it loops over and over).

Is there a faster way to achieve what I am after (while making the code as flexible as it is)?

Thanks in advance smile.png

Share this post


Link to post
Share on other sites
If you always search for objects by name, you could use std::map to get the right one. That way the lookup is only O(log n) instead of O(n); you won't see a difference with your 4 objects, but once you add more objects you will see the difference. When using std::map, you might also take a look at hashing to avoid string compares when looking for the data, as string compares can be quite expensive compared to integer compares.

Share this post


Link to post
Share on other sites

I don't really understand how you use that code.. it would be interesting to see an usage example.

 

If you are retrieving often your entities by name (but I don't see why you should).. you might want to use a std::map<string,Object*> .

 

As I said.. I don't see why you'd want to call your objects by name.. to do stuff on your objects you just need a loop:

 

for (auto object : objects)

{

object->doStuff();

}

Share this post


Link to post
Share on other sites
That will call doStuff on every object. If you only want to call a method on one object, however, it's not helpful.

I'll also suggest that you use a map for lookups, but I would suggest changing the key from string to some kind of id like an unsigned int. Maybe hash the string, for example.

Share this post


Link to post
Share on other sites
Thanks for the suggestions so far guys :)

So the string comparisons are relatively slow? The reason behind it was so I could call objects "player", "ground", "enemy", etc..

I could 'define' or 'enum' them instead if that would speed up the loop.

Share this post


Link to post
Share on other sites

The reason to put object in a list is to allow fast iterations of common operations.

If you need operation on a "player".. then you should have a Object* player; Object* ground; and so on.. having to go through a list to find a object EVERY TIME makes no sense, and having a list without performing common operations on that list doesn't make sense.

 

Unless it's a VERY rare occurrence, it should never be necessary to retrieve an element from a list, by name, in the game loop.

 

In other words.. if you are retrieving an object by name "hundreds" of time in a frame, you are doing it wrong, map or no map.

Edited by kunos

Share this post


Link to post
Share on other sites
Thanks for the reply kunos.

You are probably right. I'll have to take a look at my code and see if I can remember why I went down that vector path in the first place - LOL

I am about a month in to this project (i remember it made sense at the time of designing - but no idea at the moment - due to being sleepy hehe).

I am about to go to bed and am way too tired to think at the moment. So, I'll take a look again in the morning when I am refreshed again.

[edit]
Thinking further on this I can't see how you could avoid retrieving object information hundreds of times per frame, as a level might consist of hundreds of ground tiles alone.

In my object class I have a variable that marks the object as solid and then I sort these (once) per loop to bring the solid objects to the top of the vector to cut out unnecessary comparisons. So, if I have 100 solid objects and 900 un-solid objects the loop will be more efficient than an unsorted one.

But yeah, I'll take a good look at what I am doing in the morning.

Thanks again so far. :)

Share this post


Link to post
Share on other sites

If you are using a vector, you will get a contiguous block of memory used for your objects which may be helpful for cache performance and things like that.  If you want to find a particular entity, then I would suggest using an index into the vector instead of by string name.  You could easily create a helper function to convert to / from index and name, which will ease the process.

 

I wouldn't see any particular need to use a map in this case, since you don't need to really store the items by a unique ID or key.

Share this post


Link to post
Share on other sites

With regards to iterating over all objects in a given container, there's really nothing that beats vector.  It's unlikely that changing the container will have any significant impact on your collision detection code.  Should be perfectly fine for entity logic and rendering though, and there are options to eliminate the necessity of actually deleting elements in the vector to avoid that problem.

 

For collision detection though, If your collision detection algorithm is O(N^2), there's no container that's going to allow that sort of brute force method to work even remotely efficiently for large N.  You need to focus more on the collision detection algorithm itself, partition your objects to minimize the total number of collision tests that need to be made.  A simple grid, a BSP tree, etc.  That's where you'll see real gains.

Share this post


Link to post
Share on other sites

So the string comparisons are relatively slow?
 

 

You would have to get very creative to find a slower way.

 

Perhaps you load a data file into a vector (or map) with string names, but then you would process that data into trees of data using pointers.

Share this post


Link to post
Share on other sites

This topic is 1256 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.

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