Performance optimization with btDiscreteDynamicsWorld.cpp

Post Reply
Digitalghost
Posts: 25
Joined: Thu Dec 20, 2007 4:03 am

Performance optimization with btDiscreteDynamicsWorld.cpp

Post by Digitalghost »

After running a profiler I found that a significant amount of processor was spend linearly searching for constraints. Because the constrains are sorted, I replaced the linear search with a binary search. This significantly improved performance. Attached is a patch to address this issue.

I included some debug code that you can turn on to verify that the same constraint is found every time

It will not let me upload the patch file, so I'm pasting it here:

Code: Select all

Index: btDiscreteDynamicsWorld.cpp

===================================================================

--- btDiscreteDynamicsWorld.cpp	(revision 1696)

+++ btDiscreteDynamicsWorld.cpp	(working copy)

@@ -591,9 +591,9 @@

 		}
 };
 
+#include <iostream>
+using namespace std;
 
-
-
 void	btDiscreteDynamicsWorld::solveConstraints(btContactSolverInfo& solverInfo)
 {
 	BT_PROFILE("solveConstraints");
@@ -647,9 +647,41 @@

 			{
 					//also add all non-contact constraints/joints for this island
 				btTypedConstraint** startConstraint = 0;
+				btTypedConstraint** tmpstartConstraint = 0;
 				int numCurConstraints = 0;
 				int i;
 				
+                //Use binary search to find the first constraint for this island
+			    int high, low;
+			    for ( low=(-1), high=m_numConstraints-1;  high-low > 1;  )
+			    {
+				    i = (high+low) / 2;
+                    int curID = btGetConstraintIslandId(m_sortedConstraints[i]);
+				    if (
+                        curID == islandId &&
+                        (i==0 || btGetConstraintIslandId(m_sortedConstraints[i-1]) != islandId)
+                        )
+				    {
+					    tmpstartConstraint = &m_sortedConstraints[i];
+                        break;
+				    }
+				    else if ( islandId <= curID  )
+					    high = i;
+				    else
+					    low  = i;
+			    }
+                if(
+                    high>=0 && 
+                   btGetConstraintIslandId(m_sortedConstraints[high]) == islandId &&
+                   (high==0 || btGetConstraintIslandId(m_sortedConstraints[high-1]) != islandId)
+                   )
+                {
+                    tmpstartConstraint = &m_sortedConstraints[high];
+                    i = high;
+                }
+				int tmpI = i;
+
+				/*
 				//find the first constraint for this island
 				for (i=0;i<m_numConstraints;i++)
 				{
@@ -659,6 +691,21 @@

 						break;
 					}
 				}
+				*/
+
+				startConstraint = tmpstartConstraint;
+				if(tmpstartConstraint != startConstraint)
+				{
+					cout << __FILE__ << " ERROR! " << tmpI << " != " << i << " Island ID: " << islandId << endl;
+
+					int j=0;
+					for (j=0;j<m_numConstraints;j++)
+					{
+						cout << btGetConstraintIslandId(m_sortedConstraints[j]) << ", ";
+					}
+					cout << endl;
+				}
+
 				//count the number of constraints in this island
 				for (;i<m_numConstraints;i++)
 				{
@@ -666,8 +713,13 @@

 					{
 						numCurConstraints++;
 					}
+					else
+					{
+						break;
+					}
 				}
 
+
 				///only call solveGroup if there is some work: avoid virtual function call, its overhead can be excessive
 				if (numManifolds + numCurConstraints)
 				{
thloh85
Posts: 26
Joined: Mon Feb 09, 2009 10:07 am

Re: Performance optimization with btDiscreteDynamicsWorld.cpp

Post by thloh85 »

Looks like a nice one. Hope your patch gets integrated.
ola
Posts: 169
Joined: Sun Jan 14, 2007 7:56 pm
Location: Norway
Contact:

Re: Performance optimization with btDiscreteDynamicsWorld.cpp

Post by ola »

It's recommended to upload the patch to the issue tracker at http://code.google.com/p/bullet/issues/list.

Great work! :-)
Digitalghost
Posts: 25
Joined: Thu Dec 20, 2007 4:03 am

Re: Performance optimization with btDiscreteDynamicsWorld.cpp

Post by Digitalghost »

ola wrote:It's recommended to upload the patch to the issue tracker at http://code.google.com/p/bullet/issues/list.

Great work! :-)
Alright, I submitted a patch for it.

I've been running Underworld Hockey Club for a few days now and I haven't tripped the error condition, so I think it's good to go in.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Performance optimization with btDiscreteDynamicsWorld.cpp

Post by Erwin Coumans »

Thanks a lot for the patch.

Note that we don't accept STL for Bullet. Is it possible to change the patch, and remove the following lines?

Code: Select all

+#include <iostream>
+using namespace std;
Thanks,
Erwin
Post Reply