Skip to main content
gamedev.net
🔒 Locked

Optimization

Started by juxie Jan 24, 2008 at 9:44 AM 22 replies 2.1k views
Original Post
juxie
juxie
Hi, I am looking for a way which I can optimize the following codes. I hope there could be a help. Thank you. Here is the codes: (_shear is vector containing Spring* and assuming that _shear.size() returns 2000) 

	// Calculate shear spring forces
	for( int i = 0; i < (int) _shear.size(); i++ )
	{
		Spring* s = _shear;

		Particle* p1 = _parList[s->_index1];
		Particle* p2 = _parList[s->_index2];

		D3DXVECTOR3 tDir = p2->_pos - p1->_pos;
		D3DXVECTOR3 tVel = p2->_vel - p1->_vel;

		float tL = D3DXVec3Length(&tDir);
		D3DXVec3Normalize(&tDir, &tDir);

		D3DXVECTOR3 tForce = - s->_kS * (tL - s->_rL) * tDir;
		tForce += - s->_kD * tVel;

		p1->_force += -tForce;
		p2->_force += tForce;
	}
Sneftel
Sneftel
There are teeny math things and other microoptimizations you could do, but nothing jumps out as terrible. How many times are you executing it per frame?
juxie
juxie
I implemented Euler and RK4 to execute the loop.
There are 3 types of similar loop though for different type of springs.

So that makes:
Euler, execute 3 * 1 times per frame.
RK4, execute 3 * 4 times.
Evil Steve
Evil Steve
This code might cause two sqrt calls:
float tL = D3DXVec3Length(&tDir);
D3DXVec3Normalize(&tDir, &tDir);
You could inline your own version of D3DXVec3Normalize (After checking the generated assembly to make sure it is doing two square roots of course).

Aside from that, there's nothing obvious I see. Have you profiled this and shown that this is a bottleneck? Otherwise optimising it is totally pointless.

Is there any algorithmic change you can make, such as not checking all 2000 springs each frame; I.e. only checking modified ones, or only checking 200 springs per frame or something?
How big is _parList? Is it small enough to fit in the CPU cache? Do you have the secure STL turned on? There's a preprocessor definition you can change to disable it, which might speed up your vector access slightly.

But the main thing is to optimise the algorithm wherever possible. You'll see much more improvement from that that tweaking the code.
jpetrie
jpetrie
Moving to General Programming.
juxie
juxie
Quote:
Original post by Evil Steve
This code might cause two sqrt calls:
float tL = D3DXVec3Length(&tDir);
D3DXVec3Normalize(&tDir, &tDir);
You could inline your own version of D3DXVec3Normalize (After checking the generated assembly to make sure it is doing two square roots of course).

Aside from that, there's nothing obvious I see. Have you profiled this and shown that this is a bottleneck? Otherwise optimising it is totally pointless.

Is there any algorithmic change you can make, such as not checking all 2000 springs each frame; I.e. only checking modified ones, or only checking 200 springs per frame or something?
How big is _parList? Is it small enough to fit in the CPU cache? Do you have the secure STL turned on? There's a preprocessor definition you can change to disable it, which might speed up your vector access slightly.

But the main thing is to optimise the algorithm wherever possible. You'll see much more improvement from that that tweaking the code.


Thanks Evil Steve.
I haven't actually profiled as I have no experience using profiler so far.
Will try to pick up asap.

But what I did was remove the part that calculates the springs and notice the frame rate increases by a few times.

I am actually developing a cloth simulation and I am afraid I will need to calculate the forces produced by every springs.

Another thing I might try is to optimize the rendering by using batches as advised by http://www.gamedev.net/reference/articles/article1946.asp

And probably replacing those loops into using for_each() as in Scott Myers books.

I am not sure if those will help but I will give it a try.
d00fus
d00fus
As Evil Steve has said, large-scale algorithmic changes will produce the best results: the fastest work is the work you don't do at all. However, failing that, converting your code to SIMD (for example, using SSE on Intel) will likely make quite significant gains. This is not a trivial task and will require making data structure changes as well as rewriting the code. You should be able to find more information on this by googling and in these forums if you want to go down this route.

But most importantly - you should only attempt this once you have determined your bottlenecks through profiling and know your way reasonably well around your chosen profiling tool, as you'll need to keep using this while making changes to the code.
Spoonbender
Spoonbender
Quote:
Original post by juxie
I implemented Euler and RK4 to execute the loop.
There are 3 types of similar loop though for different type of springs.

So that makes:
Euler, execute 3 * 1 times per frame.
RK4, execute 3 * 4 times.

......

What, really?

In that case, you can start worrying about performance when you do it a maybe ten thousand times more often.

Honestly, profile *first*. Find out if the time spent on this bit of code is even big enough to be measured. Then you can decide if it's worth optimizing.
d00fus
d00fus
Quote:
Original post by Spoonbender
......

What, really?

In that case, you can start worrying about performance when you do it a maybe ten thousand times more often.

Honestly, profile *first*. Find out if the time spent on this bit of code is even big enough to be measured. Then you can decide if it's worth optimizing.


The point is totally valid but the OP indicated they had around 2000 springs, so he's executing the code at least 6000 times per frame - so I can believe it's a possible optimization target :) However as you and I both pointed out, the OP should profile first to check this.
Zahlman
Zahlman
Are Spring objects polymorphic? If not, why store them by pointer? Indirection hurts - not only the dereference itself, but also in terms of cache coherency. Idem for Particles in the _parList.

As noted: instead of calling the normalize function, you could just divide by the length to avoid it being re-calculated internally. (I'm wondering if the fact that the D3D functions use pointers rather than references could inhibit inlining :s)

Also, consider using std::for-each - or at the least, iterators rather than indices - for iterating through the vector. Also, I've been told that compilers often have difficulty optimizing out repeated calls to things like .size() (even when it should be patently obvious that it's a loop invariant) because of aliasing issues (the danger of working in an unsafe language like C++).

There are other things about the mathematical expression that look a bit, well, odd to me (why not calculate tForce in one line? Why not just use -= to subtract it?), but you're not realistically going to lose performance for *those* things unless your compiler was written by drunk college students at 1am for an assignment ;)
iMalc
iMalc
Here's a cleanup of the posted code. I improved style issues, and showed the optimisation to remove a duplicate sqrt, that EvilSteve was talking about.
Do these really need to be vectors of pointers instead of objects?
	// Calculate shear spring forces	for( vector<Spring*>::const_iterator it = _shear.begin(); it != _shear.end(); ++it)	{		const Spring& s = *it;		Particle& p1 = *_parList[s._index1];		Particle& p2 = *_parList[s._index2];		D3DXVECTOR3 tDir = p2._pos - p1._pos;		D3DXVECTOR3 tVel = p2._vel - p1._vel;		float tL = D3DXVec3Length(&tDir);		D3DXVec3Scale(&tDir, &tDir, 1.f / tL);		D3DXVECTOR3 tForce = s._kS * (tL - s._rL) * tDir + s._kD * tVel;		p1._force += tForce;		p2._force -= tForce;	}
juxie
juxie
Quote:
Original post by d00fus
Quote:
Original post by Spoonbender
......

What, really?

In that case, you can start worrying about performance when you do it a maybe ten thousand times more often.

Honestly, profile *first*. Find out if the time spent on this bit of code is even big enough to be measured. Then you can decide if it's worth optimizing.


The point is totally valid but the OP indicated they had around 2000 springs, so he's executing the code at least 6000 times per frame - so I can believe it's a possible optimization target :) However as you and I both pointed out, the OP should profile first to check this.


Thanks d00fus and Spoonbender.

I will get a profiler and check if that part of my code is the bottleneck.
Do you think PIX can help?
Do you know if there is any free license profiler?
juxie
juxie
Quote:
Original post by Zahlman
Are Spring objects polymorphic? If not, why store them by pointer? Indirection hurts - not only the dereference itself, but also in terms of cache coherency. Idem for Particles in the _parList.

As noted: instead of calling the normalize function, you could just divide by the length to avoid it being re-calculated internally. (I'm wondering if the fact that the D3D functions use pointers rather than references could inhibit inlining :s)

Also, consider using std::for-each - or at the least, iterators rather than indices - for iterating through the vector. Also, I've been told that compilers often have difficulty optimizing out repeated calls to things like .size() (even when it should be patently obvious that it's a loop invariant) because of aliasing issues (the danger of working in an unsafe language like C++).

There are other things about the mathematical expression that look a bit, well, odd to me (why not calculate tForce in one line? Why not just use -= to subtract it?), but you're not realistically going to lose performance for *those* things unless your compiler was written by drunk college students at 1am for an assignment ;)


Thanks Zahlman and iMalc

The spring and particle objects are not polymorphic but i don't necessarily create them during initialization.
They may be created at a press of a button.
Should I do it like this?
vector<Spring&> _stretch;for( int i = 0; i < 10; i++ ){    Spring temp;    _stretch.push_back(temp);}


I have checked D3DXVec3Length does have a sqrt but I didn't see any in D3DXVec3Normalize. I might be wrong though.

The mathematical expression is more for the purpose of saying that the spring force formula is - kS * (tL - rL) * tDir - kD * tVel as sometimes.

[Edited by - juxie on January 28, 2008 3:13:06 AM]
juxie
juxie
I run an intel profiler using the simple quick performance analyzer.
Please follow the link below.

Free Image Hosting at www.ImageShack.us

Free Image Hosting at www.ImageShack.us

It shows that the bottleneck is in the CalculateForce() where I calculate the spring force.
Just for updates, I have already changed the original loop to use for_each.
So now it looks like this:

for_each(_stretch.begin(); _stretch.end(); mem_fun(&Spring::CalculateForce());


But there is one more CPU killer which takes more than 35% time.
I am not sure whether I can actually do someting about that.
Hope to get your advises please.

Thanks.

[Edited by - juxie on January 28, 2008 3:37:01 AM]
Adam_42
Adam_42
From looking at that first picture VTune isn't able to get at the symbols or exports in the DLLs, but it's fairly clear that that function is taking a big chunk of CPU time. You also seem to be using the debug version of D3DX which won't help things (you should turn that off in the DirectX control panel when performance testing).

Firstly that msvcr80.dll is the C runtime library, which contains a lot of functions. You need to work out which one(s) are taking most of the time, and where you call them from. Linking it statically (the Runtime Library option under C++ Code Generation settings) may help the profiler work out what the functions are.

Here's a version I've tweaked for speed, the main thing I did was to drop the D3DX calls (in my experience it's often quicker to inline them due to function call overhead and aliasing issues). I also unrolled the loop to allow the optimizer to have a better chance of scheduling it nicely (the loop unrolled by the compiler itself would probably have aliasing issues).

You might also get a bit more speed by optimizing memory access patterns. You seem to have a lot of indirection which could mean the memory accesses are fairly random causing cache misses. If you can do so, try and make sure the spring and particle access is roughly linear by a preprocessing step it may help significantly.

If you need a faster version than that then extra unrolling may help a little, but I don't see much more that can be done apart from reducing the number of springs, or switching to SSE intrinsics or assembly.

	const int nUnroll = 2;	const int nSizeLeft = _shear.size() % nUnroll;	const int nLoopSize = _shear.size() - nSizeLeft;	// Calculate shear spring forces	for( int i = nSizeTimes2 - nUnroll; i >= 0; i -= nUnroll )	{		Spring* s1 = _shear;		Spring* s2 = _shear[i+1];		Particle* s1p1 = _parList[s1->_index1];		Particle* s1p2 = _parList[s1->_index2];		Particle* s2p1 = _parList[s2->_index1];		Particle* s2p2 = _parList[s2->_index2];		D3DXVECTOR3 tDir1 = s1p2->_pos - s1p1->_pos;		D3DXVECTOR3 tVel1 = s1p2->_vel - s1p1->_vel;		D3DXVECTOR3 tDir2 = s2p2->_pos - s2p1->_pos;		D3DXVECTOR3 tVel2 = s2p2->_vel - s2p1->_vel;		float tL1 = sqrtf(tDir1.x * tDir1.x + tDir1.y * tDir1.y + tDir1.z * tDir1.z);		float tL2 = sqrtf(tDir2.x * tDir2.x + tDir2.y * tDir2.y + tDir2.z * tDir2.z);		float itL1 = 1.0f / tL1;		float itL2 = 1.0f / tL2;		tDir1.x *= itL1; tDir1.y *= itL1; tDir1.z *= itL1;		tDir2.x *= itL2; tDir2.y *= itL2; tDir2.z *= itL2;		D3DXVECTOR3 tForce1 = (-s1->_kS * (tL1 - s1->_rL) * tDir1) - (s1->_kD * tVel1);		D3DXVECTOR3 tForce2 = (-s2->_kS * (tL2 - s2->_rL) * tDir2) - (s2->_kD * tVel2);		s1p1->_force += -tForce1;		s1p2->_force += tForce1;		s2p1->_force += -tForce2;		s2p2->_force += tForce2;	}	for( int i = nSizeLeft; i >= 0; i-- )	{		Spring* s = _shear;		Particle* p1 = _parList[s->_index1];		Particle* p2 = _parList[s->_index2];		D3DXVECTOR3 tDir = p2->_pos - p1->_pos;		D3DXVECTOR3 tVel = p2->_vel - p1->_vel;		float tL = D3DXVec3Length(&tDir);		D3DXVec3Normalize(&tDir, &tDir);		D3DXVECTOR3 tForce = - s->_kS * (tL - s->_rL) * tDir;		tForce += - s->_kD * tVel;		p1->_force += -tForce;		p2->_force += tForce;	}
Zahlman
Zahlman
Quote:
Original post by juxie
The spring and particle objects are not polymorphic but i don't necessarily create them during initialization.
They may be created at a press of a button.
Should I do it like this?
*** Source Snippet Removed ***


No, storing references doesn't work. Store values. When you create one, just push_back() a value. Don't think "I have to allocate things dynamically with 'new' because I don't know how many there will be". That allocation is exactly the std::vector's job.

Quote:
I have checked D3DXVec3Length does have a sqrt but I didn't see any in D3DXVec3Normalize. I might be wrong though.


Logically, it needs to - at least indirectly. It probably makes a call to D3DXVec3Length instead ;) Logically, normalization is the process of dividing by length. If you need the length information *anyway*, it makes more sense to do the division directly yourself.
Jerax
Jerax
Why normalize at all?

You can rewrite the code:
float tL = D3DXVec3Length(&tDir);D3DXVec3Normalize(&tDir, &tDir);D3DXVECTOR3 tForce = - s->_kS * (tL - s->_rL) * tDir;


as

float tL = D3DXVec3Length(&tDir);D3DXVECTOR3 tForce = - s->_kS * (1 - s->_rL/tL) * tDir;


You save yourself a couple of divides/muls that way.
Striken
Striken
Following on from Adam_42 I would also:

const int nUnroll = 2;const int nSizeLeft = _shear.size() % nUnroll;const int nLoopSize = _shear.size() - nSizeLeft;Spring *s1 = NULL;Spring *s2 = NULL;Particle* s1p1 = NULL;Particle* s1p2 = NULL;Particle* s2p1 = NULL;Particle* s2p2 = NULL;D3DXVECTOR3 tDir1;D3DXVECTOR3 tVel1;D3DXVECTOR3 tDir2;D3DXVECTOR3 tVel2;D3DXVECTOR3 tForce1D3DXVECTOR3 tForce2float tL1 = 0.f;float tL2 = 0.f;float itL1 = 0.f;float itL2 = 0.f;// Calculate shear spring forcesfor( int i = nSizeTimes2 - nUnroll; i >= 0; i -= nUnroll ){	s1 = _shear;	s2 = _shear[i+1];	s1p1 = _parList[s1->_index1];	s1p2 = _parList[s1->_index2];	s2p1 = _parList[s2->_index1];	s2p2 = _parList[s2->_index2];	tDir1 = s1p2->_pos - s1p1->_pos;	tVel1 = s1p2->_vel - s1p1->_vel;	tDir2 = s2p2->_pos - s2p1->_pos;	tVel2 = s2p2->_vel - s2p1->_vel;	tL1 = sqrtf(tDir1.x * tDir1.x + tDir1.y * tDir1.y + tDir1.z * tDir1.z);	tL2 = sqrtf(tDir2.x * tDir2.x + tDir2.y * tDir2.y + tDir2.z * tDir2.z);	itL1 = 1.0f / tL1;	itL2 = 1.0f / tL2;	tDir1.x *= itL1; tDir1.y *= itL1; tDir1.z *= itL1;	tDir2.x *= itL2; tDir2.y *= itL2; tDir2.z *= itL2;	tForce1 = (-s1->_kS * (tL1 - s1->_rL) * tDir1) - (s1->_kD * tVel1);	tForce2 = (-s2->_kS * (tL2 - s2->_rL) * tDir2) - (s2->_kD * tVel2);	s1p1->_force += -tForce1;	s1p2->_force += tForce1;	s2p1->_force += -tForce2;	s2p2->_force += tForce2;}


Do that.


Perhaps a guru could correct me or not but I've always believed that any new variable declared inside a loop is deconstructed/reconstructed for each iteration - so if you do not need the variable's explicit constructor to be called during each iteration of the loop, then initialize them outside.
Teach a programmer an answer, he can code for a day. Show a programmer the documentation, he can code for a lifetime.
stonemetal
stonemetal
Also look up optimization on msdn. you should find things like noalias and some of the other function decorations.
juxie
juxie
Quote:
Original post by Jerax
Why normalize at all?

You can rewrite the code:
*** Source Snippet Removed ***

as

*** Source Snippet Removed ***

You save yourself a couple of divides/muls that way.


Thanks it increases the FPS by about 20.

Topic Locked

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

Sign in to reply to this topic.