2.5 KiB
bullet-0003: btSortedOverlappingPairCache — O(N) findLinearSearch for pair lookup and removal
Severity: MEDIUM File: src/BulletCollision/BroadphaseCollision/btOverlappingPairCache.cpp Lines: 450, 494 Status: PATCHED
Description
btSortedOverlappingPairCache stores collision pairs in an unsorted btAlignedObjectArray<btBroadphasePair>. Both removeOverlappingPair and findPair call findLinearSearch to locate a pair in this array — O(N) per call.
The source contains two explicit acknowledgments of the defect:
// line 484-487:
///this findPair becomes really slow. Either sort the list to speedup the query,
///or use a different solution. It is mainly used for Removing overlapping pairs.
///Removal could be delayed.
// line 450: removeOverlappingPair (non-deferred path)
int findIndex = m_overlappingPairArray.findLinearSearch(findPair); // O(N)
// line 494: findPair
int findIndex = m_overlappingPairArray.findLinearSearch(tmpPair); // O(N)
removeOverlappingPair is called by btHashedOverlappingPairCache::processAllOverlappingPairs and btSortedOverlappingPairCache::cleanProxyFromPairs. During broadphase pair removal (objects leaving each other's AABB) with P total pairs, this is O(P) calls × O(P) scan = O(P²).
Root Cause
btSortedOverlappingPairCache is a simpler/older implementation that was not updated to use hashing. btHashedOverlappingPairCache already solves this correctly with a hash table — it is the recommended default. btSortedOverlappingPairCache remains in the codebase and is used when hasDeferredRemoval() returns true (its default).
Fix
Option 1 (preferred): Switch all callers from btSortedOverlappingPairCache to btHashedOverlappingPairCache, which provides O(1) addOverlappingPair/removeOverlappingPair/findPair via hash table (btOverlappingPairCache.cpp:100-260).
Option 2: Add a btHashMap<btBroadphasePairSortPredicate, int> index inside btSortedOverlappingPairCache that maps pair key → array index, updated on every insert/remove.
Speedup
| Active pairs (P) | Before (removal phase) | After (hash) |
|---|---|---|
| 100 | ~10 000 ops | ~100 ops |
| 1 000 | ~1 000 000 ops | ~1 000 ops |
| 5 000 | ~25 000 000 ops | ~5 000 ops |
Estimated ~1000x at P=1000 pairs during broadphase removal sweep. The btHashedOverlappingPairCache alternative is already present and correct.