russell@unturf.com
1b98cac200
cocos2d-0001: EventDispatcher _toRemovedListeners std::find O(L*R) MEDIUM 2.4x cocos2d-0002: PhysicsWorld collisionBeginCallback std::find O(J_body*J_world) MEDIUM 11.6x cocos2d-0003: BoneNode::visit _boneSkins.contains O(C*S) per frame MEDIUM 7.3x MOAD-0002 (Intertangle): heavy singleton pattern (Director, etc.) but architectural, not patchable MOAD-0003 (Leaked Context): no thread_local usage, CLEAN MOAD-0004 (Logged Secret): no credential logging, CLEAN MOAD-0005 (Thundering Herd): TextureCache uses unordered_map, CLEAN 6/6 unit tests PASS.
93 lines
3.5 KiB
C++
93 lines
3.5 KiB
C++
// Unit test for cocos2d-0002: PhysicsWorld::collisionBeginCallback O(J_body * J_world)
|
|
// Defect: std::find on _joints vector inside per-body-joint loop in collision callback.
|
|
// Called every physics frame for every contact pair. O(J_body * J_world).
|
|
// Fix: Build std::unordered_set from _joints for O(1) lookup.
|
|
|
|
#include <vector>
|
|
#include <unordered_set>
|
|
#include <chrono>
|
|
#include <cstdio>
|
|
#include <cassert>
|
|
#include <algorithm>
|
|
|
|
struct Joint {
|
|
int id;
|
|
bool collisionEnabled;
|
|
};
|
|
|
|
// Defect: linear scan of worldJoints for each bodyJoint
|
|
int defectCollisionCheck(const std::vector<Joint*>& bodyJoints,
|
|
const std::vector<Joint*>& worldJoints) {
|
|
int checked = 0;
|
|
for (auto* joint : bodyJoints) {
|
|
if (std::find(worldJoints.begin(), worldJoints.end(), joint) == worldJoints.end())
|
|
continue;
|
|
if (!joint->collisionEnabled)
|
|
checked++;
|
|
}
|
|
return checked;
|
|
}
|
|
|
|
// Fixed: hash set from worldJoints for O(1) lookup per query
|
|
// In practice, the set would be maintained incrementally as joints are added/removed.
|
|
// Here we build it once and reuse across all frames to model the amortized cost.
|
|
int fixedCollisionCheck(const std::vector<Joint*>& bodyJoints,
|
|
const std::unordered_set<Joint*>& jointSet) {
|
|
int checked = 0;
|
|
for (auto* joint : bodyJoints) {
|
|
if (jointSet.find(joint) == jointSet.end())
|
|
continue;
|
|
if (!joint->collisionEnabled)
|
|
checked++;
|
|
}
|
|
return checked;
|
|
}
|
|
|
|
int main() {
|
|
const int J_WORLD = 10000; // joints in the world (large physics scene)
|
|
const int J_BODY = 500; // joints per body (ragdoll + constraints)
|
|
const int FRAMES = 1000; // simulate 1000 collision callbacks per frame
|
|
|
|
std::vector<Joint> pool(J_WORLD);
|
|
for (int i = 0; i < J_WORLD; i++) {
|
|
pool[i].id = i;
|
|
pool[i].collisionEnabled = (i % 3 != 0);
|
|
}
|
|
|
|
std::vector<Joint*> worldJoints;
|
|
for (int i = 0; i < J_WORLD; i++) worldJoints.push_back(&pool[i]);
|
|
|
|
// Body has first J_BODY joints
|
|
std::vector<Joint*> bodyJoints;
|
|
for (int i = 0; i < J_BODY; i++) bodyJoints.push_back(&pool[i]);
|
|
|
|
// === Defect ===
|
|
auto t0 = std::chrono::high_resolution_clock::now();
|
|
int defectTotal = 0;
|
|
for (int f = 0; f < FRAMES; f++)
|
|
defectTotal += defectCollisionCheck(bodyJoints, worldJoints);
|
|
auto t1 = std::chrono::high_resolution_clock::now();
|
|
double defectUs = std::chrono::duration<double, std::micro>(t1 - t0).count();
|
|
|
|
// === Fixed ===
|
|
// Build the set once (amortized: maintained incrementally in real code)
|
|
std::unordered_set<Joint*> jointSet(worldJoints.begin(), worldJoints.end());
|
|
auto t2 = std::chrono::high_resolution_clock::now();
|
|
int fixedTotal = 0;
|
|
for (int f = 0; f < FRAMES; f++)
|
|
fixedTotal += fixedCollisionCheck(bodyJoints, jointSet);
|
|
auto t3 = std::chrono::high_resolution_clock::now();
|
|
double fixedUs = std::chrono::duration<double, std::micro>(t3 - t2).count();
|
|
|
|
assert(defectTotal == fixedTotal);
|
|
|
|
double ratio = defectUs / fixedUs;
|
|
printf("cocos2d-0002: PhysicsWorld::collisionBeginCallback O(J_body * J_world)\n");
|
|
printf(" J_WORLD=%d, J_BODY=%d, FRAMES=%d\n", J_WORLD, J_BODY, FRAMES);
|
|
printf(" defect: %.1f us\n", defectUs);
|
|
printf(" fixed: %.1f us\n", fixedUs);
|
|
printf(" ratio: %.1fx\n", ratio);
|
|
printf(" PASS: %s\n", (defectTotal == fixedTotal) ? "true" : "false");
|
|
|
|
return (defectTotal == fixedTotal) ? 0 : 1;
|
|
}
|