🔒 Locked

std::map serial access

Started by sheep19 May 23, 2009 at 6:31 AM 7 replies 1.1k views

Original Post

May 23, 2009 at 6:31 AM

Is serial access too slow with std::map? _AnimationMap is std::map (Animation is a "container" of Sprite objects) Is the code below slow?


bool AnimatedSprite::Collision(const AnimatedSprite &spr1, const AnimatedSprite &spr2)
{
	registry_type::const_iterator it1 = spr1._AnimationMap.begin();
	registry_type::const_iterator it2 = spr2._AnimationMap.begin();

	registry_type::const_iterator end1 = spr1._AnimationMap.end();
	registry_type::const_iterator end2 = spr2._AnimationMap.end();

	for(; it1 != end1; std::advance(it1, 1) )
	{
		for(; it2 != end2; std::advance(it2, 1) )
		{
			const Sprite spr1 = *it1->second->_ImgVec[it1->second->_current];
			const Sprite spr2 = *it2->second->_ImgVec[it2->second->_current];
			
			if( Sprite::Collision(spr1, spr2) ) return true;
		}
	}

	return false;
}

Codeka

May 23, 2009 at 7:17 AM

I don't know, is it slow? Did you test? I don't see why it would be... What do you mean by "slow"?

However, I'd probably just say that you don't really need to use std::advance since you can just use ++it (std::advance(it, n) is the same as executing ++it n times)

Antheus

May 23, 2009 at 7:24 AM

Yes, it is "slow".

First, there is algorithmic "slowness". The code performs n^2 comparisons, when only n(n-1)/2 are needed.

Next, is the implementation "slowness".

Quote:
const Sprite spr1

This creates a copy of sprite. That is 2*n^2 new copies, when exactly 0 are needed. At minimum, do

const Sprite & spr1

Maps are also highly unsuitable for iteration, since they do not allocate memory continuously. The way the std::map usually lays out memory you are almost guaranteed a cache miss on each access.

Using vector to store the elements however would improve on all of the above by a considerable factor.

Codeka

May 23, 2009 at 7:46 AM

Quote:
Original post by Antheus
First, there is algorithmic "slowness". The code performs n^2 comparisons, when only n(n-1)/2 are needed.

Actually, I just read the code (heh) and it doesn't actually do n² comparisons, but that's only because there's a bug: it2 is not reset at the beginning of the outer loop. If you set it2 = it1 at the beginning of the outer loop, then you'll be doing the correct number of comparisons (which you can't really get away from for collisions without some kind of spacial partitioning, like a quadtree/octree)

Antheus

May 23, 2009 at 9:36 AM

Quote:
Original post by Codeka
Actually, I just read the code (heh) and it doesn't actually do n² comparisons, but that's only because there's a bug: it2 is not reset at the beginning of the outer loop. If you set it2 = it1 at the beginning of the outer loop, then you'll be doing the correct number of comparisons (which you can't really get away from for collisions without some kind of spacial partitioning, like a quadtree/octree)

I was too quick skimming over what looked like a typical collision test, which the above code isn't. It compares all possible pairs between two sets, and is therefore m*n.

But despite that, I always wrote "slow", since there exists a better way to implement inner loop, but it doesn't mean that current version (provided it worked correctly) would be a problem.

alvaro

May 23, 2009 at 2:22 PM

Quote:
Original post by sheep19
Is serial access too slow with std::map?

_AnimationMap is std::map (Animation is a "container" of Sprite objects)

Is the code below slow?

*** Source Snippet Removed ***

Its main problem is not that it's slow: It's just wrong. You never set it2 back to the beginning of the container, so you are only testing if the first object in spr1 collides with any objects in spr2. From that point on the inner loop is never entered, since it2 is at end2. If you declare and initialize local variables in the first place where they are used, you won't make this type of mistakes.

You cannot use the identifiers _AnimationMap and _ImgVec because they start with an underscore followed by a capital letter. See for instance this if you don't know why.

Why are you using std::advance(it1, 1)' instead of simply ++it1'?

As it was pointed out, instead of const Sprint spr1 = ...' you probably meant something like Sprint const & spr1 = ...'.

Minor issue: The function should probably be called simply Collision' instead of AnimatedSprite::Collision'. I guess it's a static member function, but a free function makes more sense.

There's a lot to fix here before you have to care about the performance of serial access to std::map (which, by the way, is not slow at all).

AshleysBrain

May 23, 2009 at 2:43 PM

It might even be incredibly slow, but it's of no concern to you whatsoever until you can prove it's taking a significant amount of time in your program. You'd prove that by profiling it. Even if the function can be made to run 100 times faster, if your program only spends 0.1% of its time in it, that's at most a 0.1% speed increase.

It is most important to write code that is correct and clear. After that, measure its performance with a profiler, then worry about what is slow.

sheep19

May 24, 2009 at 12:24 AM

I fixed it:

bool AnimatedSprite::Collision(AnimatedSprite &spr1, AnimatedSprite &spr2){	registry_type::const_iterator it1;	registry_type::const_iterator it2;	registry_type::const_iterator end1 = spr1._AnimationMap.end();	registry_type::const_iterator end2 = spr2._AnimationMap.end();	for(it1 = spr1._AnimationMap.begin(); it1 != end1; ++it1 )	{		for(it2 = spr2._AnimationMap.begin(); it2 != end2; ++it2 )		{			Sprite &s1 = (*it1->second->_ImgVec[it1->second->_current]);			Sprite &s2 = (*it2->second->_ImgVec[it2->second->_current]);			s1.SetPos(spr1.x(), spr1.y());			s2.SetPos(spr2.x(), spr2.y());			if( Sprite::Collision(s1, s2) ) return true;		}	}	return false;}

I don't need to iterator through all Sprites in every Animation, because I want to test the current frame (current Sprite).

alvaro

May 24, 2009 at 1:04 AM

Quote:
Original post by sheep19
I fixed it:

*** Source Snippet Removed ***

I don't need to iterator through all Sprites in every Animation, because I want to test the current frame (current Sprite).

Then you don't need two loops.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.